数据结构：栈的基本概念、顺序栈、共享栈以及链栈

相关概念

栈(Stack)是只允许在一端进行插入或删除操作的线性表。
栈顶(Top)：线性表允许插入删除的那一端。
栈底(Bottom)：固定的，不允许进行插入和删除的另一端。
栈的基本操作

• InitStack(&S)：初始化一个空栈S。
  
• StackEmpty(S)：判断一个栈是否为空，若栈S为空则返回true，否则返回false。
  
• Push(&S,x)：进栈，若栈S未满，则将x加入使之成为新栈顶。
  
• Pop(&S,&x)：出栈，若栈S非空，则弹出栈顶元素，并用x返回。
  
• GetTop(S,&x)：读栈顶元素，但不出栈，若栈S非空，则用X返回栈顶元素。
  
• DestoryStack(&S)：销毁栈，并释放栈S所占用的存储空间。
  

栈的数学性质：当\(n\)个不同元素进栈时，出栈元素的不同排列的个数为\(C^n_{2n}/(n+1)\)。该公式称为卡特兰数(Catalan)公式，可采用数学归纳法证明。
顺序栈

采用顺序存储的栈称为顺序栈，它利用一组地址连续的存储单元存放自栈底到栈顶的数据元素，同时附设一个指针（top）指示当前栈顶元素的位置。

栈和队列的判空、判满条件，会因实际给的条件不同而变化；具体来说，有时候将空栈时栈顶指针初始化为-1，有时候将空栈时栈顶指针初始化为0.

1. #define MaxSize 50
2. typedef int Elemtype;
4. typedef struct {
5.         Elemtype data[MaxSize];
6.         int top;
7. } SqStack;
10. void InitStack(SqStack& S) {
11.         S.top = -1;
12. }
14. bool StackEmpty(SqStack S) {
15.         if (S.top = -1)
16.                 return true;
17.         else
18.                 return false;
19. }
21. bool Push(SqStack& S, Elemtype x) {
22.         if (S.top == MaxSize - 1)
23.                 return false;
24.         S.data[++S.top] = x;
25.         return true;
26. }
28. bool Pop(SqStack& S, Elemtype& x) {
29.         if (S.top == -1)
30.                 return false;
31.         x = S.data[S.top--];
32.         return true;
33. }
35. bool GetTop(SqStack& S, Elemtype& x) {
36.         if (S.top == -1)
37.                 return false;
38.         x = S.data[S.top];
39.         return true;
40. }

复制代码

共享栈

利用栈底位置相对不变的特性，可让两个顺序栈共享一个一维数组空间，将两个栈的栈底分别设置在共享空间的两端，两个栈底向共享空间的中间延伸。
两个栈的栈顶指针都指向栈顶元素，top=-1时0号栈为空，top=MaxSize时1号栈为空；仅当两个栈顶指针相邻（top1-top0=1）时，判断为栈满。

1. #define MaxSize 50
2. typedef int Elemtype;
4. typedef struct {
5.         Elemtype data[MaxSize];
6.         int top1;
7.         int top2;
8. } SqStack;
11. void InitStack(SqStack& S) {
12.         S.top1 = -1;
13.         S.top2 = MaxSize;
14. }

复制代码

链栈

采用链式存储的栈称为链栈，链栈的优点是便于多个栈共享存储空间和提高其效率，且不存在栈满上溢的情况。通常采用单链表实现，并规定所有的操作都是在单链表的表头进行的。一般规定链栈没有头结点，Lhead指向栈顶元素。

添加头结点对链栈的实现没有帮助，因此一般不设置头结点。

1. #include <cstdlib>
3. typedef int Elemtype;
5. typedef struct LNode {
6.         Elemtype data;
7.         struct LNode* next;
8. } LNode, *LiStack;
10. void InitStack(LiStack& L) {
11.         L = (LNode*)malloc(sizeof(LNode));        // 创建头节点
12.         L->next = NULL;                                                // 头节点指向空
13.         return;
14. }
16. bool StackEmpty(LiStack L) {
17.         return L->next == NULL;
18. }
20. void Push(LiStack L, Elemtype x) {
21.         LNode* node = (LNode*)malloc(sizeof(LNode));
22.         node->data = x;
23.         node->next = L->next;
24.         L->next = node;
25. }
27. bool Pop(LiStack L, Elemtype& x) {
28.         if (L->next = NULL)
29.                 return false;
30.         LNode* node = L->next;
31.         x = node->data;
32.         L->next = node->next;
33.         free(node);
34.         return true;
35. }
37. bool GetTop(LiStack L, Elemtype& x) {
38.         if (L->next = NULL)
39.                 return false;
40.         x = L->next->data;
41.         return true;
42. }

复制代码

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！