武汉理工大学华夏学院 -信息工程系第三章 栈与队列
3.1 概述栈 与 队列 是两种特殊的线性表。即,在一般线性表的操作时,插入或删除结点的位置是任意的,在表的中间或两端都可以进行插入或删除操作,这样,每进行一个结点的插入或删除时必须先要定位(确定其被执行操作结点的地址),因此实现操作比较费时。
而作为限定性的线性表 — 栈和队列,其主要特点是限定了操作位置,即 不能随意在表的任意结点上进行插入或删除操作而只能在表的一端或两端进行操作,
这样节省了定位时间并有特定规则。
武汉理工大学华夏学院 -信息工程系二 队列它是一种只能在 表的一端进行插入(称为进队)
操作,表的另一端进行删除(称为出队)操作 的线性表,显然,这是一种 先进先出 型结构。
栈与队列在许多求解非数值计算问题的程序中要用到,在很多场合对各数据的处理有先后顺序要求时,
经常使用栈或队列作为数据的暂存器来实现,当先产生的数据先处理,后产生的数据后处理时,则利用队列作为暂存器实现;若先产生的数据后处理,后产生的数据先处理时,则利用栈作为暂存器实现 。
一 栈它是一种只能在 表的一端 进行 插入 (称为 进栈 )
或 删除 (称为 出栈 )操作的线性表,显然,这是一种先进后出 或 后进先出型 结构的线性表。
武汉理工大学华夏学院 -信息工程系栈与队列有 顺序存储结构 和 链式存储结构两种。用顺序存储的方法存储的栈或队列称为顺序栈或顺序队列;
用链式存储的方法存储的栈或队列称为链式栈或链式队列。
下面分别阐述 。
三、栈与队列的存储结构武汉理工大学华夏学院 -信息工程系一、顺序栈
1,定义 用顺序方法存储的栈称为顺序栈。
2,术语栈顶 允许进行操作的一端,称为栈顶。
栈底 不允许进行操作的一端,称为栈底。
栈指针 指向栈顶元素位置的一个整型变量,称为栈指针。一般用 top表示。
空栈 栈中无元素的栈即栈指针指向零,即 top=0
时的栈,称为空栈。
3.2 栈武汉理工大学华夏学院 -信息工程系
3,顺序栈的描述顺序栈一般用一个一维数组进行描述,
且定义一个整型变量 top作为栈指针。其说明如下:
定义的栈结构如图 3 1所示 。
用 C语言 描述为,
#define n0 50
#define datatype
datatype s[no];
int top;
武汉理工大学华夏学院 -信息工程系
A
3
n0
栈顶图 3-1顺序栈示意图
B
C
D
·
·
·
栈底进栈
2
1
0
出栈
top 3
武汉理工大学华夏学院 -信息工程系
4.顺序栈的操作
(1)构造一个空栈设置(定义)一个数组后,将栈指针置为零既可。 top=- 1
( 2)判断一个栈是否为空,top==- 1?
( 3)判断一个栈是否为满:
top== n0- 1?
( 4)取栈顶元素,w= s[top]
武汉理工大学华夏学院 -信息工程系
( 5) 进栈 (又称压入)进栈就是在栈顶位置往栈中添加元素。
操作原则是,首先判栈满否?若满,则上溢;(这是要避免的)否则,可以进栈。
进栈时是先移动指针( top=top+1)再进栈 。
例如,设有一栈区为 s,n0=3,将 A,B,C三个元素依次进栈操作过程为,图 3-2所示初态
top - 1
栈图 3-2顺序栈进栈示意图武汉理工大学华夏学院 -信息工程系
A进栈
A
top 0

B进栈 B
A
top 1

C进栈
C
B
A
top 2
栈武汉理工大学华夏学院 -信息工程系图 3-3进栈算法流程图
top=top+1
S[top]=x
/*进栈完成 */
/*栈上溢错 */
给 X赋值返回
/*栈空无元素出栈 */
X=S[top]
top=top-1
/*出栈完成 */
返回
/*出栈操作 */
图 3-5出栈算法流程图是是
top= =n0-1
top= = -1
武汉理工大学华夏学院 -信息工程系例如,在图 3-2所示的 s栈中,n0=3,将三个元素依次出栈操作过程为图 3-4所示,可见,进栈顺序为 A,B,C,而出栈后的序列则是 C,B,A。
( 6)出栈 (又称 弹出 ),就是把栈顶元素送出。
操作原则 是,首先判栈空否?若空,则下溢;
(即栈处理过程中的结束)否则,可以出栈。
出栈时是先出栈,再移动指针( top=top- 1)。
初态 CB
A
top 2
栈图 3-4顺序栈出栈示意图武汉理工大学华夏学院 -信息工程系
C出栈
C
B
A
top 1
B出栈 CB
A
top

A出栈
CB
A
top - 1

0
栈武汉理工大学华夏学院 -信息工程系
5,如何避免栈上溢?
栈作为一个回溯算法处理结构普遍应用于递归等算法中,但是栈区大小的设置影响了算法效率,若栈区小,常常会遇到栈上溢的错误,
导致算法不能进行到底。如何防止栈上溢?
当一个算法中需要使用两个以上栈时,常采用两栈共享一片连续存储区的方法来节省存储空间且避免栈上溢。
武汉理工大学华夏学院 -信息工程系具体操作为,设 S[N]为一个数组,用来作为 P
栈和 T栈的栈区。 P栈的栈指针为 PTOP,T栈的栈指针为 TTOP,分别将两个栈的栈底分设在 S 数组的两端,P栈按正常状态进出栈,T栈反向进出栈。两栈空的表示是:即 PTOP=-1,为 P栈空当 TTOP= N 时,为 T栈空。两栈满的表示是:
两栈的栈指针在 S 数组的某一位置相遇,即当 PTOP+1=TTOP时,两栈均满。如图 3-5所示。
进出栈的算法框图如图 3-6所示。
武汉理工大学华夏学院 -信息工程系
ptop 两栈空
A进 P栈图 3-6两栈共享连续存储区示意图
-1 ttop n
B进 T栈
… …
ptop 0 ttop n-1
… …
两栈满
BE DG· · · K M H · · · ·A C
A B
武汉理工大学华夏学院 -信息工程系
ptop+1=ttop
显示上溢
Ptop=ptop+1
S[ptop]=x
进 P栈进 T栈
Ttop=ttop-1
S[ttop]=x
出哪一个栈出 T栈 出 P栈
ttop=n
栈空 (无数出栈)Y=s[ttop]
ttop=ttop+1
ptop=-1
Y=s[ptop]
ptop=ptop-1
返回返回图 3-7进出栈算法框图是 是否 否栈满武汉理工大学华夏学院 -信息工程系
3,操作步骤
( 1)进栈:形成新结点;将头指针的值送入新结点的指针字段中将新结点的地址送给头指针保存。
( 2)出栈:首先判栈空否:若不空,则将首结点的指针字段的值送头指针即可。
二,链式栈
1.定义 用链接方法存储的栈,称为链式栈,也称链接栈。
2.结构 用单链表作为栈区,单链表的头指针作为作为栈指针,所以对栈的操作(进出栈)实际就是在单链表的表头位置进行插入或删除操作,只需注意头指针的位置即可。因此,操作算法比较简单。
武汉理工大学华夏学院 -信息工程系
a b c d e
/*栈指针 */
/*进栈 */
a b c d e
x
a ^ b c d e
/*出栈 */
武汉理工大学华夏学院 -信息工程系
5.栈的应用
( 1) 改变序列的原顺序例如,设有一个序列 a,b,c,d,e依次进栈,
可以得到的出栈序列有哪些?
( 2)编译系统中检查括号配对、进行表达式计算
( 3)递归、递推算法的求解
( 4)生活中的应用 如列车的货车车厢编组武汉理工大学华夏学院 -信息工程系
3.3 队列一、顺序队列
1,定义 用顺序存储方法存储的队列称为顺序队列 。
2,结构 用结构数组作为队区,并设置两个指针 f和 r作为队列的队首、队尾指针,所以对队列的操作(进、出队)实际就是顺序表的头部位置进行删除操作、尾部位置进行插入操作,且只需注意改变首、尾指针的值即可。
因此,操作算法比较简单武汉理工大学华夏学院 -信息工程系
A
n0- 1
队尾
B
C
D
·
·
·
队头进队端出队端
f 0
r 33
2
1
0
图 3-7 顺序队列结构武汉理工大学华夏学院 -信息工程系
( 1) 队首 允许进行删除操作 (出队 )的一端,称为队首。
( 2) 队尾 允许进行插入操作 (进队 )的一端,称为队尾。
( 3) 队首指针 指向队首元素位置的一个整型变量,称为队首指针,又称出队指针。一般用
f 表示。
3,术语武汉理工大学华夏学院 -信息工程系
( 4) 队尾指针 指向队尾元素位置的一个整型变量,称为队尾指针,又称进队指针。一般用 r
表示。
( 5) 环状队列 由于队列的插入或删除操作是根据队首指针和队尾指针的移动来实现的,且队首指针和队尾指针是朝着同一个方向移动,
所以,把队列就想象成一个首尾相连的环,即可以避免“假溢出”,又可以控制队首指针和队尾指针保证在数组的上下界内改变。(注意:
“假溢出”就是队首指针或队尾指针已到数组的上界,但又没有装满所有的存储空间)
武汉理工大学华夏学院 -信息工程系
4.顺序队列的描述顺序队列一般用一个一维数组进行描述,
且定义一个整型变量 f作为队首指针,r作为队尾指针 。其说明如下:
用 C语言 描述为,
#define n0 50
#define datatype char
datatype que[n0 ];
int f,r;
定义的顺序队列结构如图 3-7所示。
武汉理工大学华夏学院 -信息工程系
( 1) 进队 进队就是在队尾位置往队中添加元素。
操作原则是,首先判队满否?(队满的判断是:
进队指针 r是否追上了出队指针 f) 若满,则上溢否则,
可以进队。
( 2)出队 出栈就是把队首位置上的元素送出。(或表示该元素不在队中)
操作原则是,首先判队空否?(队空的判断是:
出队指针 f是否追上了进队指针 r) 若空,则下溢;(即队处理过程中的结束)否则,可以出队。
5,顺序队列的操作注意,在进出队操作时,还需要判断是否要翻转例如,设有一队区为 s,n0=3,将 A,B,C,D四个元素依次进行进出队操作的过程为图 3-8所示:
武汉理工大学华夏学院 -信息工程系
A
A
B
A
B
C
B
D
初态
r - 1
f 0
队列
A进队
r 0
f 0
操作过程:
r=f,S[r]=A
B进队
r 1
f 0
操作过程:
r=r+1,S[r]=B
A出队
r 1
f 1
操作过程:
x=S[f],f=f+1
C进队
r 2
f 1
操作过程:
r=r+1,S[r]=C
D进队
r 0
f 1
操作过程:
r=0,S[r]=D
此时为假溢出翻转图 3-8进出队示意图
B
C
A
武汉理工大学华夏学院 -信息工程系不难看出,进队要进行三次判断(队满,队空,是否翻转);出队时要进行两次判断(队空,是否翻转)。
( 3)进出队的算法流程图进队
r=r+1
S[r]=x
给 X赋值队空无元素出队返回
X=s[f]
f= f+1
r= f
上溢
r= 0
f= 0
返回出队要空要空队满否队空否队空否要翻转?
要翻转?
满武汉理工大学华夏学院 -信息工程系
1,定义 用链接方法存储的队列,称为链式队列,也称链接队列。
2,结构 用单链表作为队区,单链表的头指针作为队首指针,用 f表示,另外增加一个队尾指针 r,指向单链表的尾结点的地址,所以对链式队列的操作(进出队) 实际就是在单链表的表头 位进行插入及在单链表的表尾位置进行删除操作即可。
二、链式队列武汉理工大学华夏学院 -信息工程系
3,操作步骤
( 1) 进队,
形成新结点;将进队指针 r的值送入新结点的指针字段中再将新结点的地址送给 r保存。
( 2) 出队,
首先判队空否:
若不空,则将出队指针 f指出的结点的指针字段的值送 给 f即可。
武汉理工大学华夏学院 -信息工程系三 队列的应用
1,操作系统中的应用
打印机与 cpu的速率不匹配问题的处理
2.缓冲区的设计原理
3.算法中的应用 例如:报数问题
例题 设队列中有 a,b,c,d,e五个元素,其中队首为 a,若对这个队列重复执行下列四步操作
( 1)输出队首元素 ( 2)把队首元素插入到队尾
( 3)删除队首元素 ( 4)删除队首元素
直到队列为空,则得到的输出序列是什么?
本章作业,P87 3.1,3.2,3.3,3.8