本文最后更新于 8 天前，如有失效或谬误请评论区留言。

逻辑结构和线性表相同但是运算收到了限制，根据受到限制的不同分为栈和队列

1 栈

栈是限制在表一端(表尾)进行插入和删除的线性表，即只能在另一端进行插入和删除操作，并且操作顺序遵循先进后出的规律
栈的主要操作包括：

初始化空栈
入栈
出栈
判断栈是否为空栈
取栈顶数据元素

栈的存储方式有：

顺序存储结构->顺序栈
链式存储结构->链栈

1.1 顺序存储结构

用一组地址连续的存储单元依次存储栈中的每个数据元素，一般用数组实现，因为栈的操作都在栈顶进行，所以需要一个变量去保存栈顶的位置以方便操作，有以下两种常用方法：

栈顶指针指示栈顶的实际位置：数组长度n，栈顶为top，top为n说明栈顶为$a_{n}$，为-1说明栈是空栈
栈顶指针指示下一次入栈的位置：top为n+1说明栈顶为$a_{n}$，为0说明栈是空栈
(这里的指针指的不是指向内存地址的指针，这里的指针是一个逻辑的概念，实际就是一个整型变量，存储栈顶的数组下标)

#define MAXSIZE 1024
typedef struct{
    ElemType data[MAXSIZE];
    int top; //栈顶指针
}SeqStack;

若栈顶指针指示栈顶的实际位置，初始化后的空栈，其栈顶指针指向-1，此时如果有元素x1入栈，则s.data[top + 1] = x1，并且更新栈顶的位置++top，后面的元素同理，直到溢出报错，如果最后入栈的元素x5现在想要出栈，则直接更新栈顶的位置--top，不需要对数据本身做任何操作(因为后面如果再有入栈的元素会直接覆盖掉原来那里的值)

1.1.1 顺序栈操作的实现

初始化：s.top = -1
入栈：

if(s.top < MAXSIZE - 1)
    s.data[++s.top] = x;
else
    printf("overflow");

出栈：

if(s.top >= 0)
    s.top--;
else
    printf("overflow");

判断栈是否为空：s.top == -1
判断栈是否为满：s.top == MAXSIZE - 1
获取栈顶元素：s.data[s.top]

1.2 链式存储结构

采用不带表头的单链表存放栈
根据栈的定义，结点空间的指针存放直接前驱而不是直接后继
单链表的头指针对应栈顶
出栈：直接删除单链表的第一个数据元素结点
入栈：在第一个数据元素节点之前插入一个新的数据元素

typedef struct node{
    int data;
    struct node *next; // 直接前驱
}Node, *LinkList;
LinkList top; // 栈顶指针

1.2.1 链式栈操作的实现

出栈

if(top){ // 栈顶指针存在、指向头结点
    p = top;
    top = top->next;
    free(p);
}

把x入栈

s = (LinkList)malloc(sizeof(Node));
s->data = x;
s->next = top;
top = s;
// 建立一个新的结点s，把它作为新的表头，原来的表头的直接前驱设为它，并且更新栈顶指针

1.3 栈的应用

检查表达式中括号是否合法：左括号一个一个入栈，遇到一个匹配的右括号就出栈一个左括号，最后检查栈如果非空，则表达式括号不合法，反之为合法
将$+,-,\times,/$和单字母变量组成的普通表示转换为逆波兰式

1.3.1 表达式转换

前缀表达式：波兰式，不包含括号，运算符放在两个运算对象的前面，所有运算按照运算符出现的顺序从右向左执行(运算符之间的优先级被抹去)
后缀表达式：逆波兰式，不包含括号，运算符放在两个运算对象的后面，所有运算按照运算符出现的顺序从左向右执行(运算符之间的优先级被抹去)
中缀表达式：运算符放在两个运算对象中间，就是我们数学中常用的那种写法

1.3.1.1 中缀转前缀：

下面使用这个例子：$a\times b+c-d/e$

把运算符号移动到对应的括号前面
则变成：$-(+(\times(ab)c)/(de))$

把括号去掉：-+*abc/de

前缀表达式出现

1.3.1.2 中缀转后缀：

把运算符号移动到对应的括号后面
则变成：$(((ab)\times c)+(de)/)-$

把括号去掉：ab*c+de/-

后缀表达式出现

1.4 双栈共享存储空间

两个栈公用一个一维数组的实现方式，栈底分别设在数组的两端，各自向中间伸展，两个栈共享存储空间，可以互补空间，使得某个栈实际可利用的空间大于$\frac{M}{2}$

2 队列

限制插入在表一段进行，而删除在表的另一端进行，其特点是先进先出，即先进入队列的元素必定先出队

主要操作：

入队
出队
初始化空队列
求队长

存储方式：

顺序存储结构：顺序队列
链式存储结构：链队

2.1 顺序存储结构

#define MAXSIZE 5
typedef struct{
    ElemType data[MAXSIZE];
    int f,r; // 队首和队尾指针
}SeQueue;
SeQueue q;

顺序结构的队列就是双指针的思想，队首和队尾指针初始都在0，如果有新元素入队，在不溢出的前提下，队尾指针++，比如元素x1入队，则q.data[f++] = x1，此时的队首就是0没有问题不变，每出队一个元素，队首就也自增，直到队尾和队首都到溢出边缘

2.1.1 顺序队列操作的实现

初始化：q.f = 0;q.r = 0;
入队：

if(q,r < MAXSIZE){
    q.data[q.r] = x;
    q.r++;
}
else
    printf("overflow");

出队：

if(q.f != q.r) // 或者if(q.f < q.r)
    q.f++;

2.2 循环队列

上述普通的队列在队首和队尾指针都到溢出边缘时，出现假溢出的情况，即数组其实整个空间都属于未使用的空间，只是两个指针碰一块了，这个结构和算法无法处理这种情况，此时我们有如下解决办法：

每删除一个数据元素，余下的所有元素顺次移动一个位置：由于数组是顺序表结构，移动位置占用的资源太多，时间复杂度是$O(n)$，这个方案不可取
循环队列，通过取余运算，将顺序队列data[0,MAXSIZE - 1]看成一个头尾相接的循环结构

2.2.1 循环队列操作实现

初始化：q.f = 0;q.r = 0;
入队:

if(有空间){
    q.data[q.r] = x;
    q.r = (q.r + 1)%MAXSIZE;
}
else
    printf("overflow");

出队：

if(队不空)
    q.f = (q.f + 1)%MAXSIZE;

2.2.2 队空和队满

如果这样实现的话，就会出现另一个问题，即队空和队满时都有$q.f==q.r$，无法根据这两个指针的相对位置判断队列是空的还是满的，有如下解决方法

2.2.2.1 牺牲一个位置

指定数组的某个元素位里面不存储数据，这样的话当(q.r+1)%MAXSIZE==q.f就认为队满了，q.r == q.f为队空

2.2.2.2 引入一个计数器

设一个计数器，初始化的时候计数器清零，入队时计数器+1，出队时计数器-1

2.3 链式存储结构

很显然的结构，入队就是给现有表尾添加一个直接后继，出队就是删除表的第一个元素，不再赘述

2.4 双端队列和超队列

双端队列是一种允许同时从前端和后端添加和删除元素的特殊队列，它是队列和栈的结合体

输入受限双端队列是队列的一端允许插入、删除，另一端只允许删除的双端队列

输出受限双端队列是队列的一端允许插入、删除，另一端只允许插入的双端队列

超队列插入限制在一端，但删除出队仍允许在两端进行

1 栈