栈是一种先进后出的数据结构

基本概念

定义
只允许在一端进行插入或删除操作的线性表

栈顶（Top）：线性表允许进行插入和删除的一端。
栈底（Bottom）：固定的，不允许进行插入和删除的另一端。
空栈：不含任何元素。

基本操作

s.empty() 返回栈是否为空
s.size() 返回栈的元素个数
s.top() 返回栈顶元素
s.pop() 弹出栈顶元素
s.push(x) 将 x 压入栈中

顺序存储结构

顺序栈

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
//初始化
void InitStack(SqStack& S)
{
    S.top = -1;             //初始化栈顶指针
}
//判栈空
bool StackEmpty(SqStack& S)
{
    if( S.top == -1)
    {
        return true;
    }
    return false;
}
//进栈
bool Push(SqStack& S, ElemType x)
{
    if( S.top == MAXSIZE - 1 )//栈满，报错
    { 
        return false;        
    }
    S.top ++ ;                  //栈顶指针加1
    S.data[S.top] = x;          //入栈
    return true;
}
//出栈
bool Pop(SqStack& S, ElemType& x)
{
    if( S.top == -1 )//栈空，报错
    {          
        return false;
    }
    x = S.data[S.top];
    S.top --;
    return true;
}
//读栈顶元素
bool GetTop(SqStack& S,ElemType& x)
{
    if( S.top == -1 )//栈空，报错
    {          
        return false;
    }
    x = S.data[S.top];
    return true;
}

共享栈

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

两个栈的栈顶指针都指向栈顶元素，top1 = -1 时，stack1 为空，top2 = MAXSIZE 时，stack2 为空；
仅当两个栈顶指针相邻(top2 - top1 == 1)时，判断栈满。
当stack1进栈时top1先加1再赋值，stack2进栈时top2先减1再赋值；出栈正好相反。

共享栈是为了更有效地利用存储空间，两个栈的空间正好互相调节，只有在整个存储空间被占满时才发生上溢。存取数据的时间复杂度均为O(1)，所以对存取效率没有什么影响。

链式存储结构

链栈

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

应用

递归

四则运算表达式求值