第二章 程序设计基础知识
第7节 栈和队列
一、栈
栈是只能在某一端插入和删除的特殊线性表。用桶堆积物品，先堆进来的压在底下，随后一件一件往上堆。取走时，只能从上面一件一件取。堆和取都在顶部进行，底部一般是不动的。栈就是一种类似桶堆积物品的数据结构，进行删除和插入的一端称栈顶，另一端称栈底。插入一般称为进栈（PUSH），删除则称为退栈（POP）。栈也称为后进先出表（LIFO表）。
一个栈可以用定长为n的数组s来表示，用一个栈指针top指向栈顶。若top=0，表示栈空，top=n则栈满。进栈时top加1，退栈时top减1，当top<0时为下溢，栈指针在运算中永远指向栈顶。
- 进栈（PUSH）算法
- 若top>=n时，则给出溢出信息，作出错处理（进栈前首先检查栈是否已满，满则溢出；不满则作②）；
- top++（栈指针加1，指向进栈地址）；
- s[top]=x，结束（x为新进栈的元素）；
- 退栈（POP）算法
- 若top<=0，则给出下溢信息，作出错处理（退栈前先检查是否已为空栈，空则下溢；不空则作②）；
- x=s[top]，（退栈后的元素赋给x）；
- top--，结束（栈指针减1，指向栈顶）。
进栈、出栈的C++实现过程程序：
#define n 100
void push(int s[],int *top,int *x) //入栈
{
if(*top==n)printf("overflo"); else (*top++;s[*top]=*x;}
}
void pop(int s[],int *y,int *top) //出栈
{
if(*top==0)printf("nderflow"); else {*y=s[*top];*top--;}
}
从历届初赛可以看出，栈也是属于比较容易出题的知识点，选择题、解答题等题型都有可能出现。
例题1：设输入元素为1、2、3、P和A，输入次序为123PA，如图所示。元素经过栈后到达输出序列，当所有元素均到达输出序列后，有哪些序列可以作为高级语言的变量名？
【解答】高级语言变量名的定义规则：以字母开头，字母与数字的组合。由于必须以字母开头，所以，第一个可能出现的字母是P，那么必然要求123已经先后入栈，这样便可得到以P开头的、并且123按逆序排列的（即321）、同时A位于P后任一位置的变量名序列。此外，还需要考虑以A开头的可能情况，这只有一种情形为AP321。所以AP321，PA321，P3A21，P32A1，P321A可以作为高级语言的变量名。
例题2：火车站列车调度，假设调度站两侧的轨道为单向行驶轨道。
①如果进站的车厢序列为123，则可能的出站车厢序列是什么？
②如果进站的车厢序列为123456，问能否得到135426和435612的出站序列。
二、队列
队列是限定在一端进行插入，另一端进行删除的特殊线性表。就像排队买东西，排在前面的人买完东西后离开队伍（删除），而后来的人总是排在队伍末尾（插入）。通常把队列的删除和插入分别称为出队和入队。允许出队的一端称为队头，允许入队的一端称为队尾。所有需要进队的数据项，只能从队尾进入，队列中的数据项只能从队头离去。由于总是先入队的元素先出队（先排队的人先买完东西），这种表也称为先进先出（FIFO）表。
队列可以用数组Q[m+1]来存储，数组的上界m即是队列所容许的最大容量。在队列的运算中需设两个指针：
- head：队头指针，指向实际队头元素的前一个位置；
- tail：队尾指针，指向实际队尾元素所在的位置。
一般情况下，两个指针的初值设为0，这时队列为空，没有元素。图1（a）画出了一个由6个元素构成的队列，数组定义Q[11]。Q(i) i=3,4,5,6,7,8，头指针head=2，尾指针tail=8。
队列中拥有的元素个数为L=tail-head，现要让排头的元素出队，则需将头指针加1，即head++。这时头指针向上移动一个位置，指向Q(3)，表示Q(3)已出队，见图1（b）。
如果想让一个新元素入队，则需尾指针向上移动一个位置，即tail++，这时Q(9)入队，见图1（c）。
当队尾已经处在最上面时，即tail=10，见图1（d），如果还要执行入队操作，则要发生"上溢"，但实际上队列中还有三个空位置，所以这种溢出称为"假溢出"。
克服假溢出的方法有两种。一种是将队列中的所有元素均向低地址区移动，显然这种方法很浪费时间；另一种方法是将数组存储区看成是一个首尾相接的环形区域。当存放到n地址后，下一个地址就"翻转"为1，在结构上采用这种技巧来存储的队列称为循环队列。
循环队列的入队算法如下：
- tail++;
- 若tail=n+1，则tail=1;
- 若head=tail，尾指针与头指针重合，表示元素已装满队列，则作上溢出错处理;
- 否则，Q(tail)=x，结束（x为新入队元素）。