栈：顺序栈和链式栈

    前面已经介绍了“链表”，包括顺序链表和链式链表。链表和栈都属于线性表，只是栈是一种特殊的线性表，其“只能够从一端（栈顶）进出”，必须遵循“先进后出”的原则。下面，我们简要学习一下顺序栈和链式栈。

（1）顺序栈

        与顺序存储的链表一样，顺序栈也是采用“数组”来存储。其数据结构如下：

[cpp]  view plain copy

1. #define MAXSIZE 20  
2. typedef int Elemtype;  
3. typedef struct  
4. {  
5.      Elemtype data[MAXSIZE];  
6.      int top;  
7. }sqStack;  

        这里我们看出，栈和链表的数据结构几乎一模一样，只是里面的成员含义不同而已。在顺序链表里面，定义的是一个长度length，表示所能够存储的最大数据的个数，这个值是不能变化的；而顺序栈中定义的是栈顶元素的下标，这个值可以变化。

       对于栈的操作来说，最重要的是“入栈”和“出栈”。这两个操作都必须遵循“FILO”的原则，其具体实现如下：

[cpp]  view plain copy

1. //入栈  
2. bool Push(sqStack *S, Elemtype e)  
3. {  
4.       if(S->top >= MAXSIZE - 1)  
5.                 return false;  
6.       S->top++;    //要细心，不能单独用top，而是引用结构体中的元素  
7.       S->data[s->top] = e;  
8.       return true;  
9. }  
10. //出栈  
11. bool Pop(sqStack *S, Elemtype *e)  
12. {  
13.       if(S->top == 0)  
14.              return false;  
15.        *e = S->data[S->top];  
16.        S->top--;  
17.        return true;  
18. }  

        从上面的知识中，可以知道，顺序栈的操作很方便，但其最大的不足在于，必须事先确定数据存储的最大空间。这里，我们扩展一下知识，下面介绍一下如何做到两个顺序栈共享数据空间。这个方法的基本思想为：数组空间有两个端点，两个栈有两个栈底；让一个栈的栈底位于数组的起始端（下标为0处），让另一个栈的栈底位于数组的末端（下标为N-1处）；如果要向栈里面添加元素，那么使栈顶向数组中间移动即可。

数据结构如下：

[cpp]  view plain copy

1. typedef struct   
2. {  
3.       Elemtype data[MAXSIZE];  
4.       int top1;  
5.       int top2;  
6. }sqDoubleStack;  

入栈操作：

[cpp]  view plain copy

1. bool Push(sqDoubleStack *S, Elemtype e, int stackNumber)  
2. {  
3.       if(S->top1+1 == S->top2)//特别注意，如果栈满了，top1和top2不是相等的，而是两者前后相邻，因此要加1  
4.            return false;  
5.       if(stackNumber == 1)  
6.       {  
7.               S->top1++;  
8.               S->data[S->top1] = e;  
9.               return true;  
10.       }    
11.       if(stackNumber == 2)  
12.       {  
13.               S->top2++;  
14.               S->data[S->top2] = e;  
15.               return true;  
16.       }      
17. }  

（2）链式栈

        链式存储的栈就不会存在“栈满”的现象。因此，在进行入栈、出栈的时候，就不用再判断是否满栈了。在对链式栈进行操作时，始终要把握一点：首先看到的是整个栈，而不每一个结点；对于整个栈，只有两个指标——栈顶指针（top）和栈元素个数（count）；这样，我们就能够通过栈顶指针（top）来取到栈顶的一个结点，从而获取其中的数据data，并可以创建指针，移动指针位置，遍历栈中的各个元素。也就是说，我们必须“从栈（top、count），再到结点（data、next）”。

其数据解结构可以定义为：

[cpp]  view plain copy

1. typedef struct StackNode  
2. {  
3.      Elemtype data;  
4.      struct StackNode * next;  
5. }StackNode, *LinkStackPtr;  
6. typedef struct LinkStack  
7. {  
8.      LinkStackPtr top;//这里top是一个stack结点类型的指针，指向Stack结点（栈顶）  
9.      int count;  
10. }LinkStack;  

入栈操作：

[cpp]  view plain copy

1. bool Push(LinkStack *S, Elemtype e)  
2. {  
3.       LinkStackPtr tmp = (LinkStackPtr)malloc(sizeof(StackNode));  
4.       tmp->data = e;  
5.       tmp->next = S->top;  
6.       S->top = tmp;  
7.       S->count++;  
8.        return true;  
9. }  

出栈操作：

[cpp]  view plain copy

1. bool Pop(LinkStack *S, Elemtype *e)  
2. {  
3.       LinkStack p;  
4.       *e = S->top->data;  
5.       p = S->top;  
6.       S->top = S->top->next;  
7.       free(p);  
8.       S->count--:  
9.       return true;  
10. }