栈

栈的基本概念

栈的定义

• 栈（Stack）：只允许在一端进行插入或删除操作的线性表。首先栈是一种线性表，但限定这种线性表只能在某一端进行插入和删除操作。
• 栈顶（Top）：线性表允许进行插入删除的那一端。
• 栈底（Bottom）：固定的，不允许进行插入和删除的另一端。
• 空栈：不含任何元素的空表。

假设某个栈 #card=math&code=S%20%3D%20%28a%7B1%7D%2Ca_2%2C%20a_3%2Ca_4%2Ca_5%29&id=tnGPn)，则 为栈底元素， 为栈顶元素。由于栈只能在栈顶进行插入和删除操作，进栈次序依次为  而出栈次序为 。由此可见，栈的操作特性可以明显地概括为后进先出（Last In First Out，LIFO）。

栈的数学性质： 个不同元素进栈，出栈元素不同排列的个数为 。上述公式称为卡特兰（Catalan）数，可采用数学归纳法证明。

找的基本操作

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

栈的顺序存储结构

栈是一种操作受限的线性表，类似于线性表，它也有对应的两种存储方式。

顺序栈的实现

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

#define MaxSize 10
typedef struct {
    int data[MaxSize];
    int top;
} SqStack;

• 栈顶指针：S.top，初始时设置 S.top=-1；
• 栈顶元素：S.data[S.top]；
• 进栈操作：栈不满时，栈顶指针先加1，再送值到栈顶元素。
• 出栈操作：栈非空时，先取栈顶元素值，再将栈项指针减 1。
• 栈空条件：S.top==-1；
• 栈满条件：S.top==MaxSize-1
• 栈长：S.top+1

由于顺序栈的入栈操作受数组上界的约束，当对栈的最大使用空间估计不足时，有可能发生栈上溢，此时应及时向用户报告消息，以便及时处理，避免出错。

顺序栈的基本运算

初始化：

void InitStack(SqStack &S){
    S.top = -1;
}

判断栈空：

bool StackEmpty(SqStack S) {
    if (S.top == -1) {
        return true;
    } else {
        return false;
    }
}

进栈：

bool Push(SqStack &S,int x){
    if(S.top == MaxSize-1){
        return false;
    }
    S.data[++S.top] = x;
    return true;
}

当找不满时， top 先加 1，再入栈。

出栈：

bool Pop(SqStack &S,int &x){
    if(S.top == -1){
        return false;
    }
    X = S.data[S.top--];
    return true;
}

读取栈顶元素：

bool Pop(SqStack &S,int &x){
    if(S.top == -1){
        return false;
    }
    X = S.data[S.top];
    return true;
}

注意：这里 top 指向的是栈顶元素，所以进栈操作为 S.data[++S.top]=x，出栈操作为 x=S.data[S.top--]。若栈顶指针初始化为 S.top=0，即 top 指向栈顶元素的下一位置，则入栈操作变为 S.data[S.top++]=x；出栈操作变为 x=S.data[--S.top]。 相应的栈空、栈满条件也会发生变化。

共享栈

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

两个栈的栈顶指针都指向栈顶元素，top0=-1 时 0 号栈为空，top1=MaxSize 时 1 号栈为空；仅当两个栈顶指针相邻（top1-top0=1） 时，判断为栈满。当 0 号栈进栈时 top0 先加1 再赋值，1 号栈进栈时 top1 先减 1 再赋值；出栈时则刚好相反。

共享栈是为了更有效地利用存储空间，两个栈的空间相互调节，只有在整个存储空间被占满时才发生溢。其存取数据的时间复杂度均为 #card=math&code=O%281%29&id=npqzH)，所以对存取效率没有什么影响。

栈的链式存储结构

采用链式存储的栈称为链栈，链栈的优点是便于多个栈共享存储空间和提高其效率，且不存在栈满上溢的情况。通常采用单链表实现，并规定所有操作都是在单链表的表头进行的。拢的链式存储类型可描述为：

typedef struct LinkNode {
    int data;
    struct LinkNode *next;
} *LiStack;

采用链式存储，便于结点的插入与删除。链栈的操作与链表类似，入栈和出栈的操作都在链表的表头进行。需要注意的是，对于带头结点和不带头结点的链栈，具体的实现会有所不同。