第三章 栈和队列
3.1 栈的表示和实现
3.2 递归过程
3.4 队列的表示和实现
栈和队列的逻辑结构、物理结构，以及它们之间的相互关系；
定义与之相适应的运算；
设计相应的算法；
分析算法的效率。
3.1.1、栈的概念栈 （ stack） 是 插入 和 删除 操作限定在表尾进行的线性表。
栈的逻辑表示为,S =（ a1,a2,…,an）
表尾元素 an称为 栈顶 (top)
表头元素 a1称为 栈底 (bottom)
不含元素的空表称为 空栈
栈的运算特性是后进先出 (Last In First Out--LIFO)
或先进后出 (First In Last Out--FILO)
3.1 栈的表示和实现
3.1.2 顺序栈由于栈是运算受限的线性表，因此线性表的存储结构对栈也适应。
栈的顺序存储结构简称为顺序栈，它是运算受限的线性表。因此，可用数组来实现顺序栈。因为栈底位臵是固定不变的，
所以可以将栈底位臵设臵在数组的两端的任何一个端点；栈顶位臵是随着进栈和退栈操作而变化的，故需用一个整型变量 top
3.1 栈的表示和实现来指示当前栈顶的位臵，通常称 top为栈顶指针。因此，顺序栈的类型定义只需将顺序表的类型定义中的长度属性改为 top即可。
顺序栈的类型定义如下：
# define StackSize 100
typedef char datatype;
typedef struct {
datatype data[stacksize];
int top;
}seqstack;
例、一叠书或一叠盘子。
栈的抽象数据类型的定义如下,P44
a n
a n-1
a2
a1
……
栈顶栈底
top
base
top
7
6
5
4
3
2
1
－ 1
设 S是 SeqStack类型的指针变量。若栈底位置在向量的低端，即 s–>data[0]是栈底元素，那么栈顶指针 s–>top是正向增加的，即进栈时需将 s–>top加 1，退栈时需将
s–>top 减 1。因此,s–>top<0表示空栈，
s–>top =stacksize-1表示栈满。当栈满时再做进栈运算必定产生空间溢出，简称
,上溢,;当栈空时再做退栈运算也将产生溢出，简称,下溢,。上溢是一种出错状态，应该设法避免之；下溢则可能是正常现象，因为栈在程序中使用时，其初态或终态都是空栈，所以下溢常常用来作为程序控制转移的条件。
3.1.3、判断栈满
int stackfull(seqstack *s)
{
return(s–>top==stacksize-1);
}
3.1.4、进栈
void push(seqstack *s,datatype x)
{
if (stackfull(s))
printf(“stack overflow”);
s–>data[++s–>top]=x;
}
3.1.5、置空栈
void initstack(seqstack *s)
{
s–>top=-1;
}
3.1.6、判断栈空
int stackempty(seqstack *s)
{
return(s–>top==-1);
}
3.1.7、退栈
datatype pop(seqstack *s)
{
if (stackempty(s))
error(“stack underflow”);
x=s–>data[top];
s–>top--;
return(x)
//return(s–>data[s–>top--]);
}
3.1.8、取栈顶元素
Datatype stacktop(seqstack *s)
{
if(stackempty(s)
error(“stack is enpty”);
return s–>data[s–>top];
}
3.1.3 链栈栈的链式存储结构称为链栈，它是运算是受限的单链表，克插入和删除操作仅限制在表头位置上进行,由于只能在链表头部进行操作，故链表没有必要像单链表那样附加头结点。栈顶指针就是链表的头指针。 链栈的类型说明如下：
typedef struct stacknode{
datatype data
struct stacknode *next
}stacknode;
typedef struct { stacknode *top}
linkstack;
Void initstack(linkstack *p)
{
p–>top=null;
}
int stackempty(linkstack *p)
{
return p–>top==null;
}
Void push(linkstack *p,datatype x)
{
stacknode *q
q=(stacknode*)malloc(sizeof(stacknode));
q–>data=x;
q–>next=p–>top;
p–>top=p;
}
Datatype pop(linkstack *p)
{
datatype x;
stacknode *q=p–>top;
if(stackempty(p)
error(“stack underflow.”);
x=q–>data;
p–>top=q–>next;
free(q);
return x;
}
datatype stack top(linkstack *p)
{
if(stackempty(p))
error(“stack is empty.”);
return p–>top–>data;
}
3.2 栈的应用举例由于栈结构具有的后进先出的固有特性，
致使栈成为程序设计中常用的工具。以下是几个栈应用的例子。
3.2.1 数制转换十进制 N和其它进制数的转换是计算机实现计算的基本问题,其解决方法很多,其中一个简单算法基于下列原理,
N=(n div d)*d+n mod d
( 其中,div为整除运算,mod为求余运算 )
例如 (1348)10=(2504)8,其运算过程如下：
n n div 8 n mod 8
1348 168 4
168 21 0
21 2 5
2 0 2
void conversion( ) {
initstack(s);
scanf (“%”,n);
while(n){
push(s,n%8);
n=n/8;
}
while(! Stackempty(s)){
pop(s,e);
printf(“%d”,e);
}
}
3.2.2 括号匹配的检验假设表达式中充许括号嵌套,则检验括号是否匹配的方法可用,期待的急迫程度,这个概念来描述。例：
（（）（） （（）））
3.2.3 行编辑程序在编辑程序中，设立一个输入缓冲区，
用于接受用户输入的一行字符，然后逐行存入用户数据区。允许用户输入错误，并在发现有误时可以及时更正。
行编辑程序算法如下,
void lineedit( ){
initstack(s);
ch=gether( );
while(ch!=eof){
while(ch!=eof && ch!=?\n?){
switch(ch){
case?#?,pop(s,c);
case?@?,clearstack(s);
default,push(s,ch);
}
ch=getchar( );
}
clearstack(s);
if(ch!=eof)
ch=gethar( );
}
destroystack(s);
}
3.2.4 迷宫求解入口出口
3.4 队列
3.4.1 抽象数据类型队列的定义队列 (Queue)也是一种运算受限的线性表。它只允许在表的一端进行插入，而在另一端进行删除。
允许删除的一端称为队头 (front)，允许插入的一端称为队尾 (rear)。
例如：排队购物。操作系统中的作业排队。先进入队列的成员总是先离开队列。因此队列亦称作先进先出 (First In First Out)的线性表，简称 FIFO
表。
当队列中没有元素时称为空队列。在空队列中依次加入元素 a1,a2,… an之后,a1是队头元素,an是队尾元素。显然退出队列的次序也只能是 a1,a2,… an,
也就是说队列的修改是依先进先出的原则进行的。
下图是队列的示意图：
a1 a2 … an出队 入队队头 队尾队列的抽象数据定义见书Ｐ 59
3.4.2 循环队列－队列的顺序表示和实现队列的顺序存储结构称为顺序队列，顺序队列实际上是运算受限的顺序表，和顺序表一样，
顺序队列也是必须用一个向量空间来存放当前队列中的元素。由于队列的队头和队尾的位臵是变化的，因而要设两个指针和分别指示队头和队尾元素在队列中的位臵，它们的初始值地队列初始化时均应臵为０。入队时将新元素插入所指的位臵，然后将加１。出队时，删去所指的元素，然后将加１并返回被删元素。由此可见，当头尾指针相等时队列为空。在非空队列里，头指针始终指向队头元素，而尾指针始终指向队尾元素的下一位臵。
０ １ ２ ３ 0 1 2 3
Front
rear
a b c
Front rear
(a)队列初始为空 （ b） A,B,C入队
０ １ ２ ３ ０ １ ２ ３
b c
front rear front
rear
（ c) a出队 (d) b,c出队，队为空和栈类似，队列中亦有上溢和下溢现象。此外，
顺序队列中还存在,假上溢,现象。因为在入队和出队的操作中，头尾指针只增加不减小，致使被删除元素的空间永远无法重新利用。因此，尽管队列中实际的元素个数远远小于向量空间的规模，但也可能由于尾指针巳超出向量空间的上界而不能做入队操作。该现象称为假上溢。
为充分利用向量空间。克服上述假上溢现象的方法是将向量空间想象为一个首尾相接的圆环，并称这种向量为循环向量，存储在其中的队列称为循环队列（ Circular Queue)。在循环队列中进行出队、入队操作时，头尾指针仍要加 1，朝前移动。
只不过当头尾指针指向向量上界（ QueueSize-1）
时，其加 1操作的结果是指向向量的下界 0。
这种循环意义下的加 1操作可以描述为：
if(I+1==QueueSize)
i=0;
else
i++;
利用模运算可简化为,i=(i+1)%QueueSize
显然，因为循环队列元素的空间可以被利用，
除非向量空间真的被队列元素全部占用，否则不会上溢。因此，除一些简单的应用外，真正实用的顺序队列是循环队列。
如图所示：由于入队时尾指针向前追赶头指针，
出队时头指针向前追赶尾指针，故队空和队满时头尾指针均相等。因此，我们无法通过 front=rear
来判断队列“空”还是“满”。
解决此问题的方法至少有三种：
其一是另设一个布尔变量以匹别队列的空和满；
其二是少用一个元素的空间，约定入队前，测试尾指针在循环意义下加 1后是否等于头指针，若相等则认为队满（注意,rear所指的单元始终为空）；
其三是使用一个计数器记录队列中元素的总数
（实际上是队列长度）。下面我们用第三种方法实现循环队列上的六种基本操作，为此先给出循环队列的类型定义。
#define QueueSize 100
typedef char DataType;
typedef Struct{
int front;
int rear;
int count;
datatype data[queuesize]
}cirqueue;
（ 1）臵空队
void initqueue(cirqueue *q){
q–>front=q–>rear=0;
q–>count=0;
}
（ 2）判断队空
int queueempty(cirqueue *q) {
return q–>count==0;
}
（ 3）判断队满
int queuefull(cirqueue *q){
return q–>count==queuesize;
}
（ 4）入队
void enqueue(cirqueue *q,datatype x)
{
if(queuefull(q))
error(“queue overflow”);
q–>count++;
q–data[q–rear]=x;
q–rear=(q–rear+1)%queuesize;
}
（ 5）出队
datatype dequeue(cirqueue *q)
{
datatype temp;
if(queueempty(q))
error(“queue underflow”);
temp=q–>data[q–>front];
q–>count--;
q–front=(q–>front+1)%queuesize;
return temp;
}
（ 6）取头指针
datatype queuefront(cirqueue *q)
{
if(queueempty(q))
error(“queue is empty.”);
return q–>data[q–>front];
}
3.4.3 链队列
队列的链式存储结构简称为链队列，它是限制仅在表头删除和表尾插入的单链表。显然仅有单链表的头指针不便于在表尾做插入操作，
为此再增加一个尾指针，指向链表的最后一个结点。于是，一个链队列由一个头指针唯一确定。和顺序队列类似，我们也是将这两个指针封装在一起，将链队列的类型 LinkQueue定义为一个结构类型：
typedef struct queuenode{
datatype data;
struct queuenode *next;
}queuenode;
typedef struct{
queuenode *front;
queuenode *rear;
}linkqueue;
下面给出链队列上实现的基本运算：
void initqueue(linkqueue *q)
{
q–>front=q–>rear=null;
}
int queueempty(linkqueue *q)
{
return q–>front==null &&q–>rear==null;
}
void enqueue(linkqueue *q,datatype x)
{
queuenode *p
p=(queuenode * )malloc(sizeof(queuenode));
p–>data=x;
p–next=null;
if(queueempty(q))
q–>front=q–>rear=p;
else{
q–>rear–>next=p;
q–rear=p;
}
}
Datatype dequeue(linkqueue *q)
{
datatype x;
queuenode *p
if(queueempty(q))
error(“queue underflow”);
p=q–>front;
x=p–>data;
q–>front=p–>next;
if(q–>rear==p)
q–rear=null;
free(p);
return x;
}
datatype queuefront(linkqueue *q)
{
if(queueempty(q))
error(“queue is empty.”);
return q–>front–>data;
}
注意：在出队算法中，一般只需修改队头指针。
但当原队中只有一个结点时，该结点既是队头也是队尾，故删去此结点时亦需修改尾指针，
且删去此结点后队列变空。
习题
1、设将整数以万计,2,3,4依次进栈，但只要出栈时栈非空，则可将出栈操作按任何次序夹入其中，请回答下有问题：
（ 1）若入栈次序为 push(1),pop(),push(2，
push(3),pop(),pop( ),push(4),pop( )，
则出栈的数字序列为什么？
（ 2）能否得到出栈序列车员 423和平共处五项原则 432？并说明为什么不能得到或如何得到。
（ 3）请分析 1,2,3,4的 24种排列中，哪些序列可以通过相应的入出栈得到。
2、链栈中为何不设头指针？
3、循环队列的优点是什么？如何判断它的空和满？
4、设长度为 n的链队列用单循环链表表示，若只设头指针，则怎样进行入队和出队操作；若只设尾指针呢？
5、利用栈的基本操作，写一个返回栈 s中结点个数的算法 int stacksize(seqstack s)，并说明 s为何不用作为指针参数？
6、利用栈的基本操作，写一个将栈中所有结点均删除算法，并说明 S为何要作为指针参数？
7、用第二种方法，即少用一个元素空间的方法来区别循环队列的队空和队满，试设计臵空队、
判队空、判队满、出队、入队及取队头元素等六个基本操作。
8、假设循环队列只设 rear和 quelen来分别指示队尾元素的位臵和队中元素的个数，试给出判断此循环队列的队满条件，并写出相应的入队和出队算法，要求出队时需返回队头指针。
9、指出下列程序段的功能是什么？
(1) void demo1(seqstack *s){
int I;arr[64];n=0;
while (!stackempty(s)) arr[n++]=pos(s);
for(I=0;<n;I++) push(s,arr[I]);
}
(2) void demo2(seqstack *s,int m){
seqstack t; int i;
initstack(t);
while(! Stackempty(s))
if(I=pop(s)!=m) push(t,I);
While(! Stackempty(t)) {
i=pop(t);
push(s,I);
}
}
3.1 栈的表示和实现
3.2 递归过程
3.4 队列的表示和实现
栈和队列的逻辑结构、物理结构，以及它们之间的相互关系；
定义与之相适应的运算；
设计相应的算法；
分析算法的效率。
3.1.1、栈的概念栈 （ stack） 是 插入 和 删除 操作限定在表尾进行的线性表。
栈的逻辑表示为,S =（ a1,a2,…,an）
表尾元素 an称为 栈顶 (top)
表头元素 a1称为 栈底 (bottom)
不含元素的空表称为 空栈
栈的运算特性是后进先出 (Last In First Out--LIFO)
或先进后出 (First In Last Out--FILO)
3.1 栈的表示和实现
3.1.2 顺序栈由于栈是运算受限的线性表，因此线性表的存储结构对栈也适应。
栈的顺序存储结构简称为顺序栈，它是运算受限的线性表。因此，可用数组来实现顺序栈。因为栈底位臵是固定不变的，
所以可以将栈底位臵设臵在数组的两端的任何一个端点；栈顶位臵是随着进栈和退栈操作而变化的，故需用一个整型变量 top
3.1 栈的表示和实现来指示当前栈顶的位臵，通常称 top为栈顶指针。因此，顺序栈的类型定义只需将顺序表的类型定义中的长度属性改为 top即可。
顺序栈的类型定义如下：
# define StackSize 100
typedef char datatype;
typedef struct {
datatype data[stacksize];
int top;
}seqstack;
例、一叠书或一叠盘子。
栈的抽象数据类型的定义如下,P44
a n
a n-1
a2
a1
……
栈顶栈底
top
base
top
7
6
5
4
3
2
1
－ 1
设 S是 SeqStack类型的指针变量。若栈底位置在向量的低端，即 s–>data[0]是栈底元素，那么栈顶指针 s–>top是正向增加的，即进栈时需将 s–>top加 1，退栈时需将
s–>top 减 1。因此,s–>top<0表示空栈，
s–>top =stacksize-1表示栈满。当栈满时再做进栈运算必定产生空间溢出，简称
,上溢,;当栈空时再做退栈运算也将产生溢出，简称,下溢,。上溢是一种出错状态，应该设法避免之；下溢则可能是正常现象，因为栈在程序中使用时，其初态或终态都是空栈，所以下溢常常用来作为程序控制转移的条件。
3.1.3、判断栈满
int stackfull(seqstack *s)
{
return(s–>top==stacksize-1);
}
3.1.4、进栈
void push(seqstack *s,datatype x)
{
if (stackfull(s))
printf(“stack overflow”);
s–>data[++s–>top]=x;
}
3.1.5、置空栈
void initstack(seqstack *s)
{
s–>top=-1;
}
3.1.6、判断栈空
int stackempty(seqstack *s)
{
return(s–>top==-1);
}
3.1.7、退栈
datatype pop(seqstack *s)
{
if (stackempty(s))
error(“stack underflow”);
x=s–>data[top];
s–>top--;
return(x)
//return(s–>data[s–>top--]);
}
3.1.8、取栈顶元素
Datatype stacktop(seqstack *s)
{
if(stackempty(s)
error(“stack is enpty”);
return s–>data[s–>top];
}
3.1.3 链栈栈的链式存储结构称为链栈，它是运算是受限的单链表，克插入和删除操作仅限制在表头位置上进行,由于只能在链表头部进行操作，故链表没有必要像单链表那样附加头结点。栈顶指针就是链表的头指针。 链栈的类型说明如下：
typedef struct stacknode{
datatype data
struct stacknode *next
}stacknode;
typedef struct { stacknode *top}
linkstack;
Void initstack(linkstack *p)
{
p–>top=null;
}
int stackempty(linkstack *p)
{
return p–>top==null;
}
Void push(linkstack *p,datatype x)
{
stacknode *q
q=(stacknode*)malloc(sizeof(stacknode));
q–>data=x;
q–>next=p–>top;
p–>top=p;
}
Datatype pop(linkstack *p)
{
datatype x;
stacknode *q=p–>top;
if(stackempty(p)
error(“stack underflow.”);
x=q–>data;
p–>top=q–>next;
free(q);
return x;
}
datatype stack top(linkstack *p)
{
if(stackempty(p))
error(“stack is empty.”);
return p–>top–>data;
}
3.2 栈的应用举例由于栈结构具有的后进先出的固有特性，
致使栈成为程序设计中常用的工具。以下是几个栈应用的例子。
3.2.1 数制转换十进制 N和其它进制数的转换是计算机实现计算的基本问题,其解决方法很多,其中一个简单算法基于下列原理,
N=(n div d)*d+n mod d
( 其中,div为整除运算,mod为求余运算 )
例如 (1348)10=(2504)8,其运算过程如下：
n n div 8 n mod 8
1348 168 4
168 21 0
21 2 5
2 0 2
void conversion( ) {
initstack(s);
scanf (“%”,n);
while(n){
push(s,n%8);
n=n/8;
}
while(! Stackempty(s)){
pop(s,e);
printf(“%d”,e);
}
}
3.2.2 括号匹配的检验假设表达式中充许括号嵌套,则检验括号是否匹配的方法可用,期待的急迫程度,这个概念来描述。例：
（（）（） （（）））
3.2.3 行编辑程序在编辑程序中，设立一个输入缓冲区，
用于接受用户输入的一行字符，然后逐行存入用户数据区。允许用户输入错误，并在发现有误时可以及时更正。
行编辑程序算法如下,
void lineedit( ){
initstack(s);
ch=gether( );
while(ch!=eof){
while(ch!=eof && ch!=?\n?){
switch(ch){
case?#?,pop(s,c);
case?@?,clearstack(s);
default,push(s,ch);
}
ch=getchar( );
}
clearstack(s);
if(ch!=eof)
ch=gethar( );
}
destroystack(s);
}
3.2.4 迷宫求解入口出口
3.4 队列
3.4.1 抽象数据类型队列的定义队列 (Queue)也是一种运算受限的线性表。它只允许在表的一端进行插入，而在另一端进行删除。
允许删除的一端称为队头 (front)，允许插入的一端称为队尾 (rear)。
例如：排队购物。操作系统中的作业排队。先进入队列的成员总是先离开队列。因此队列亦称作先进先出 (First In First Out)的线性表，简称 FIFO
表。
当队列中没有元素时称为空队列。在空队列中依次加入元素 a1,a2,… an之后,a1是队头元素,an是队尾元素。显然退出队列的次序也只能是 a1,a2,… an,
也就是说队列的修改是依先进先出的原则进行的。
下图是队列的示意图：
a1 a2 … an出队 入队队头 队尾队列的抽象数据定义见书Ｐ 59
3.4.2 循环队列－队列的顺序表示和实现队列的顺序存储结构称为顺序队列，顺序队列实际上是运算受限的顺序表，和顺序表一样，
顺序队列也是必须用一个向量空间来存放当前队列中的元素。由于队列的队头和队尾的位臵是变化的，因而要设两个指针和分别指示队头和队尾元素在队列中的位臵，它们的初始值地队列初始化时均应臵为０。入队时将新元素插入所指的位臵，然后将加１。出队时，删去所指的元素，然后将加１并返回被删元素。由此可见，当头尾指针相等时队列为空。在非空队列里，头指针始终指向队头元素，而尾指针始终指向队尾元素的下一位臵。
０ １ ２ ３ 0 1 2 3
Front
rear
a b c
Front rear
(a)队列初始为空 （ b） A,B,C入队
０ １ ２ ３ ０ １ ２ ３
b c
front rear front
rear
（ c) a出队 (d) b,c出队，队为空和栈类似，队列中亦有上溢和下溢现象。此外，
顺序队列中还存在,假上溢,现象。因为在入队和出队的操作中，头尾指针只增加不减小，致使被删除元素的空间永远无法重新利用。因此，尽管队列中实际的元素个数远远小于向量空间的规模，但也可能由于尾指针巳超出向量空间的上界而不能做入队操作。该现象称为假上溢。
为充分利用向量空间。克服上述假上溢现象的方法是将向量空间想象为一个首尾相接的圆环，并称这种向量为循环向量，存储在其中的队列称为循环队列（ Circular Queue)。在循环队列中进行出队、入队操作时，头尾指针仍要加 1，朝前移动。
只不过当头尾指针指向向量上界（ QueueSize-1）
时，其加 1操作的结果是指向向量的下界 0。
这种循环意义下的加 1操作可以描述为：
if(I+1==QueueSize)
i=0;
else
i++;
利用模运算可简化为,i=(i+1)%QueueSize
显然，因为循环队列元素的空间可以被利用，
除非向量空间真的被队列元素全部占用，否则不会上溢。因此，除一些简单的应用外，真正实用的顺序队列是循环队列。
如图所示：由于入队时尾指针向前追赶头指针，
出队时头指针向前追赶尾指针，故队空和队满时头尾指针均相等。因此，我们无法通过 front=rear
来判断队列“空”还是“满”。
解决此问题的方法至少有三种：
其一是另设一个布尔变量以匹别队列的空和满；
其二是少用一个元素的空间，约定入队前，测试尾指针在循环意义下加 1后是否等于头指针，若相等则认为队满（注意,rear所指的单元始终为空）；
其三是使用一个计数器记录队列中元素的总数
（实际上是队列长度）。下面我们用第三种方法实现循环队列上的六种基本操作，为此先给出循环队列的类型定义。
#define QueueSize 100
typedef char DataType;
typedef Struct{
int front;
int rear;
int count;
datatype data[queuesize]
}cirqueue;
（ 1）臵空队
void initqueue(cirqueue *q){
q–>front=q–>rear=0;
q–>count=0;
}
（ 2）判断队空
int queueempty(cirqueue *q) {
return q–>count==0;
}
（ 3）判断队满
int queuefull(cirqueue *q){
return q–>count==queuesize;
}
（ 4）入队
void enqueue(cirqueue *q,datatype x)
{
if(queuefull(q))
error(“queue overflow”);
q–>count++;
q–data[q–rear]=x;
q–rear=(q–rear+1)%queuesize;
}
（ 5）出队
datatype dequeue(cirqueue *q)
{
datatype temp;
if(queueempty(q))
error(“queue underflow”);
temp=q–>data[q–>front];
q–>count--;
q–front=(q–>front+1)%queuesize;
return temp;
}
（ 6）取头指针
datatype queuefront(cirqueue *q)
{
if(queueempty(q))
error(“queue is empty.”);
return q–>data[q–>front];
}
3.4.3 链队列
队列的链式存储结构简称为链队列，它是限制仅在表头删除和表尾插入的单链表。显然仅有单链表的头指针不便于在表尾做插入操作，
为此再增加一个尾指针，指向链表的最后一个结点。于是，一个链队列由一个头指针唯一确定。和顺序队列类似，我们也是将这两个指针封装在一起，将链队列的类型 LinkQueue定义为一个结构类型：
typedef struct queuenode{
datatype data;
struct queuenode *next;
}queuenode;
typedef struct{
queuenode *front;
queuenode *rear;
}linkqueue;
下面给出链队列上实现的基本运算：
void initqueue(linkqueue *q)
{
q–>front=q–>rear=null;
}
int queueempty(linkqueue *q)
{
return q–>front==null &&q–>rear==null;
}
void enqueue(linkqueue *q,datatype x)
{
queuenode *p
p=(queuenode * )malloc(sizeof(queuenode));
p–>data=x;
p–next=null;
if(queueempty(q))
q–>front=q–>rear=p;
else{
q–>rear–>next=p;
q–rear=p;
}
}
Datatype dequeue(linkqueue *q)
{
datatype x;
queuenode *p
if(queueempty(q))
error(“queue underflow”);
p=q–>front;
x=p–>data;
q–>front=p–>next;
if(q–>rear==p)
q–rear=null;
free(p);
return x;
}
datatype queuefront(linkqueue *q)
{
if(queueempty(q))
error(“queue is empty.”);
return q–>front–>data;
}
注意：在出队算法中，一般只需修改队头指针。
但当原队中只有一个结点时，该结点既是队头也是队尾，故删去此结点时亦需修改尾指针，
且删去此结点后队列变空。
习题
1、设将整数以万计,2,3,4依次进栈，但只要出栈时栈非空，则可将出栈操作按任何次序夹入其中，请回答下有问题：
（ 1）若入栈次序为 push(1),pop(),push(2，
push(3),pop(),pop( ),push(4),pop( )，
则出栈的数字序列为什么？
（ 2）能否得到出栈序列车员 423和平共处五项原则 432？并说明为什么不能得到或如何得到。
（ 3）请分析 1,2,3,4的 24种排列中，哪些序列可以通过相应的入出栈得到。
2、链栈中为何不设头指针？
3、循环队列的优点是什么？如何判断它的空和满？
4、设长度为 n的链队列用单循环链表表示，若只设头指针，则怎样进行入队和出队操作；若只设尾指针呢？
5、利用栈的基本操作，写一个返回栈 s中结点个数的算法 int stacksize(seqstack s)，并说明 s为何不用作为指针参数？
6、利用栈的基本操作，写一个将栈中所有结点均删除算法，并说明 S为何要作为指针参数？
7、用第二种方法，即少用一个元素空间的方法来区别循环队列的队空和队满，试设计臵空队、
判队空、判队满、出队、入队及取队头元素等六个基本操作。
8、假设循环队列只设 rear和 quelen来分别指示队尾元素的位臵和队中元素的个数，试给出判断此循环队列的队满条件，并写出相应的入队和出队算法，要求出队时需返回队头指针。
9、指出下列程序段的功能是什么？
(1) void demo1(seqstack *s){
int I;arr[64];n=0;
while (!stackempty(s)) arr[n++]=pos(s);
for(I=0;<n;I++) push(s,arr[I]);
}
(2) void demo2(seqstack *s,int m){
seqstack t; int i;
initstack(t);
while(! Stackempty(s))
if(I=pop(s)!=m) push(t,I);
While(! Stackempty(t)) {
i=pop(t);
push(s,I);
}
}
