1. 栈的定义#

栈(Stack)是仅允许在一端进行插入和删除操作的线性表。作为一种特殊的线性表，栈的插入(入栈)和删除(出栈)操作被限制在表的一端进行。

栈顶(Top)：允许进行插入和删除操作的一端。

栈底(Bottom)：固定不变、不允许进行插入和删除操作的另一端。

空栈：不含任何元素的栈。

假设某栈 $S=(a_{1}, a_{2}, a_{3}, a_{4}, a_{5})$，其中 $a_{1}$ 为栈底元素，$a_{5}$ 为栈顶元素。栈的入栈和出栈操作只能在栈顶进行。若元素按顺序 $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)。

NOTE

每接触一种新的数据结构，都应从其逻辑结构、存储结构和基本运算三方面进行系统理解。

2. 栈的基本操作#

不同教材对基本操作的命名略有差异，但含义基本一致，本文采用严蔚敏教材的命名规范。

• InitStack(&S): 初始化一个空栈 S。
• StackEmpty(S)：判断栈是否为空。若栈 S 为空，返回 true；否则返回 false。
• Push(&S,x): 入栈操作；若栈未满，则x成为新的栈顶元素。
• Pop(&S,&x)：出栈操作；若栈非空，则弹出栈顶元素，并通过x返回该值。
• GetTop(S, &x)：读取栈顶元素但不出栈；若栈非空，则通过 x 返回栈顶元素。
• DestroyStack(&S)：销毁栈 S，并释放其所占用的存储空间(&表示引用调用)。

在解答算法题时，若题目未作特殊限制，可直接使用上述基本操作函数。

栈的数学性质：当 n 个不同元素按固定次序入栈时，可能的出栈序列总数为 $\frac{1}{n+1}C_{2n}^{n}$。该数列称为卡特兰(Catalan)数，可通过数学归纳法证明，有兴趣的读者可参考组合数学教材。

1. 顺序栈的实现#

采用顺序存储的栈称为顺序栈，它利用一组地址连续的存储单元存放从栈底到栈顶的数据元素，并附设一个整型指针(top)指示当前栈顶元素的位置。

顺序栈的类型可定义如下

1
#define MaxSize 50          //定义栈中元素的最大个数
2
typedef struct{
3
    Elemtype data[MaxSize]; //存放栈中元素
4
    int top;                //栈顶指针
5
}SqStack;

栈顶指针：S.top，初始时设为 S.top=-1；栈顶元素：S.data[S.top]。

入栈操作：当栈未满时，先将栈顶指针加1，再将元素存入栈顶。

出栈操作：当栈非空时，先取出栈顶元素，再将栈顶指针减1。

栈空条件：S.top==-1；栈满条件：S.top==MaxSize-1；栈长：S.top+1。

另一种常见的方式是：栈顶指针初始化为 $S.top=0$；入栈时先将元素存入栈顶，再将栈顶指针加 1；出栈时先将栈顶指针减 1，再取出栈顶元素；栈空条件为 $S.top==0$；栈满条件为 S.top==MaxSize。

顺序栈的入栈操作受数组上界约束。若对栈的最大使用空间估计不足，则可能发生栈上溢，此时，应向用户报告错误信息，以便及时处理，避免程序异常。

NOTE

栈和队列的判空、判满条件，会因实际给出的条件不同而变化，下面的代码实现是在栈顶指针初始化为-1的条件下的相应方法，而其他情况则需具体问题具体分析。

2. 顺序栈的基本操作#

栈顶指针的作用：它标识了栈中有效元素的边界。

以下是顺序栈常用基本操作的实现(基于 top=-1 初始化)。

(1) 初始化

1
void InitStack(SqStack &S) {
2
    S.top=-1;   //初始化栈顶指针
3
}

(2) 判栈空

1
bool StackEmpty(SqStack S){
2
    if(S.top==-1)   //栈空
3
        return true;
4
    else            //不空
5
    return false;
6
}

(3) 入栈

1
bool Push(SqStack &S,ElemType x){
2
    if(S.top==MaxSize-1)    //栈满，报错
3
        return false;
4
    S.data[++S.top]=x;      //指针先加1，再入栈
5
    return true;
6
}

(4) 出栈

1
bool Pop(SqStack &S,ElemType &x){
2
    if(S.top==-1)       //栈空，报错
3
        return false;
4
    x=S.data[S.top--];  //先出栈，指针再减1
5
    return true;
6
}

(5) 读栈顶元素

1
bool GetTop(SqStack S,ElemType &x){
2
    if(S.top==-1)       //栈空，报错
3
        return false;
4
    x=S.data[S.top];    //x记录栈顶元素
5
    return true;
6
}

该操作不改变栈的状态，栈顶元素依然保留在栈中。

NOTE

此处，top指向栈顶元素本身。因此入栈为S.data[++S.top]=x，出栈为x=S.data[S.top—]。若top初始化为0(指向栈顶元素的下一个位置)，则入栈变为S.data[S.top++]=x，出栈变为x=S.data[—S.top]，相应的判空、判满条件也随之改变。请读者仔细体会差异，做题时务必根据题目设定灵活应对。

3. 共享栈#

利用栈底位置相对固定的特性，可让两个顺序栈共享同一段一维数组空间，将两个栈的栈底分别置于数组两端，栈顶向中间延伸。

0号栈栈顶指针为top0，1号栈栈顶指针为top1，均指向各自的栈顶元素；初始时top0=-1(0号栈空)，top1=MaxSize(1号栈空)；栈满条件为top1-top0==1(两栈顶相邻)。当0号栈入栈时，top0先加1，再赋值；当1号栈入栈时，top1先减1，再赋值；出栈操作的顺序相反。

共享栈能更高效地利用存储空间，两个栈的空间可动态调节，仅当整个数组被占满时，才发生栈溢出。其存取数据的时间复杂度均为 $O(1)$，对存取效率无影响。