了解一下栈结构

数据结构

栈

本文部分截图来自王道考研
书籍参考：[1]王晓东.数据结构（语言描述）[M].北京：电子工业出版社.2019前言

前言

栈是一种特殊的表，这种表只能在表首进行插入和删除。所以表首对于栈有特殊意义，称为栈顶，表尾称为栈底，不含任何元素的栈称为空栈。可以简单的来说，栈的修改是按后进先出的原则进行，又称为后进先出（Last In First Out）表，简称LIFO表。

假设一个栈$S$中的元素为$a(n),a(n-1),…,a(1)$，则称$a(1)$为栈底元素，$a(n)$为栈顶元素。栈中元素按照$a(1),a(2)…,a(n)$的顺序进栈，第一个进栈的是$a(1)$，接着依次往后，任何时候，出栈的都是栈顶元素$a(n)$。当$n$个不同的元素进栈，出栈元素不同排列的个数则为
$$
\frac{1}{n+1}C_{2n}^n
$$
这个公式称为卡特兰（Catalan）数

  • InitStack(&S)：初始化栈，构造一个空栈$S$，分配内存空间。
  • StackFree(&S)`：销毁栈，销毁并释放栈$S$所占用的内存空间
  • Push(&S,x)：进栈，若栈$S$未满，则将$x$加入使之成为新栈顶。
  • Pop(&S,&x)：出栈，若栈$S$非空，则弹出栈顶元素，并用$x$返回。
  • StackTop(&S,&x)：读入栈顶元素，若栈$S$非空，则用$x$返回栈顶元素
  • StackEmpty(&S)：判断一个栈$S$是否为空，若$S$为空，则返回True，否则False

栈的顺序存储

栈是一个特殊的表，所以可以使用数组来实现栈，用一个数组data存储栈元素，栈底固定在数组的底部，即data[0]为最早的入栈元素

  • 代码实现
栈的顺序存储实现
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
// 栈-顺序存储
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

typedef struct astack{
    int top, //栈顶
        maxtop; // 栈空间上界
    int *data; // 存储栈元素的数组
}Astack;

typedef struct astack *Stack; //栈指针类型

Stack StackInit(int size){
    Stack S = (Stack)malloc(sizeof(*S)); // 创建一个空栈
    S->data = (int *)malloc(size*sizeof(int)); //为存储栈元素的数组分配内存空间
    S->maxtop = size; // 栈空间上限为size
    S->top = -1; // 初始化栈顶指针
    return S;
}

void testStack(){
    Stack S;
    S = StackInit(10);
}

int main(){
    testStack();

    return 0;
}

创建一个size大小的栈，因为刚开始的时候，data[0]还没存放数据，所以S->top初始化不能等于$0$，令它等于$-1$

栈顺序存储的基本操作

判断非空

1
2
3
4
5
int StackEmpty(Stack S){
    /* 是否为空栈 */
    return S->top < 0; // 如果栈顶小于0，证明还没存储元素
}

进栈操作

1
2
3
4
5
6
7
8
9
void Push(Stack S, int x){
    /* 进栈操作 */
    if (StackFull(S)){
        // 判断是否栈满
        exit(1);
    }
    S->top = S->top+1; // 栈顶加1
    S->data[S->top] = x; // 添加一个元素
}

先判断栈顶指针是否已经达到了栈的最大容量，如果是返回False。因为入栈了一个元素，所以栈顶指针加1，再令当前栈顶指针的位置等于插入元素$x$。

出栈操作

1
2
3
4
5
6
7
8
9
int Pop(Stack S){
    /* 出栈操作 */
    if(StackEmpty(S)){
        exit(1);
    }
    int x = S->data[S->top]; //返回出栈的元素
    S->top = S->top-1; // 栈顶减一
    return x;
}

令栈顶指针top减去一位，使得逻辑上进行一个出栈操作，但实际数据还是遗留在内存中。

读栈顶元素

1
2
3
4
5
6
7
int StackTop(Stack S){
    /* 读取栈顶 */
    if (StackEmpty(S)){
        exit(1);
    }
    return S->data[S->top];
}

因为数组是动态分配的，所以需要写一个释放内存的函数

1
2
3
4
void StackFree(Stack S){
    free(S->data);
    free(S);
}

打印栈

1
2
3
4
5
6
7
void StackPrint(Stack S){
    /* 打印栈 */
    for (int i=S->top; i>=0; i--){
        // 因为栈后进先出，所以要从栈顶开始打印，一直到栈底
        printf("%d\n",S->data[i]);
    }
}

在同时使用过多个栈的情况，为了不会栈溢出，通常要给栈分配一个较大的栈空间，但是各个栈在算法运行中，所使用的最大空间很难估计。所以可以使用共享栈来提高栈空间的利用率。

例如两个栈使用同一个数组data[0:n]，那么利用栈底不变的特性，一个栈底设为0，另一个栈底设为n，分别各自往数组中间延申。这样每一个栈最大的可用空间为$\frac{n}{2}$。

栈的链式存储

如果要用到多个栈的时候，可以使用链表作为栈的存储结构，也就是栈的链式存储，就是用指针来实现栈。这样方式使栈有着动态大小，这种实现方式也被称为链栈

  • 代码实现
栈的链式存储实现
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
// 栈-链式存储
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef struct snode{ // 栈结构
    int data; // 栈元素
    struct snode *next; // 下一结点指针
}StackNode;

typedef StackNode *SLink; // 栈结点指针类型

typedef struct lstack{ // 栈结构
    SLink top; // 栈顶指针
}Lstack;

typedef Lstack *Stack;

SLink NewStackNode(){
    /* 创建新结点 */
    return (SLink)malloc(sizeof(StackNode));
}

Stack StackInit(){
    /* 初始化栈 */
    Stack S = (Stack)malloc(sizeof(*S));
    S->top = NULL; // top置为空指针
    return S;
}

void testStack(){
    Stack S;
    S = StackInit();
}

int main(){
    testStack();
    return 0;
}

首先创建一个栈结点的类型，data存储栈元素，next指向下一个结点的指针。使用typedef创建一个snode类型的栈结点指针类型SLink。

再创建一个链栈Stack，其中结构只有一个栈顶指针，其指针的类型是栈结点指针类型SLink。

栈链式存储的基本操作

判断非空

1
2
3
4
int StackEmpty(Stack S){
    /* 判断释放为空栈 */
    return S->top == NULL;
}

进栈操作

1
2
3
4
5
6
void Push(Stack S, int x){
    SLink p = NewStackNode(); // 申请一个结点的内存空间
    p->data = x; // 将栈元素存入
    p->next = S->top; // 将新结点的下一个结点指针置空
    S->top = p; // 栈顶结点下一个为p，使p为新的栈顶
}

为新结点申请一块内存空间，同时类型设置为栈结点指针类型，将元素x存入data中，将新结点的下一个结点置为top的下一个结点。因为top的下一个结点是NULL，所以此时结点p的下一个结点也为NULL。这时结点p为栈的栈顶。

出栈操作

1
2
3
4
5
6
7
8
9
10
11
12
int Pop(Stack S){
    /* 出栈操作 */
    if (StackEmpty(S)){
        // 判断栈是否为空栈
        exit(1);
    }
    int x = S->top->data; // 返回出栈元素
    SLink p = S->top; // 另p等于栈顶指针
    S->top = p->next; // 将栈顶指针top，指向p的下一个结点。
    free(p); // 释放p
    return x;
}

假设栈内结点为$k->q->s->Null$，这时执行出栈操作，这时候的栈顶为$s$，定义一个变量$x$，另它等于栈顶的data，将出栈元素赋值给x，再函数的结尾处返回。定义一个栈指针类型的结点$p$，另它等于栈顶，所以这个时候栈内就变成这样$k->q->p->Null$。将栈顶指向$p$的下一个结点，也就是$Null$,$k->q->NULL$，最后将$p$占用的结点内存释放。

读栈顶元素

1
2
3
4
5
6
7
int StackTop(Stack S){
    /* 读取栈顶元素 */
    if (StackEmpty(S)){
        exit(1);
    }
    return S->top->data;
}

打印栈

1
2
3
4
5
6
7
8
9
10
11
12
13
int StackPrint(Stack S){
    /* 打印栈 */
    if (StackEmpty(S)){
        // 判断非空
        exit(1);
    }
    SLink p = NewStackNode(); // 创建一个结点
    p = S->top; // 令p等于栈顶结点
    while (p!=NULL){
        printf("%d\n",p->data); // 
        p = p->next;
    }
}