在实际生活中，描述数据元素之间逻辑关系的问题不仅仅局限于线性结构，例如家庭、行政组织机构等都是非线性的数据结构。树就是一种非线性的数据结构。

一、栈

栈是只能在某一端插入和删除的特殊线性表。用桶堆积物品，先堆进来的压在底下，随后一件一件往上堆。取走时，只能从上面一件一件取。堆和取都在顶部进行，底部一般是不动的。栈就是一种类似桶堆积物品的数据结构，进行删除和插入的一端称栈顶，另一端称栈底。插入一般称为进栈（PUSH），删除则称为退栈（POP）。栈也称为后进先出表（LIFO 表）。 一个栈可以用定长为 n 的数组 s 来表示，用一个栈指针top 指向栈顶。若 top=0 ，表示栈空，top=n 则栈满。进栈时 top 加 1，退栈时 top 减 1，当 top<0 时为下溢，栈指针在运算中永远指向栈顶。

1. 进栈（PUSH）算法

1. 若 top>=n 时，则给出溢出信息，作出错处理（进栈前首先检查栈是否已满，满则溢出；不满则作②）；
2. top++（栈指针加 1，指向进栈地址）；
3. s[top]=x，结束（x 为新进栈的元素）；

2. 退栈（POP）算法

1. 若 top<=0，则给出下溢信息，作出错处理（退栈前先检查是否已为空栈，空则下溢；不空则作②）；
2. x=s[top]（退栈后的元素赋给 x）；
3. top--，结束（栈指针减 1，指向栈顶）。

进栈，出栈的C++实现过程程序

#define n 100
void push(int s[], int *top, int *x) { //进栈
    if (*top == n) printf("overflow");
    else { *top++; s[*top] = *x; }
}
void pop(int s[], int *y, int *top) { //出栈
    if (*top == 0) printf("underflow");
    else { *y = s[*top]; *top--; }
}

对于出栈运算中的“下溢”，程序中仅给出了一个标志信息。在任何情况下，下溢都是控制程序转移的判断标志，是十分有用的。对于入栈运算中的“上溢”，则是一种致命错误，将使程序无法继续运行，所以要设法避免。

例题 1：设输入元素为 123PA，如图所示。元素经过栈后到达输出序列。输出次序为 PA321，输入次序为 123PA。

【解答】高级语言变量名的定义规则为以字母开头，字母与数字的组合。由于必须以字母开头，所以第一个可能出现的字母是 P，那么必然要求 123 已经先后入栈，这样便可得到以 P 开头的、并且 123 按逆序排列的（即 321）、同时 A 位于 P 后任一位置的变量名序列。此外，还需要考虑以 A 开头的可能情况，这只有一种情形为 AP321。所以 AP321、PA321、P3A21、P32A1、P321A 可以作为高级语言的变量名。

例题 2：火车站列车调度，假设调度站两侧的轨道为单向行驶轨道。

1. 如果进站的车厢序列为 123，则可能的出站车厢序列是什么？
2. 如果进站的车厢序列为 123456，问能否得到 135426 和 435612 的出站序列？

【解答】

• 如果进站的车厢序列为 123，则可能的出站车厢序列为 321、213、132 和 231。
• 如果进站的车厢序列为 123456，则不能得到 135426 和 435612 的出站序列。

二、队列

队列是限定在一端进行插入，另一端进行删除的特殊线性表。就像排队买东西，排在商店前面的人先买完东西离开队伍（删除），后面的人买完东西后离开队伍（删除）。通常把队列的所有需要进队的数据项，只能从队尾进入，数据项只能从队头离去。由于总是先进队的元素先出队（先排队的人先买完东西），所以这种表也称为先进先出（FIFO）表。

队列的存储与运算

队列可以用数组 Q[m+1] 来存储，数组的上界即是队列所容许的最大容量。在队列的运算中需设两个指针：

• head：队头指针，指向实际队头元素的位置。
• tail：队尾指针，指向实际队尾元素的后一个位置。

一般情况下，两个指针的初值设为 0，这时队列为空，没有元素。图 1(a) 画出了一个由 6 个元素构成的队列，数组定义为 Q[11]。

• Q(i) = 3, 4, 5, 6, 7, 8，头指针 head = 2，尾指针 tail = 8。
• 队列中拥有的元素个数为 L = tail - head。
• 现要让排头的元素出队，则需将头指针加 1，这时头指针向上移动一个位置，指向 Q(3)，表示 Q(3) 已经出队，见图 1(b)。
• 如果想让一个新元素入队，则需尾指针向上移动一个位置，即 tail++，这时 Q(9) 入队，见图 1(c)。
• 当队尾已经处在最上面时，即 tail = 10，见图 1(d)，如果还要执行入队操作，则会发生“上溢”。但实际上队列中还有三个空位置，所以这种溢出称为“假溢出”。

克服假溢出的方法有两种：

1. 一种是将队列中的所有元素均向低地址区移动，显然这种方法很浪费时间。
2. 另一种方法是将数组存储区看成是一个首尾相接的环形区域。当存放到 n 地址后，下一个地址就“翻转”为 1，在结构上采用这种技巧来存储的队列称为循环队列，见图 2。

循环队列的入队算法如下：

1. tail++;
2. 若 tail = n+1 ，则 tail = 1;
3. 若 head = tail ，则尾指针与头指针重合，表示元素已装满队列，则作上溢出错处理。
4. 否则，Q(tail) = x，结束（x 为新入队元素）。

三、习题

1. NOIP2013/NOIP2018 下图中所使用的数据结构是()。

{{ select(1) }}

• 哈希表
• 栈
• 队列
• 二叉树

2. NOIP2008 设栈 s 的初始状态为空，元素 a、b、c、d、e、f 依次入栈 s，出栈的序列为 b、d、f、e、c、a，则栈 s 的容量至少应该是()。

{{ select(2) }}

• 6
• 5
• 4
• 3

3. NOIP2009 有六个元素 FEDCBA 从左至右依次进栈。下列不可能是合法出栈序列的是()。

{{ select(3) }}

• EDCFAB
• DECABF
• CDFEBA
• BCDAEF

4. NOIP2010 元素 R1、R2、R3、R4、R5 的入栈顺序为 R1、R2、R3、R4、R5，若 R3 最先出栈，则第 5 个出栈的不可能是()。

{{ select(4) }}

• R1
• R2
• R4
• R5

5. NOIP2012 如果一个栈初始时为空，且当前栈中的元素从栈底到栈顶依次为 a，b，c（如右图所示），另有元素 d 已经出栈，则可能的入栈顺序是()。

{{ select(5) }}

• a,d,c,b
• b,a,c,d
• a,c,b,d
• d,a,b,c

6. NOIP2015 有一空栈 S，对下列待进栈的数据元素序列 a、b、c、d、e、f 依次进行进栈、进栈、出栈、进栈、进栈、出栈的操作，则此操作完成后，栈 S 的栈顶元素为()。

{{ select(6) }}

• f
• c
• a
• b

7. NOIP2017 表达式 a*(b+c)*d 的后缀形式是()。

{{ select(7) }}

• abcd*+*
• abc+*d *
• a*bc+*d
• b+c *a *d

8. NOIP2017 对于栈顺序为 a、b、c、d、e、f、g 的序列，下列不可能是合法的出栈序列的是()。

{{ select(8) }}

• a,b,c,d,e,f,g
• a,d,c,b,e,g,f
• a,d,b,c,g,f,e
• g,f,e,d,c,b,a

9. NOIP2011 广度优先搜索时需要用到的数据结构是()。

{{ select(9) }}

• 链表
• 队列
• 栈
• 散列表

10. NOTP2017 向一个栈顶指针为 hs 的链式栈中插入一个指针 s 指向的结点时，应执行()

{{ select(10) }}

• hs->next=s ;
• s->next=hs ; hs=s ;
• s->next=hs->next ; hs->next=s ;
• s->next=hs ; hs=hs->next ;

11. NOIP2012 () 是一种先进先出的线性表。

{{ select(11) }}

• 栈
• 队列
• 哈希表（散列表）
• 二叉树