考研数据结构与算法（三）栈和队列

一、栈

栈是一种 后进先出（LIFO） 的线性结构，只允许在一端进行插入和删除等操作的线性结构

这个结构最重要的两个操作便是：push 和pop 因为其分别对应的是往结构中加入新元素以及删除结构中的元素，又由于栈的这个结构，这两个操作一般都是在栈顶做的操作，也如上图所示

也正是由于这两个操作，使得栈有一个出栈排列顺序的数据结构：

n n n 个不同元素进栈，出栈元素不同排列的个数为 C 2 n n n + 1 \frac{C^n_{2n}}{n+1} n+1C2nn​​ 这个公式也被称为卡特兰数

说完了最重要的两个操作，我们接着来说栈的一些基本的操作（以严蔚敏老师的教材为例）

函数名操作InitStack(&S)初始化栈StackEmpty(S)判断栈是否为空Push(&S,x)入栈、若栈未满往栈 S S S 中放入元素 x x xPop(&S,x)出栈、若栈未空将栈顶元素弹出GetTop(&S,&x)若栈为空则将栈顶元素的值赋给 x x xDestroyStack(&S)销毁栈，并释放栈所用的空间 1.1 顺序栈

采用顺序存储的栈称为顺序栈（简单理解为用数组实现的），它通过一组地址连续的空间实现了栈这种先进后出的数据结构，一般这样的数据结构可以描述为：

#define MaxSize 100
struct Stack{
    Elemtype data[MaxSize];
    int top;
}S;

其中 data 数组表示的是栈的空间，而 top 表示的是栈顶的位置，通常来说栈顶的位置初始时（栈为空的时候）设置为 − 1 -1 −1 ，当然也有设置为 0 0 0 的，我们来讲若栈空设置为 − 1 -1 −1 的情况：

• 进栈：若栈不满，则先将栈顶指针top加 1 1 1 再将元素放入当前的位置
• 出栈：若栈不空，则当前元素指向的就是栈顶位置，先将当前元素赋给其他变量，再将栈顶指针top减 1 1 1
• 栈空：若栈为空，则栈顶指针top的值为 − 1 -1 −1

同理不难得到若栈空设置为 0 0 0 的情况：

• 进栈：若栈不满，则先将元素放入当前的位置再将栈顶指针top加 1 1 1
• 出栈：若栈不空，则当前元素指向的就是栈顶的下一个位置，先将栈顶指针top减 1 1 1 ，再将当前元素赋给其他变量
• 栈空：若栈为空，则栈顶元素指针top 的值为 0 0 0

其实当栈顶指针初始化为 − 1 -1 −1 则 top 代表的含义就是当前指向的位置就是栈顶的位置，而初始化为 0 0 0 则代表的含义是当前位置是栈顶位置的下一个位置。

1.1.1 顺序栈代码实现 1.1.1.1 初始化

将 top 指针归位即可，即置为 − 1 -1 −1

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

1.1.1.2 判栈空

只需要判断 top 指针是否指向 − 1 -1 −1

bool StackEmpty(struct Stack S) {
    return S.top == -1;
}

1.1.1.3 进栈

按照上面分析的，如果栈未满，则先将指针往后移动一位，然后将新元素放入

bool Push(struct Stack &S,Elemtype x) {
    if(S.top == MaxSize - 1) return false;//如果栈未满
    S.data[++S.top] = x;
    return true;
}

1.1.1.4 出栈

按照上面分析的，如果栈未空，先取出当前栈顶的元素，然后 top 指针往前移动一位

bool Pop(struct Stack &S,Elemtype &x) {
    if(S.top == -1) return false;//如果栈未空
    x = S.data[S.top--];
    return true;
}

1.1.1.5 读栈顶元素

如果栈没空，则将栈顶元素复制给元素 x x x

bool GetTop(struct Stack &S,&x) {
    if(S.top == -1) return false;
    x = S.data[S.top];
    return true;
}

1.2 链栈

由于顺序结构这种数据结构在空间的拓展上非常的麻烦或者有限，不好分配栈的大小，那么链栈则成为了便于扩展空间的结构，那么其实和链表的操作并无太大差别，若我们用 头插法 ，则栈顶元素就是头结点元素，而其他具体的操作如下：

• 进栈：将新的元素通过头插法插入链表中即可，此时头结点元素即为栈顶元素
• 出栈：如果栈不为空，将头节点元素删除即为出栈操作
• 栈空：我们只需要判断头指针的next直至，如果指向NULL则表示栈为空，否则表示栈中有元素

1.2.1 链栈的代码实现

由于我们之前学习过链表的基本操作，那么我这里就直接使用之前实现的函数了

typedef struct Stack_Node{
    ElemType data;//数据域
    struct Stack_Node *next;//指针域
}Node;

1.2.1.1 初始化

从前往后遍历链表，并且将链表空间释放，最后将链表的头指针指向 NULL

void InitStack(Node *S) {
    Node *p = S;
    while(p->next) {
        Node *t = p->next;
        p = t->next;
        free(t);
    }
    S->next = NULL
}

1.2.1.2 判栈空

看头指针指向的结点是否为空

void InitStack(Node *S) {
    return S->next == NULL;
}

1.2.1.3 进栈

头部插入元素即可

bool Push(Node *S,Elemtype x) {
    Node *t = (Node *)malloc(sizeof(Node));
    t->data = x;
    t->next = S->next;
    S->next = t;
    return true;
}

1.2.1.4 出栈

将头节点删除即可

bool Pop(Node *S) {
    if(S->next == NULL) return false;
    Node *t = S->next;
    S->next = t->next;
    free(t);
    return true;
}

1.2.1.5 读取栈顶元素

如果栈不为空，那么就将栈顶元素赋值给 x

bool GetTop(Node *S,&x) {
    if(S->next == NULL) return false;
    x = S->next->data;
    return true;
}

1.3 共享栈

因为栈底的位置不会发生改变，那么对于一个线性结构又是有两个方向的，那么我们两个方向分别作为栈底往中心靠齐则能提高一块空间的利用率，这其实就是共享栈，此时的共享栈需要设置top0 和 top1 分别表示两个方向的栈顶，那么此时的一些满栈和空栈的判断就发生了改变

当栈满时，即为：top1 - top0 == 1

当左栈空时，即为： top0 == -1

当右栈空时，即为： top1 == Maxsize

那么入栈和出栈的操作就不列举啦，和之前顺序栈一样的

具体结构如下图所示：

1.4 实际应用 1.4.1 进制转化

例如十进制转 x x x 进制，我们需要对当前的十进制不断取余，最后将这些余数倒序连接则成为了转换后的位数，这里为了方便简单实现一下

void conversion(int k,int x) {
    stack S;
    while(k) {
        S.push(k % x);
        k /= x;
    }
    while(!S.empty()) {
        printf("%d",S.top());
        S.pop();
    }
}

1.4.2 括号匹配

如果栈不为空，那么我们就将当前的元素和栈顶元素进行判断是否构成一个匹配，如果不构成那么就将当前元素放入栈中，继续等待下一个，如果发现匹配则将当前的栈顶元素出栈操作，并且不讲当前的元素放入栈中，因为其构成了一个匹配，最后如果我们发现栈中还有元素则说明括号不能匹配，假设这里只有一种括号( 和)

bool check(string str) {
    stack S;
    for(int i = 0,l = str.size();i  str;
	for (int i = 0; i = '0' && str[i]