三要素:
栈和队列都是操作受限的线性表。
栈是只允许在一端进行插入或删除操作的线性表。
进栈顺序:
\[a_1->a_2->a_3->a_4->a_5 \]出栈顺序:
\[a_5->a_4->a_3->a_2->a_1 \]后进先出,Last In First OUT(LIFO)
InitStack(&S)
:初始化栈。构造一个空栈 \(S\),分配内存空间。DestroyStack(&S)
:销毁栈。销毁并释放栈 \(S\) 所占用的内存空间。Push(&S, x)
:进栈。若栈 \(S\) 未满,则将 \(x\) 加入使之成为新栈顶。Pop(&S, &x)
:出栈,若栈 \(S\) 非空,则弹出栈顶元素,并用 \(x\) 返回。GetTop(S, &x)
:读栈顶元素。若栈 \(S\) 非空,则用 \(x\) 返回栈顶元素。StackEmpty(S)
:判断一个栈 \(S\) 是否为空。若 \(S\) 为空,则返回 true
,否则返回 false
。\(n\) 个不同的元素进栈,出栈元素的不同排列的个数为:
\[\frac{1}{n+1} C^{n}_{2n} \]上述公式称为 卡特兰(Catalan)数。可采用数学归纳法证明(不要求掌握)。
\[\frac{1}{5+1} C^{5}_{10} =\frac{10 \times 9 \times 8 \times 7 \times 6}{6 \times 5 \times 4 \times 3 \times 2 \times 1} =42 \]用顺序存储方式实现的栈。
#define MaxSize 10 typedef struct { ElemType data[MaxSize]; int top; // 栈顶指针 } SqStack;
\(MaxSize*sizeof(ElemType)+4B\)
// 初始化栈 void InitStack(SqStack &S) { S.top = -1; }
// 判断栈空 bool StackEmpty(SqStack S) { return S.top == -1; }
// 判断栈满 bool StackFull(SqStack S) { return S.top == MaxSize - 1; }
// 进栈 bool Push(SqStack &S, int x) { if (StackFull(S)) { return false; } // S.top++; // S.data[S.top] = x; S.data[++S.top] = x; return true; }
// 出栈,数据还残留在内存中,只是逻辑上被删除了 bool Pop(SqStack &S, int &x) { if (StackEmpty(S)) { return false; } // x = S.data[S.top]; // S.top--; x = S.data[S.top--]; return true; }
// 读取栈顶元素 bool GetTop(SqStack &S, int &x) { if (StackEmpty(S)) { return false; } x = S.data[S.top]; return true; }
// 初始化栈 void InitStack(SqStack &S) { S.top = 0; }
// 判断栈空 bool StackEmpty(SqStack S) { return S.top == 0; }
// 判断栈满 bool StackFull(SqStack S) { return S.top == MaxSize; }
栈的大小不可改变。
两个栈共享同一片内存空间,两个栈从两边往中间增长。
#define MaxSize 10 typedef struct { ElemType data[MaxSize]; int top0; int top1; } ShStack;
// 初始化共享栈 void InitStack(ShStack &S) { S.top0 = -1; S.top1 = MaxSize; }
// 判断栈满 bool StackFull(ShStack S) { return S.top0 + 1 == S.top1; }
typedef struct LNode { ElemType data; struct LNode *next; } LNode, *LinkStack;
// 初始化一个链栈,带头结点 bool InitStack(LinkStack &S) { S = (LNode *)malloc(sizeof(LNode)); if (S == NULL) { return false; } S->next = NULL; return true; }
// 判断栈空 bool StackEmpty(LinkStack S) { return S->next == NULL; }
// 进栈 bool Push(LinkStack &S, int x) { LNode *s = (LNode *)malloc(sizeof(LNode)); s->data = x; s->next = S->next; S->next = s; return true; }
// 出栈 bool Pop(LinkStack &S, int &x) { if (StackEmpty(S)) { return false; } LNode *q = S->next; x = q->data; S->next = q->next; free(q); return true; }
// 读取栈顶元素 bool GetTop(LinkStack &S, int &x) { if (StackEmpty(S)) { return false; } x = S->next->data; return true; }