第三章 栈和队列数据结构（ C描述）
3.1 栈
3.2 队 列退 出目 录
3.1 栈（ STACK）
3.1.1 栈的定义栈 (stack)---是限制线性表中元素的 插入和删除只能在线性表的同一端进行 的一种特殊线性表 。
允许插入和删除的一端,称为 栈顶 (Top)；
另一端为固定的一端,称为 栈底 (Bottom)。
3.1.1 栈的定义根据栈的定义可知，最先放入栈中元素在栈底，
最后放入的元素在栈顶，而删除元素刚好相反，
最后放入的元素最先删除，最先放入的元素最后删除。
也就是说，栈是一种后进先出 (Last In First Out)
的线性表，简称为 LIFO表。
3.1.1 栈的定义
a
n
...
a
2
a
1
栈顶 t o p
3.1.1 栈的定义举例 1：家里吃饭的碗，通常在洗干净后一个一个地落在一起存放，在使用时，若一个一个地拿，一定最先拿走最上面的那只碗，而最后拿出最下面的那只碗。
举例 2：在建筑工地上，使用的砖块从底往上一层一层地码放，在使用时，将从最上面一层一层地拿取。
3.1.2 栈的基本操作
1.初始化栈,INITSTACK(S)
将栈 S置为一个空栈 (不含任何元素 )。
2.进栈,PUSH(S,x )
将元素 X插入到栈 S中,也称为,入栈,,,插入,,,压入,。
3.出栈,POP(S,x )
删除栈 S中的栈顶元素,也称为,退栈,,,删除,,,弹出,。
4.取栈顶元素,GETTOP(S,x )
取栈 S中栈顶元素 。
5.判栈空,ISEMPTY(S)
判断栈 S是否为空,若为空,返回值为 TRUE,否则返回值为 FALSE。
3.1.2 栈的基本操作
6,清空栈,CLEARSTACK(S)
将栈置为空栈；
7、判栈满,ISFULL(S)
判断栈 S是否满，若已满，返回值为 TRUE，否则返回值为 FALSE
3.1.3 顺 序 栈是用一组连续的存储单元依次存放栈中的每个数据元素，并用起始端作为栈底。
定义由于栈操作的特殊性，附设一个栈顶指针 top
来动态地表示栈顶元素在顺序栈中的位置。
3.1.3 顺 序 栈类型定义如下所示：
#define TRUE 1
#define FALSE 0
#define MAXSIZE 50
typedef struct stack{
StackElementType elem[MAXSIZE];
int top; //栈顶指针
}SeqStack;
3.1.3 顺 序 栈
M A XS I Z E -- 1
,.,
1
0
t op= - 1
（ 1） 初始化栈
void initstack(Seqstack *s)
{
s->top=0;
}
顺序栈的基本操作
（ ２ ） 进栈
int push(Seqstack *s,stackelemtype x)
{
if (s->top= =maxsize-1} return(FALSE);
else
{ s->top++;
s->elem[s->top]=x;
return(TRUE);
}
}
（ ３ ） 退栈
int pop(Seqstack *s,stackelemtype *x)
{
if (s->top= =-1) return(FALSE);
else
{ *x= s->elem[s->top];
s->top--;
return(TRUE); }
}
（ ４ ） 取栈顶元素
int Gettop(Seqstack *s,stackelemtype *x)
{
if (s->top= =-1) return(FALSE);
else
{ *x= s->elem[s->top];
return(TRUE);
}
}
（ 5） 判栈空否
int IsEmpty(Seqstack *s)
{
return (s->top= =-1? TRUE,FALSE）
}
（ 6） 判栈满
int IsFull(Seqstack *s)
{
return (s->top= =MAXSIZE-1? TRUE,FALSE）
}
有时,一个程序设计中,需要 使用多个同一类型的栈,这时候,可能会产生一个栈空间过小,容量发生溢出,而另一个栈空间过大,造成大量存储单元浪费的现象 。 为了充分利用各个栈的存储空间,这时可以采用多个栈共享存储单元,即 给多个栈分配一个足够大的存储空间,让多个栈实现存储空间优势互补 。
栈的共享存储单元栈 1 顶 栈 2 顶栈 1 底 栈 2 底两个栈共享存储单元示意图两个栈共享存储单元可用如下 C语句描述：
#define M 100
Typedef struct
{ StackElementType stack[M];
int top[2] ; //两个栈的栈顶指针 top[0],top[1]
}DqStack;
初始化操作：
DqStack *s;
s->top[0]=-1;
s->top[1]=M;
（ 1） 两个栈共享存储单元的进栈算法
int push(DqStack *s,stackelemtype x,int i)
//将元素 x压入到以 S的 i号栈中
{ if (s->top[0]+1==s->top[1]) return(FALSE);
else if (i==0) { s->top[0]++;
s->stack[s->top[0]]=x;}
else if(i= =1) { s->top[1]--;
s->stack[s->top[1]]=x;}
else return(FALSE);
return(TRUE);
}
（ 2） 两个栈共享存储单元的退栈算法
int pop(DqStack *s,stackelemtype *x,int i)
//将以 s为栈空间的栈中第 i个栈进行退栈
{
if ((i= =0)&&(s->top[0]= =-1)) return(FALSE);
else { *x= s->stack[s->top[0]];
s->top[0]--; }
if ((i= =1)&&(s->top[1]= =M) return(FALSE);
else { *x= s->stack[s->top[1]];
s->top[0]++; }
return(TRUE);
}
3.1.4 链 栈若是栈中元素的数目变化范围较大或不清楚栈元素的数目，就应该考虑使用链式存储结构。人们将用链式存储结构表示的栈称作,链栈” 。
它是一种限制运算的链表，即规定链表中的插入和删除运算只能在链表开头进行。所以链表的表头指针就作为栈顶指针 。
3.1.4 链 栈
a n
a n - 1
t op
栈顶 栈底
…… a 1 ^
链栈结构示意图
3.1.4 链 栈定义如下：
typedef struct node
{ StackElementType data;
struct node *next;
} LinkStackNode,*LinkStack;
（ 1） 栈初始化
void initstack(LinkStack top)
{ top->next=NULL;}
链栈的运算
（ 2）进栈运算
int push(LinkStack top,StackElementType x)
{ LinkStackNode *temp;
temp=(LinkStackNode *)malloc(sizeof(LinkStackNode));
if(temp= =NULL) return(FALSE);
temp->data=x;
temp->next= top->next;
top->next=temp;
return(TRUE);
}
（ 3） 退栈运算
int pop(LinkStack top,StackElementType *x)
{ LinkStackNode *temp;
temp=top->next;
if(temp= =NULL) return(FALSE);
top->next=temp->next;
*x=temp->data;
free(temp);
return(TRUE);
}
（ 4） 取栈顶元素
int Gettop(LinkStack top,StackElementType *x)
{
if(top->next!=NULL)
{ *x=top->next->data;
return(TRUE);
else
return(FALSE);
}
（ 5） 判栈空
int Isempty(LinkStack top)
{
if(top->next==NULL)
return(TRUE);
else
return(FALSE);
}
3.1.6 栈的应用栈在日常生活中和计算机程序设计中有着许多应用,
下面仅介绍栈在计算机中的应用 。
1,表达式的求值算术表达式中包含了 算术运算符和算术量 (常量、
变量、函数 )，而运算符之间又存在着 优先级,不能简单地进行从左到右运算，编译程序在求值时，不能简单从左到右运算，必须先算运算级别高的，再算运算级别低的，同一级运算才从左到右。
因此,要实现表达式求值,必须设置两个栈,一个栈存放运算符 (OVS),另一个栈存放操作数 （ 算术量 ） (OPTR),在进行表达式求值时,编译程序从左到右扫描,
遇到操作数,一律进入操作数栈 OVS；
遇到运算符,则应与运算符栈的栈顶元素比较,
若运算符优先级高于栈顶则进栈 OPTR；
否则退栈,退栈后,在操作数栈中退出两个元素 (先退出在运算符右,后退出在运算符左 ),然后用运算符栈中退出的栈顶元素进行运算,运算的结果存入操作数栈中 。
直到扫描完毕。这时 运算符栈为空，操作数栈中只有一个元素，即为运算的结果 。
例：求无括号的算术表达式 1 + 2 * 3 – 4 / 2# 的值，
运算符优先级,# + - * / * *
① ② ③ ④
栈的变化如下：
步骤 操作数栈 运算符栈 说明开始 两栈均为空
1 1 1进入操作数栈
+进入运算符栈
2进入操作数栈
*进入运算符栈
3进入操作数栈退栈
2*3进入操作数栈退栈
1+6进入操作数栈
2
3
4
5
6
7
8
9
1 +
1 2 +
1 2 +
1
1
1
7
+
*
2 3
6
+ *
+
步骤 操作数栈 运算符栈 说明
10 7 -进入运算符栈
4进入操作数栈
/进入运算符栈
2进入操作数栈
#进入运算符栈，退栈
4/2进入操作数栈退栈
7-2进入操作数栈
11
12
13
14
15
16
17
7 4 -
7 4 - /
7 4 2 - /
7
7 2 -
-
-
5
带括号的算术表达式：
先左后右；
先乘除，后加减；
先括号内，后括号外；
（见表 3-1 算符之间的优先关系）
2,函数的嵌套调用在函数嵌套调用中,一个函数的执行没有结束,
又开始另一个函数的执行,因此必须用栈来保存函数中断的地址,以便调用返回时能从断点继续往下执行 。
例：设有一个主程序,它调用函数 a,函数 a又调用函数 b,函数 b又调用函数 c,（ 见下页 ）,其中 r,s，
t分别表示中断地址,我们可以用一个栈来描述调用情况 （ 见下页 ） 。
主函数 a 函数 b 函数 c 函数
r s t
函数的嵌套调用与返回
s
r
t
s
r
r
( a ) 调用 a 函数,r 进栈 ( b ) 调用 b 函数,s 进栈 ( c) 调用 c 函数,t 进栈
r
s
r
( d) 返回 b 函数,t 退栈 ( e) 返回 a 函数,s 退栈 ( f ) 返回主程序,r 退栈函数嵌套调用栈变化示意图
3,函数的递归调用函数的递归调用也是一种嵌套,故也必须用栈来保存断点信息,但递归调用相当于同一个函数的嵌套调用,故除了保存断点信息外,还必须保存每一层的参数,局部变量等 。
例 3-7 求 n! 可用递归函数描述如下：
1 n=0
n! ＝
n*(n-1)! n>0
4*3!
3*2!
4*3!
2*1!
3*2!
4*3!
1*0!
2*1!
3*2!
4*3!
(a) (b) (c) (d) (e)
1*1
2*1!
3*2!
4*3!
2*1
3*2!
4*3!
3*2
4*3!
4*6
( f ) ( g) ( h) ( i)
递归调用中栈变化示意图例,Hanoi塔问题。 (Page63)
3.2 队列
3.2.1 队列的定义仅允许在一端进行插入，另一端进行删除的线性表，称为队列 (queue)。允许插入的一端称为 队尾
(rear)，允许删除的一端称为 队头（ frort） 。
队列是一种 先进先出 （ First In First Out） 的特殊线性表,或称 FIFO表 。
若队列中没有任何元素，则称为空队列，否则称为非空队列。
队列的描述可以用如图 3-9的方式所描述 。
a 1 a 2 ….,a n 入队队头 队尾出队图 3 - 9 队 列示意图
3.2.2 队列的基本运算
1,初始化队列 INIQUEUE(&Q)
将队列 Q设置成一个空队列 。
2,入队列 ENQUEUE(&Q,X)
将元素 X插入到队尾中,也称,进队,,,插入,。
3,出队列 DLQUEUE(&Q,&x)
将队列 Q的队头元素删除,也称,退队,,,删除,。
4,取队头元素 GETHEAD(Q,&x)
得到队列 Q的队头元素之值 。
5,判队空 IsEMPTY(Q)
判断队列 Q是否为空,若为空返回 1,否则返回 0。
3.2.3 循环队列
1,队列的顺序存储数据类型描述
#define MAXSIZE 50
Typedef struct
{ QueueElementType element[MAXSIZE];
int front; //队头指针
int rear; //队尾指针
};
2,顺序队列将队列中元素全部存入一个一维数组中,数组的低下标一端为队头,高下标一端为队尾，将这样的队列看成是顺序队列若一维数组中所有位置上都被元素装满，称为队满，即尾指针 rear指向一维数组最后,而头指针指向一维数组开头，称为队满。
但有可能出现这样情况,尾指针指向一维数组最后,但前面有很多元素已经出队,即空出很多位置,
这时要插入元素,仍然会发生溢出 。 例如,在图 3-13(d)
中,若队列的最大容量 maxsize=6,此时,front=rear=6，
再进队时将发生溢出 。 我们将这种溢出称为,假溢出,。
要克服,假溢出,,可以将整个队列中元素向前移动,
直到头指针 front为零,或者每次出队时,都将队列中元素前移一个位置 。 因此,顺序队列的队满判定条件为 rear=maxsize。 但是,在顺序队列中,这些克服假溢出的方法都会引起大量元素的移动,花费大量的时间,
所以在实际应用中很少采用,一般采用下面的循环队列形式 。
3,循环队列为了克服顺序队列中假溢出,通常将一维数组
queue[0]到 q[maxsize-1]看成是一个首尾相接的圆环,
即 queue[0]与 queue[maxsize-1]相接在一起 。 将这种形式的顺序队列称为循环队列,见图 3-11。
队头队尾
a
n - 1
a
3
a
2
a
1
a
n
a
i
……
……
图 3 - 11 循环队列示意图在循环队列中,若 front=rear,则称为队空,若
(rear+1)%maxsize=front,则称为队满,这时,循环队列中能装入的元素个数为 maxsize-1,即浪费一个存储单元,
但是这样可以给操作带来较大方便 。
4,循环队列上五种运算实现
（ 1） 队列初始化
Void INIQUEUE(seqqueue &q )
{ q.front=q.rear=maxsize-1;
}
(2) 进队列
Void enqueue (seqqueue &q,elemtype x)
{
if ((q.rear+1)%maxsize = = q.front) cout<<”overflow”;
else { q.rear=(q.rear+1)%maxsize;
q.queue[q.rear]=x;
}
}
(3) 出队列
Void dlqueue(seqqueue &q )
{
if (q.rear= =q.front) cout<<”underflow”;
else
q.front =(q.front+1)%maxsize;
}
(4) 取队头元素 （ 注意得到的应为头指针后面一个位置值 ）
elemtype gethead(seqqueue q )
{ if (q.rear= =q.front)
{ cout<<”underflow”； return NULL;}
else return q.queue[(q.front+1)%maxsize];
}
(5) 判队列空否
int empty(seqqueue q )
{ if (q.rear= =q.front) reurn 1;
else return 0; }
3.2.5 链队列
1 。 链队列的数据类型描述队列的链式存储，称为链队列，与前面介绍的单链表类似，但为了使头指针，尾指针统一起来，另外定义一种数据类型如下。
Struct link //定义单链表数据类型
{ elemtype data;
link *next;};
struct linkqueue //定义链队列数据类型
{ link *front,*rear; //定义头指针和尾指针
};
r e a r
头 ^
f r o n t
a n ^ 头
f r o n t
a 1 …… a 2
r e a r
（ a ）空链队列 ( b ) 非空链队链队列示意图
2 。 链队列上的基本运算同样，链队列上也可以给出五种运算如下：
（ 1） 链队列上的初始化
void INIQUEUE(linkqueue( &s)
{ link *p;
p=new link;
p->next=NULL;
s.front=p;
s.rear=p;
}
(2) 入队列
void push(linkqueue &s,elemtype x)
{
link *p;
p=new link;
p->data=x;
p->next=s.rear->next;
s.rear->next=p;
s.rear=p;
}
(3) 判队空
int empty(linkqueue s)
{ if (s.front= =s.rear) return 1;
else return 0;
}
(4) 取队头元素
elemtype gethead(linkqueue s)
{ if (s.front= =s.rear) return NULL;
else retuen s.front->next->data;
}
(5) 出队列
void pop(linkqueue &s)
{ link *p;
p=s.front->next;
if (p->next= =NULL) //链队列中只有一个队头元素,
无其它元素
{s.front->next=NULL;
s.rear=s.front;}
else
s.front->next =p->next;
delete (p);}
从上述出队列算法中可知,若链队列中只有一个元素时,需作特殊处理 (用 if语句判断 ),修改队尾指针 。 为了避免修改队尾指针,我们可以采用一种改进的出队列算法 。 其基本思想是：出队列时,修改头指针,删除头结点而非队头结点,这时,将队头结点成为新的头结点,队列中第二个结点成为队头结点 。 这时,不管队列中有多少个元素,都不需作特殊处理 （ 不需用 if
语句来判断 ）,这种改进的算法如下：
void pop(linkqueue &s)
{ link *p;
p=s.front;
s.front=p->next;
delete (p);}
3.2.6 队列的应用队列在日常生活中和计算机程序设计中,有着非常重要的作用,在此,仅举出两个方面例子来说明它,其它应用在后面章节中将会遇到 。
第一个例子就是 CPU资源的竞争问题 。 在具有多个终端的计算机系统中,有多个用户需要使用 CPU各自运行自己的程序,它们分别通过各自终端向操作系统提出使用 CPU的请求,操作系统按照每个请求在时间上的先后顺序,将其排成一个队列,每次把 CPU分配给队头用户使用,当相应的程序运行结束,则令其出队,再把 CPU分配给新的队头用户,直到所有用户任务处理完毕 。
第二个例子就是主机与外部设备之间速度不匹配的问题 。 以主机和打印机为例来说明,主机输出数据给打印机打印,主机输出数据的速度比打印机打印的速度要快得多,若直接把输出的数据送给打印机打印,由于速度不匹配,显然是不行的 。 所以解决的方法是设置一个打印数据缓冲区,主机把要打印输出的数据依此写如到这个缓冲区中,写满后就暂停输出,继而去做其它的事情,打印机就从缓冲区中按照先进先出的原则依次取出数据并打印,打印完后再向主机发出请求,主机接到请求后再向缓冲区写入打印数据,这样利用队列既保证了打印数据的正确,又使主机提高了效率 。
3.1 栈
3.2 队 列退 出目 录
3.1 栈（ STACK）
3.1.1 栈的定义栈 (stack)---是限制线性表中元素的 插入和删除只能在线性表的同一端进行 的一种特殊线性表 。
允许插入和删除的一端,称为 栈顶 (Top)；
另一端为固定的一端,称为 栈底 (Bottom)。
3.1.1 栈的定义根据栈的定义可知，最先放入栈中元素在栈底，
最后放入的元素在栈顶，而删除元素刚好相反，
最后放入的元素最先删除，最先放入的元素最后删除。
也就是说，栈是一种后进先出 (Last In First Out)
的线性表，简称为 LIFO表。
3.1.1 栈的定义
a
n
...
a
2
a
1
栈顶 t o p
3.1.1 栈的定义举例 1：家里吃饭的碗，通常在洗干净后一个一个地落在一起存放，在使用时，若一个一个地拿，一定最先拿走最上面的那只碗，而最后拿出最下面的那只碗。
举例 2：在建筑工地上，使用的砖块从底往上一层一层地码放，在使用时，将从最上面一层一层地拿取。
3.1.2 栈的基本操作
1.初始化栈,INITSTACK(S)
将栈 S置为一个空栈 (不含任何元素 )。
2.进栈,PUSH(S,x )
将元素 X插入到栈 S中,也称为,入栈,,,插入,,,压入,。
3.出栈,POP(S,x )
删除栈 S中的栈顶元素,也称为,退栈,,,删除,,,弹出,。
4.取栈顶元素,GETTOP(S,x )
取栈 S中栈顶元素 。
5.判栈空,ISEMPTY(S)
判断栈 S是否为空,若为空,返回值为 TRUE,否则返回值为 FALSE。
3.1.2 栈的基本操作
6,清空栈,CLEARSTACK(S)
将栈置为空栈；
7、判栈满,ISFULL(S)
判断栈 S是否满，若已满，返回值为 TRUE，否则返回值为 FALSE
3.1.3 顺 序 栈是用一组连续的存储单元依次存放栈中的每个数据元素，并用起始端作为栈底。
定义由于栈操作的特殊性，附设一个栈顶指针 top
来动态地表示栈顶元素在顺序栈中的位置。
3.1.3 顺 序 栈类型定义如下所示：
#define TRUE 1
#define FALSE 0
#define MAXSIZE 50
typedef struct stack{
StackElementType elem[MAXSIZE];
int top; //栈顶指针
}SeqStack;
3.1.3 顺 序 栈
M A XS I Z E -- 1
,.,
1
0
t op= - 1
（ 1） 初始化栈
void initstack(Seqstack *s)
{
s->top=0;
}
顺序栈的基本操作
（ ２ ） 进栈
int push(Seqstack *s,stackelemtype x)
{
if (s->top= =maxsize-1} return(FALSE);
else
{ s->top++;
s->elem[s->top]=x;
return(TRUE);
}
}
（ ３ ） 退栈
int pop(Seqstack *s,stackelemtype *x)
{
if (s->top= =-1) return(FALSE);
else
{ *x= s->elem[s->top];
s->top--;
return(TRUE); }
}
（ ４ ） 取栈顶元素
int Gettop(Seqstack *s,stackelemtype *x)
{
if (s->top= =-1) return(FALSE);
else
{ *x= s->elem[s->top];
return(TRUE);
}
}
（ 5） 判栈空否
int IsEmpty(Seqstack *s)
{
return (s->top= =-1? TRUE,FALSE）
}
（ 6） 判栈满
int IsFull(Seqstack *s)
{
return (s->top= =MAXSIZE-1? TRUE,FALSE）
}
有时,一个程序设计中,需要 使用多个同一类型的栈,这时候,可能会产生一个栈空间过小,容量发生溢出,而另一个栈空间过大,造成大量存储单元浪费的现象 。 为了充分利用各个栈的存储空间,这时可以采用多个栈共享存储单元,即 给多个栈分配一个足够大的存储空间,让多个栈实现存储空间优势互补 。
栈的共享存储单元栈 1 顶 栈 2 顶栈 1 底 栈 2 底两个栈共享存储单元示意图两个栈共享存储单元可用如下 C语句描述：
#define M 100
Typedef struct
{ StackElementType stack[M];
int top[2] ; //两个栈的栈顶指针 top[0],top[1]
}DqStack;
初始化操作：
DqStack *s;
s->top[0]=-1;
s->top[1]=M;
（ 1） 两个栈共享存储单元的进栈算法
int push(DqStack *s,stackelemtype x,int i)
//将元素 x压入到以 S的 i号栈中
{ if (s->top[0]+1==s->top[1]) return(FALSE);
else if (i==0) { s->top[0]++;
s->stack[s->top[0]]=x;}
else if(i= =1) { s->top[1]--;
s->stack[s->top[1]]=x;}
else return(FALSE);
return(TRUE);
}
（ 2） 两个栈共享存储单元的退栈算法
int pop(DqStack *s,stackelemtype *x,int i)
//将以 s为栈空间的栈中第 i个栈进行退栈
{
if ((i= =0)&&(s->top[0]= =-1)) return(FALSE);
else { *x= s->stack[s->top[0]];
s->top[0]--; }
if ((i= =1)&&(s->top[1]= =M) return(FALSE);
else { *x= s->stack[s->top[1]];
s->top[0]++; }
return(TRUE);
}
3.1.4 链 栈若是栈中元素的数目变化范围较大或不清楚栈元素的数目，就应该考虑使用链式存储结构。人们将用链式存储结构表示的栈称作,链栈” 。
它是一种限制运算的链表，即规定链表中的插入和删除运算只能在链表开头进行。所以链表的表头指针就作为栈顶指针 。
3.1.4 链 栈
a n
a n - 1
t op
栈顶 栈底
…… a 1 ^
链栈结构示意图
3.1.4 链 栈定义如下：
typedef struct node
{ StackElementType data;
struct node *next;
} LinkStackNode,*LinkStack;
（ 1） 栈初始化
void initstack(LinkStack top)
{ top->next=NULL;}
链栈的运算
（ 2）进栈运算
int push(LinkStack top,StackElementType x)
{ LinkStackNode *temp;
temp=(LinkStackNode *)malloc(sizeof(LinkStackNode));
if(temp= =NULL) return(FALSE);
temp->data=x;
temp->next= top->next;
top->next=temp;
return(TRUE);
}
（ 3） 退栈运算
int pop(LinkStack top,StackElementType *x)
{ LinkStackNode *temp;
temp=top->next;
if(temp= =NULL) return(FALSE);
top->next=temp->next;
*x=temp->data;
free(temp);
return(TRUE);
}
（ 4） 取栈顶元素
int Gettop(LinkStack top,StackElementType *x)
{
if(top->next!=NULL)
{ *x=top->next->data;
return(TRUE);
else
return(FALSE);
}
（ 5） 判栈空
int Isempty(LinkStack top)
{
if(top->next==NULL)
return(TRUE);
else
return(FALSE);
}
3.1.6 栈的应用栈在日常生活中和计算机程序设计中有着许多应用,
下面仅介绍栈在计算机中的应用 。
1,表达式的求值算术表达式中包含了 算术运算符和算术量 (常量、
变量、函数 )，而运算符之间又存在着 优先级,不能简单地进行从左到右运算，编译程序在求值时，不能简单从左到右运算，必须先算运算级别高的，再算运算级别低的，同一级运算才从左到右。
因此,要实现表达式求值,必须设置两个栈,一个栈存放运算符 (OVS),另一个栈存放操作数 （ 算术量 ） (OPTR),在进行表达式求值时,编译程序从左到右扫描,
遇到操作数,一律进入操作数栈 OVS；
遇到运算符,则应与运算符栈的栈顶元素比较,
若运算符优先级高于栈顶则进栈 OPTR；
否则退栈,退栈后,在操作数栈中退出两个元素 (先退出在运算符右,后退出在运算符左 ),然后用运算符栈中退出的栈顶元素进行运算,运算的结果存入操作数栈中 。
直到扫描完毕。这时 运算符栈为空，操作数栈中只有一个元素，即为运算的结果 。
例：求无括号的算术表达式 1 + 2 * 3 – 4 / 2# 的值，
运算符优先级,# + - * / * *
① ② ③ ④
栈的变化如下：
步骤 操作数栈 运算符栈 说明开始 两栈均为空
1 1 1进入操作数栈
+进入运算符栈
2进入操作数栈
*进入运算符栈
3进入操作数栈退栈
2*3进入操作数栈退栈
1+6进入操作数栈
2
3
4
5
6
7
8
9
1 +
1 2 +
1 2 +
1
1
1
7
+
*
2 3
6
+ *
+
步骤 操作数栈 运算符栈 说明
10 7 -进入运算符栈
4进入操作数栈
/进入运算符栈
2进入操作数栈
#进入运算符栈，退栈
4/2进入操作数栈退栈
7-2进入操作数栈
11
12
13
14
15
16
17
7 4 -
7 4 - /
7 4 2 - /
7
7 2 -
-
-
5
带括号的算术表达式：
先左后右；
先乘除，后加减；
先括号内，后括号外；
（见表 3-1 算符之间的优先关系）
2,函数的嵌套调用在函数嵌套调用中,一个函数的执行没有结束,
又开始另一个函数的执行,因此必须用栈来保存函数中断的地址,以便调用返回时能从断点继续往下执行 。
例：设有一个主程序,它调用函数 a,函数 a又调用函数 b,函数 b又调用函数 c,（ 见下页 ）,其中 r,s，
t分别表示中断地址,我们可以用一个栈来描述调用情况 （ 见下页 ） 。
主函数 a 函数 b 函数 c 函数
r s t
函数的嵌套调用与返回
s
r
t
s
r
r
( a ) 调用 a 函数,r 进栈 ( b ) 调用 b 函数,s 进栈 ( c) 调用 c 函数,t 进栈
r
s
r
( d) 返回 b 函数,t 退栈 ( e) 返回 a 函数,s 退栈 ( f ) 返回主程序,r 退栈函数嵌套调用栈变化示意图
3,函数的递归调用函数的递归调用也是一种嵌套,故也必须用栈来保存断点信息,但递归调用相当于同一个函数的嵌套调用,故除了保存断点信息外,还必须保存每一层的参数,局部变量等 。
例 3-7 求 n! 可用递归函数描述如下：
1 n=0
n! ＝
n*(n-1)! n>0
4*3!
3*2!
4*3!
2*1!
3*2!
4*3!
1*0!
2*1!
3*2!
4*3!
(a) (b) (c) (d) (e)
1*1
2*1!
3*2!
4*3!
2*1
3*2!
4*3!
3*2
4*3!
4*6
( f ) ( g) ( h) ( i)
递归调用中栈变化示意图例,Hanoi塔问题。 (Page63)
3.2 队列
3.2.1 队列的定义仅允许在一端进行插入，另一端进行删除的线性表，称为队列 (queue)。允许插入的一端称为 队尾
(rear)，允许删除的一端称为 队头（ frort） 。
队列是一种 先进先出 （ First In First Out） 的特殊线性表,或称 FIFO表 。
若队列中没有任何元素，则称为空队列，否则称为非空队列。
队列的描述可以用如图 3-9的方式所描述 。
a 1 a 2 ….,a n 入队队头 队尾出队图 3 - 9 队 列示意图
3.2.2 队列的基本运算
1,初始化队列 INIQUEUE(&Q)
将队列 Q设置成一个空队列 。
2,入队列 ENQUEUE(&Q,X)
将元素 X插入到队尾中,也称,进队,,,插入,。
3,出队列 DLQUEUE(&Q,&x)
将队列 Q的队头元素删除,也称,退队,,,删除,。
4,取队头元素 GETHEAD(Q,&x)
得到队列 Q的队头元素之值 。
5,判队空 IsEMPTY(Q)
判断队列 Q是否为空,若为空返回 1,否则返回 0。
3.2.3 循环队列
1,队列的顺序存储数据类型描述
#define MAXSIZE 50
Typedef struct
{ QueueElementType element[MAXSIZE];
int front; //队头指针
int rear; //队尾指针
};
2,顺序队列将队列中元素全部存入一个一维数组中,数组的低下标一端为队头,高下标一端为队尾，将这样的队列看成是顺序队列若一维数组中所有位置上都被元素装满，称为队满，即尾指针 rear指向一维数组最后,而头指针指向一维数组开头，称为队满。
但有可能出现这样情况,尾指针指向一维数组最后,但前面有很多元素已经出队,即空出很多位置,
这时要插入元素,仍然会发生溢出 。 例如,在图 3-13(d)
中,若队列的最大容量 maxsize=6,此时,front=rear=6，
再进队时将发生溢出 。 我们将这种溢出称为,假溢出,。
要克服,假溢出,,可以将整个队列中元素向前移动,
直到头指针 front为零,或者每次出队时,都将队列中元素前移一个位置 。 因此,顺序队列的队满判定条件为 rear=maxsize。 但是,在顺序队列中,这些克服假溢出的方法都会引起大量元素的移动,花费大量的时间,
所以在实际应用中很少采用,一般采用下面的循环队列形式 。
3,循环队列为了克服顺序队列中假溢出,通常将一维数组
queue[0]到 q[maxsize-1]看成是一个首尾相接的圆环,
即 queue[0]与 queue[maxsize-1]相接在一起 。 将这种形式的顺序队列称为循环队列,见图 3-11。
队头队尾
a
n - 1
a
3
a
2
a
1
a
n
a
i
……
……
图 3 - 11 循环队列示意图在循环队列中,若 front=rear,则称为队空,若
(rear+1)%maxsize=front,则称为队满,这时,循环队列中能装入的元素个数为 maxsize-1,即浪费一个存储单元,
但是这样可以给操作带来较大方便 。
4,循环队列上五种运算实现
（ 1） 队列初始化
Void INIQUEUE(seqqueue &q )
{ q.front=q.rear=maxsize-1;
}
(2) 进队列
Void enqueue (seqqueue &q,elemtype x)
{
if ((q.rear+1)%maxsize = = q.front) cout<<”overflow”;
else { q.rear=(q.rear+1)%maxsize;
q.queue[q.rear]=x;
}
}
(3) 出队列
Void dlqueue(seqqueue &q )
{
if (q.rear= =q.front) cout<<”underflow”;
else
q.front =(q.front+1)%maxsize;
}
(4) 取队头元素 （ 注意得到的应为头指针后面一个位置值 ）
elemtype gethead(seqqueue q )
{ if (q.rear= =q.front)
{ cout<<”underflow”； return NULL;}
else return q.queue[(q.front+1)%maxsize];
}
(5) 判队列空否
int empty(seqqueue q )
{ if (q.rear= =q.front) reurn 1;
else return 0; }
3.2.5 链队列
1 。 链队列的数据类型描述队列的链式存储，称为链队列，与前面介绍的单链表类似，但为了使头指针，尾指针统一起来，另外定义一种数据类型如下。
Struct link //定义单链表数据类型
{ elemtype data;
link *next;};
struct linkqueue //定义链队列数据类型
{ link *front,*rear; //定义头指针和尾指针
};
r e a r
头 ^
f r o n t
a n ^ 头
f r o n t
a 1 …… a 2
r e a r
（ a ）空链队列 ( b ) 非空链队链队列示意图
2 。 链队列上的基本运算同样，链队列上也可以给出五种运算如下：
（ 1） 链队列上的初始化
void INIQUEUE(linkqueue( &s)
{ link *p;
p=new link;
p->next=NULL;
s.front=p;
s.rear=p;
}
(2) 入队列
void push(linkqueue &s,elemtype x)
{
link *p;
p=new link;
p->data=x;
p->next=s.rear->next;
s.rear->next=p;
s.rear=p;
}
(3) 判队空
int empty(linkqueue s)
{ if (s.front= =s.rear) return 1;
else return 0;
}
(4) 取队头元素
elemtype gethead(linkqueue s)
{ if (s.front= =s.rear) return NULL;
else retuen s.front->next->data;
}
(5) 出队列
void pop(linkqueue &s)
{ link *p;
p=s.front->next;
if (p->next= =NULL) //链队列中只有一个队头元素,
无其它元素
{s.front->next=NULL;
s.rear=s.front;}
else
s.front->next =p->next;
delete (p);}
从上述出队列算法中可知,若链队列中只有一个元素时,需作特殊处理 (用 if语句判断 ),修改队尾指针 。 为了避免修改队尾指针,我们可以采用一种改进的出队列算法 。 其基本思想是：出队列时,修改头指针,删除头结点而非队头结点,这时,将队头结点成为新的头结点,队列中第二个结点成为队头结点 。 这时,不管队列中有多少个元素,都不需作特殊处理 （ 不需用 if
语句来判断 ）,这种改进的算法如下：
void pop(linkqueue &s)
{ link *p;
p=s.front;
s.front=p->next;
delete (p);}
3.2.6 队列的应用队列在日常生活中和计算机程序设计中,有着非常重要的作用,在此,仅举出两个方面例子来说明它,其它应用在后面章节中将会遇到 。
第一个例子就是 CPU资源的竞争问题 。 在具有多个终端的计算机系统中,有多个用户需要使用 CPU各自运行自己的程序,它们分别通过各自终端向操作系统提出使用 CPU的请求,操作系统按照每个请求在时间上的先后顺序,将其排成一个队列,每次把 CPU分配给队头用户使用,当相应的程序运行结束,则令其出队,再把 CPU分配给新的队头用户,直到所有用户任务处理完毕 。
第二个例子就是主机与外部设备之间速度不匹配的问题 。 以主机和打印机为例来说明,主机输出数据给打印机打印,主机输出数据的速度比打印机打印的速度要快得多,若直接把输出的数据送给打印机打印,由于速度不匹配,显然是不行的 。 所以解决的方法是设置一个打印数据缓冲区,主机把要打印输出的数据依此写如到这个缓冲区中,写满后就暂停输出,继而去做其它的事情,打印机就从缓冲区中按照先进先出的原则依次取出数据并打印,打印完后再向主机发出请求,主机接到请求后再向缓冲区写入打印数据,这样利用队列既保证了打印数据的正确,又使主机提高了效率 。
