栈和队列ADT

栈模型

  • 限制插入和删除只能在表的末端的表
  • 表的末端叫做栈顶(top)
  • 支持Push进栈和Pop入栈操作
  • //LIFO后进先出表

栈的实现

链表实现

类型声明

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
struct Node ;
typedef struct Node *PtrToNode ;
typedef struct Node Stack

int IsEmpty(Stack S) ;
Stack CreateStack(void) ;
void DisposeStack(Stack S) ;
void MakeEmpty(Stack S) ;
void Push(ElementType X,Stack S) ;
ElementType Top(Stack S) ;
void Pop(Stack s) ;

struct Node
{
ElementType Element ;
PtrToNode Next ;
}

检测是否为空栈

1
2
3
4
void IsEmpty(Stack S)
{
return S->Next == NULL ;
}

创建空栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
Stack CreateStack(void)
{
Stack S ;
S = malloc(sizeof(struct Node)) ;
if(S == NULL)
{
FatalError("内存不足") ;
}
S->Next = NULL ;
MakeEmpty(S) ;
return S ;
}

void MakeEmpty(Stack S)
{
if(S == NULL)
{
Error("请先创建一个栈") ;
}
else
{
while(!IsEmpty(S)
Pop(S) ;
}
}

Push进栈

1
2
3
4
5
6
7
8
9
10
11
12
13
void Push(ElementType X, Stack S)
{
PtrToNode TmpCell ;
TmpCell = malloc(sizeof(struct Node)) ;
if(TmpCell == NULL)
FaltalError("内存不足") ;
else
{
TmpCell->Element = X ;
TmpCell->Next = S->Next ;
S->Next = TmpCell ;
}
}

返回top栈顶元素

1
2
3
4
5
6
7
ElementType Top(Stack S)
{
if(!IsEmpty(S)
return S->Next->ElementType ;
Error("空栈") ;
return 0 ;
}

Pop出栈

1
2
3
4
5
6
7
void Pop(Stack S)
{
PtrToNode FirstCell ;
FirstCell = S->Next ;
S->Next = FirstCell->Next ;
free(FirstCell) ;
}

数组实现

  • 潜在危害:需要提前声明栈的大小
  • 实现思路:
    1. 栈指针TopOfStack //并不是指针,只是指示下标
    2. 压栈Stack[TopOfStack] = x TopOfStack++ ;
    3. 出栈,TopOfStack– ;

      栈的声明

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      struct StackRecord ;
      typedef struct StackRecord *Stack ;

      int IsEmpty(Stack S) ;
      Stack CreateStack(int MaxElements) ;
      void DisposeStack(Stack S) ;
      void MakeEmpty(Stack S) ;
      void Push(ElementType X,Stack S) ;
      ElementType Top(Stack S) ;
      void Pop(Stack s) ;

      #define EmptyTOS(-1) ; //空栈标志
      #define MinStackSize (5) ;

      struct Node
      {
      ElementType *Array ;
      int Capacity ;
      int TopOfStack ;
      }

栈的创建//数组实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Stack CreateStack(int MaxElements)
{
Stack S ;

if(MaxElements < MinStackSize)
Error("栈过小") ;
S = malloc(sizeof(struct Node) ;
if(S == NULL)
FatalError("内存不足") ;
S->Array = malloc(sizeof(struct Node) * MaxElements) ;
if(S->Array = NULL)
FatalError("内存不足") ;
S->Capacity = MaxElements ;
MakeEmpty(S) ;
}

void MakeEmpty(Stack S)
{
S->TopOfStack = EmptyTOS ;
}

释放栈函数

1
2
3
4
5
6
7
8
void DisposeStack(Stack S)
{
if(S != NULL)
{
free(S->Array) ;
free(S) ;
}
}

检测空栈函数

1
2
3
4
void IsEmpty(Stack S)
{
return S->TopOfStack == EmptyTOS ;
}

释放栈函数

1
2
3
4
5
6
7
8
void Dispose(Stack S)
{
if(S != NULL)
{
free(S->Array) ;
free(S) ;
}
}

压栈函数

1
2
3
4
5
6
7
void Push(ElementType X, Stack S)
{
if(IsFull(S))
Error("栈满了") ;
else
S->Array[++S->TopOfStack] = X ;
}

返回栈顶函数

1
2
3
4
5
6
7
ElementType Top(Stack S)
{
if(!IsEmpty(S))
return S->Array[S->TopOfStack]
Error("空栈") ;
return 0 ;
}

出栈函数

1
2
3
4
5
6
7
void Pop(Stack S)
{
if(IsEmpty(S))
Error("空栈") ;
S->TopOfStack-- ;

}

栈的应用

  • 平衡符号
    1. 后缀表达式
    2. 中缀表达式->后缀表达式
    3. 函数调用

队列模型

  • Enqueue入队 在表的末端插入一个元素
  • Dequeue出队 返回或者删除表的开头的元素
  • FIFO先进先出

队列的实现

数组实现

注意问题:数组浪费为题

解决:循环数组

队列的类型声明

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
struct QueueRecord ;
typedef struct QueueRecord *Queue ;

int IsEmpty(Queue Q) ;
int IsFull(Queue Q) ;
Stack CreateQueue(int MaxElements) ;
void DisposeQueue Q(Queue Q) ;
void MakeEmpty(Queue Q) ;
void Enqueue(ElementType X,Queue Q) ;
ElementType Front(Queue Q) ;
void Dequeue(Queue Q) ;
ElementType FrontAndQueue(Queue Q) ;

#define MinQueueSize(5) ;

Struct QueueRecord
{
int capacity ;
int Front ;
int Rear ;
int Size ;
ElementType *Array ;
}

检测队列是否为空和构造空队列

1
2
3
4
5
6
7
8
9
10
11
void IsEmpty(Queue Q)
{
return Q->Size == 0 ;
}

void MakeEmpty(Queue Q)
{
Q->Size = 0 ;
Q->Front = 1 ;
Q->Rear = 0 ;
}

Eequeue入队函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void Enqueue(ElementType X, Queue Q)
{
if(IsFull(Q)
Error("队列已满") ;
Q->Size++ ;
Q->Rear = Succ(Q->Rear,Q) ;
Q->Array[Q->Rear] = X ;
}

int Succ(int Value, Queue Q)
{
if(++Value == Q->Capacity)
Value = 0 ;
return Value ;
}

Dequeue出队函数

1
2
3
4
5
6
7
8
9
10
ElementType Dequeue(Queue Q)
{
ElementType Tmp ;
if(Q->Rear < Q->Front)
Error("队列为空") ;
Q->Size++ ;
Tmp = Q->Array[Q->Front] ;
Q->Front = Succ(Q->Front,Q) ;
return Tmp ;
}

总结

  • 栈和队列都属于表的一种,只是支持更特殊的操作而已
  • 且用途广泛