数据结构--栈的基本概念与应用_栈有什么特性和应用

​ 栈和队列是两种重要的线性结构。从数据结构的角度看，栈和队列也是线性表，其特特殊在于栈和队列的基本操作是线性表操作的子集，他们是操作受限的线性表，因此，可以称为限定性的数据结构。

​ 但是另一方面，从数据类型角度来看，栈和队列是和线性表大不相同的两类重要的抽象数据类型。并且栈和队列因为其特性，被广泛的应用于各种软件系统中，学习他们对我们有很大的帮助。因此本文除了讨论栈和队列的定义、表示方法和实现外，还将给出一些应用的例子。

​ 由于篇幅的问题，本文先讨论栈，下一文中进行队列的讨论。

1.栈的基本概念

​ 栈的定义：栈是一种只能在一端进行插入或删除操作的线性表，其中允许进行插入或删除操作的一端称为栈顶(Top)。栈顶由一个称为栈顶指针的位置指示器（本质上就是一个变量，对于顺序栈，是记录栈顶元素所处的index；如果是链栈，就是记录栈顶元素所在结点地址的指针），它是随着入栈、出栈操作动态变化的。表的另一端称为栈底，栈底是固定不变的。栈的插入和删除操作一般称为入栈和出栈。

​ 栈的特点：由栈的定义可以看出，栈的主要特点就是先进后出（First in Last out, FILO）、后进先出。

​ 我们生活中有很多的场景和栈是类似的，比如我们小时候喜欢的玩具枪，子弹压入弹匣和击发；开进一个死胡同的汽车，最先进去的汽车要等后进来的汽车都开出去了，才能出来。

2.栈的存储结构

​ 栈的存储结构主要有两种，分别是顺序栈和链栈。顺序栈其定义如下，可以看到，顺序栈的核心就是一个连续的存储空间，在这里体现为数组。

typedef struct {
  //用于存放栈中的元素
  int data[maxSize];
  //栈顶指针
  int top;
} SqStack;
1
2
3
4
5
6

​ 链栈的定义如下，可以看到，链栈就是采用链表来存储栈，采用头插法创建栈。对于栈而言插入和删除都在头部进行，链表可以不需要设置头结点（有无头结点皆可，主要看题目），头指针直接指向第一个结点，如下如所示：

typedef struct LNode {
  //数据域
  int data;
  //指针域
  struct LNode * next;
} LNode;
1
2
3
4
5
6

​ 栈有两种存储结构，不过一般而言，我们都会选择顺序栈，因为栈在考核中一般作为一种辅助的数据结构，越简单对于代码的实现越有帮助，因此在程序设计题，顺序栈应用情况要多于链栈。

3.顺序栈的定义和基本操作

3.1 顺序栈的要素

​ 对于顺序栈st，一共有四个要素，分别为两个特殊状态：栈空、栈满；两个操作：入栈、出栈。

​ 栈空：st.top==-1，表明栈是空的。也有的书本上，将st.top==0定义为栈空条件，具体情况，要看题目给出的定义。

​ 栈满：st.top==maxSize-1。maxSize为栈中最大元素的个数，当栈满时，栈顶元素存储于数组index=maxSize-1的位置。

​ 非法状态：栈满后继续入栈、栈空时继续出栈，对应着上溢、下溢两中非法状态。

​ 入栈操作：st.data[++top] = x。因为规定了top为-1时栈为空，则元素入栈前应当先移动指针，因此需要先将++top，然后将值放入对应的位置中。

​ 出栈操作：x = st.data[top–]。因为进栈时先移动栈顶指针，在存入元素，因此出栈时需要先返回栈顶元素，然后下移栈顶指针。

3.2 顺序栈的基本操作

​ 初始化栈

void initStack(SqStack *st){
  st->top = -1;
}
1
2
3

​ 判断栈是否为空

//如果为空，返回1，否则返回0
int isEmpty(SqStack st){
    if(st.top == -1){
        return 1;
    }
    return 0;
}
1
2
3
4
5
6
7

​ 进栈操作

int push(SqStack *st, int x){
    if(st->top == maxSize - 1){
        printf("栈满，无法入栈！");
        return 0;
    }
    st->data[++(st->top)] = x;
    return 1;
}
1
2
3
4
5
6
7
8

​ 出栈操作

int pop(SqStack *st, int *x){
    if(st->top == -1){
        printf("栈空，无法出栈！");
        return 0;
    }
    *x = st->data[(st->top)--];
    return 1;
}
1
2
3
4
5
6
7
8

​ 在考试中，栈一般是作为辅助的结构来解决其他问题，因此一般情况下，栈的定义和操作可以写的很简单，比如：

//两句话定义一个栈
int stack[maxSize];
int top = -1;
//入栈
stack[++top] = x;
//出栈
x = stack[top--];
1
2
3
4
5
6
7

4.链栈的定义和基本操作

4.1 链栈的要素

​ 对于链栈lst，也有四个要素，分别为两个特殊状态：栈空、栈满；两个操作：入栈、出栈。

​ 栈空：lst->next==NULL，表明栈是空的。

​ 栈满：一般情况下，不存在栈满的情况（除非内存不足，无法申请新的结点）。

​ 非法状态：栈空时继续出栈，会导致下溢。

​ 入栈操作：元素所处结点由指针p指向，使用头插法插入结点。

//头插法
p->next = lst->next;
lst->next = p;
1
2
3

​ 出栈操作：出栈元素保存在x中

//p指向出栈结点
p = lst->next;
x = p->data;
//栈顶指针指向下一个结点
lst->next = p->next;
free(p);
1
2
3
4
5
6

4.2 链栈的基本操作

​ 初始化栈

void initStack(LNode *lst){
  //new一个新结点
  lst = (LNode *)malloc(sizeof(LNode));
  lst->next = NULL;
}
1
2
3
4
5

​ 判断栈是否为空

//如果为空，返回1，否则返回0
int isEmpty(SqStack st){
    if(st.top == -1){
        return 1;
    }
    return 0;
}
1
2
3
4
5
6
7

​ 进栈操作

int push(LNode *lst, int x){
    //new一个新结点
    LNode *p;
    p = (LNode *)malloc(sizeof(LNode));
    if(!p){
        printf("内存不足，无法入栈！");
        return 0;
    }
    //为节点复制
    p->next = NULL;
    p->data = x;
    
    //头插法建立链表
    p->next = lst->next;
    lst->next = p;
    return 1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

​ 出栈操作

int pop(LNode *lst, int *x){
    if(lst->next == NULL){
        printf("栈空，无法出栈！");
        return 0;
    }
    //new一个新结点
    LNode *p;
    
    p = lst->next;
    *x = p->data;
    //栈顶指针指向下一个结点
    lst->next = p->next;
    free(p);
    return 1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

5.共享栈

​ 相对于普通栈，共享栈的主要目的是为了提高内存的利用率和减少溢出的可能性而设计的。

​ 如上图所示，两个栈共享一块连续的存储空间，且两个栈都是顺序栈。两个栈的栈底分别位于这块连续存储空间的两端，在两个栈入栈的过程中，top1向上增加，top2向下减少。

​ 顺序栈的特性可参考下题：

例题：为了增加内存空间的利用率和减少溢出的可能性，当两个栈共享一片连续的内存空间时，应将两栈的（①）分别设在这片内存空间的两端，这样当（②)时，才产生上溢。
①:A.长度 B.深度 C.栈顶 D.栈底
②: A.两个栈的栈顶同时到达栈空间的中心点
B.其中一个栈的栈顶到达栈空间的中心点
C.两个栈的栈顶在栈空间的某一位置相遇
D.两个栈均不空，并且一个栈的栈顶到达另一个栈的栈底

答案：D、C.

6.总结

​ 栈的概念和操作都比较简单，不过他却是经常作为辅助结构出现在其他问题的求解中，比如二叉树的非递归算法、括号的匹配问题，中缀表达式的转换等等。

​ 而且栈是一种应用非常广的数据结构，在函数的调用中，栈就扮演着非常重要的作用。我们一定以熟悉栈的特性，在求解具体问题中，将之利用好。

​ 关于栈和队列的练习题，可以参考这篇文章。

参考：

1.数据结构中的C语言编程基础

2.数据结构考研大纲

3.数据结构高分笔记

4.王道数据结构

5.数据结构–C语言版，严蔚敏

---

​ 又到了分隔线以下，本文到此就结束了，本文内容全部都是由博主根据自身理解与对考研资料进行的整理，仅作为参考，大佬有什么问题，可以评论区留言，如果有什么错误，还请批评指正。

本专栏为数据结构知识，喜欢的话可以持续关注，如果本文对你有所帮助，还请还请点赞、评论加关注。

有任何疑问，可以评论区留言。