数据结构：栈&队列

栈

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

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

顺序栈

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

• 栈顶指针：S.top，初始时设置S.top=-1
• 进栈操作：栈不满时，栈顶指针先 +1，再送值到栈顶元素
• 出栈操作：栈非空时，先取出栈顶元素，再将栈顶指针 -1
• 栈空条件：S.top==-1
• 栈满条件：S.top==MaxSize-1
• 栈长条件：MaxSize=S.top+1

共享栈

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

两个栈的栈顶指针都指向栈顶元素，top0=-1时0号栈为空，top1=MaxSize时1号栈为空；仅当两个栈指针相邻top1-top0=1时，判断为栈满。当0号栈进栈时top0先加1再赋值，1号栈进栈时top1先减1再赋值；出栈则相反。

共享栈是为了更有效地利用存储空间，两个栈的空间相互调节，只有在整个存储空间都被占满时才会发生上溢，其取数据的时间复杂度均为O(1)。

链栈

采用链式存储的栈称为链栈，链栈的优点便是多个栈共享存储空间和提高效率，且不存在栈满上溢的情况。规定链栈没有头结点，Lhead指向栈顶元素。

队列

队列（Queue）：简称队，也是一种操作受限的线性表，只允许在表的一端进行插入，而在表的另一端进行删除。

• 队头（Front）：允许删除的一端
• 队尾（Rear）：允许插入的一端
• 空队列：不含任何元素的空表

队列是操作受限的线性表，所以，不是任何对线性表的操作都可以作为队列的操作。比如，不可随便读取队列中间的某个元素。

顺序队列

队列的顺序实现是指分配一块连续的存储单元存放队列中的元素，并附设两个指针front和rear分别指向队头和队尾的位置，设队头指针指向队头元素，队尾指针指向队尾元素的下一个位置。

• 队空条件：Q.front==Q.rear==0
• 进队操作：队不满时，先送值到队尾，再将队尾指针 +1
• 出队操作：队不空时，先取出队头元素，再将队头指针 +1

循环队列

将顺序队列臆造为一个环状的空间，即把存储队列元素的表从逻辑上看成一个环，称为循环队列。

• 队空条件：Q.front==Q.rear==0
• 队首指针进1：Q.front=(Q.front+1)%MaxSize
• 队尾指针进1：Q.rear=(Q.rear+1)%MaxSize
• 出队入队时：指针都按顺时针方向进1

为了区分队空和队满的情况，有三种处理方式：

1. 牺牲一个单元来区分队空和队满，入队时少用一个队列单元，这是一种较为普遍的做法。约定以“队头指针在队尾指针的下一个位置作为队满的标志”。

• 队空条件：Q.front==Q.rear==0
• 队满条件：(Q.rear+1)%MaxSize==Q.front
• 队列中元素个数：(Q.rear-Q.front+MaxSize)%MaxSize

2. 类型中增设表示元素个数的数据成员。

• 队空的条件为Q.size==0
• 队满条件为Q.size==MaxSize

3. 类型中增设tag数据成员，以区分是队满还是队空。tag等于0的情况下，若因删除导致Q.front==Q.rear则队空；tag等于1的情况下，若因插入导致Q.front==Q.rear则队满。

链队列

队列的链式表示称为链队列，它实际上是一个同时带有队头指针和队尾指针的单链表，头指针指向队头节点，尾指针指向队尾节点，即单链表的最后一个节点。

当Q.front==NULL且Q.rear==NULL时，链式队列为空

• 出队时，首先判断队是否为空，若不空，则取出对头元素，将其从链表中摘除，并让Q.front指向下一个节点（若该节点为最后一个节点，则置Q.front和Q.rear都为NULL）。
• 入队时，建立一个新节点，将新节点插入到链表的尾部，并改让Q.rear指向这个新插入的节点（若原队列为空队，则令Q.front也指向该节点）

双端队列

双端队列是指允许在两端都可以进行入队和出队操作的队列，其元素的逻辑结构仍然是线性结构。将队列的两端分别称为前端和后端。

• 在双端队列进队时：前端进的元素排列在队列中后端进的元素的前面，后端进的元素排列在队列中前端进的元素的后面
• 在双端队列出队时：无论前端还是后端出队，先出的元素排列在后出的元素的前面
• 输出受限的双端队列：允许在一端进行插入和删除，但在另一端只允许插入的双端队列
• 输入受限的双端队列：允许在一端进行插入和删除，但在另一端只允许删除的双端队列