§3栈和队列
§3.1 栈
栈（stack）是一种仅限于在称为栈顶（top）的一端进行插入和删除操作的线性表，另一端则被为栈底（bottom）。不含元素的空表称为空栈。
栈的特点：后进先出（Last In First Out），简称：LIFO。
栈的表示和实现
和线性表类似，栈也有两种存储结构。
（1）．顺序栈
顺序栈即采用的顺序存储结构来表示栈，通常采用数组来实现。
采用顺序栈受数组空间的约束，有“溢出”的可能，编程前应作空间估算，若有溢出可能，应作溢出判断及相应的处理。
在一个程序中，常常会出现同时使用多个栈的情形。为了不因栈上溢而产生错误中断，必须给每个栈预分一个较大的空间，但这并不容易做到，因为栈实际所用的最大空间很难估计；而且各个栈的实际使用量在使用期间是变化的，往往会有这样的情况，即其中一个栈发生上溢，而另一个栈还是空的。设想，若令多个栈共享空间，则将提高空间的使用效率，并减少发生栈上溢的可能。
所以，可以采用两个栈共享空间的方法：假设在程序中需设两个栈，并共享一维数组空间。则利用“栈底位置不变”的特性，可将两个栈的栈底分别设在数组空间的两端，然后各自向中间伸展（如图），仅当两个栈的栈顶相遇时才可能发生上溢。
（2）．链栈
采用链式存储结构的栈简称链栈。
对于链栈，不含产生单个栈溢出的情况，但要记得回收结点空间（dispose（p）），否则会出现整个空间被占满，new（p）过程无法实现（即无法申请新的结点空间）的情况。
【练习】 回文串识别
输入一字符串，判断它是否为一回文串。所谓回文串是指去掉其中的空格与标点符号等非字母符号后，从前后两个方向读到的串相同，例如：
ten animals I slam in a net. （我将十只动物装在网里）
输入：一字符串 输出：Yes 或No
§3.2 队列
队列（queue ）是所有的插入都在一端进行，而所有的删除都在另一端进行的线性表。允许插入的一端称为队尾（rear ），允许删除的一端称为队头（front ）。
队列的特点：先进先出（|First In First Out ），简称：FIFO 。
队列的表示和实现
和栈一样，队列也有顺序存储和链式存储两种表示和实现方法。
在顺序存储结构中，同样有溢出可能，即元素因队满而无法入队。对于队列来说，可以采用循环队列的技巧，仅当队头与队尾相遇时为队满。
【例3.2.1】逐行打印二项展开式 (a + b )i 的系数：
杨辉三角形 (Pascal’s triangle)
要求：采用队列实现！
输入： n ——层数（n<50）25 a 1 a 2 a 3 …… a n
出队列
出队列
队头 队尾 队头 队尾 1 1 i = 1
1 2 1
2
1 5 5 1
3
1 4 6 4 1
4
1 5 10 10 5 1
5 1
6 15 20 15 6 1
6
【算法思路】
分析第 i 行元素与第i+1行元素的关系
目的是从前一行的数据可以计算下一行的数据
从第 i 行数据计算并存放第 i+1 行数据
从数据结构上，可设计一个足够长的一维数组，以实现上述算法。
【练习】根据上述思路分析，用队列的方法完成例3.2.1。
【练习】再用二维数组，用其它方法完成例3.2.1。
【练习】侦察兵队列
有一个侦察班，由11人组成，其中6名是老侦察员，5名是新侦察员。一次执勤要穿越敌人的一道封锁线。根据当时的情况，队伍只能单线纵向排列，且前面第一、二人越过后，第三个人要返回报告情况，该侦察员随后编到队伍的末尾。接着第四、五人越过，第六人报告并排到末尾。依此类推。最后三人一齐顺次过去。越过封锁线后，队伍便形成老、新交替的队形。请问，穿越前队伍该怎样排？
要求：采用队列实现！
输出：O表示老队员，Y表示新队员
【练习】倒水问题
[问题描述]
有三个分别装有a升水、b升水和c升水的量筒（c>b>a>0，且b与a互质）, 如果c 筒装满水，a与b均为空筒，三个筒相互倒水且不准把水倒往三个筒之外，一个往另一个筒倒水记为一次倒水。问是否能量出d升水(c>d>0)，若能，请求出最少的倒水次数使它能倒出容量为d的水的方案。
[输入格式]
数据存放在当前目录下的文本文件“water.in”中。
文件中以一行的形式存放四个正整数，分别a、b、c、d的值。
[输出格式]
答案输出到当前目录下的文本文件“water.out”中。
第一次行是最少的倒水次数Q，第二起的Q行是每次例水时量简的水量，依次为a、b、c （输入与输出数据中同一行相邻两个数之间用空格区分。）
[输入输出举例]
water.in
3 7 10 5
water.out
10 9
0 0 10 0 0 10
3 0 7 0 7 3
0 3 7 3 4 3
3 3
4 0 4 6
0 6 4 3 1 6
3 6 1 0 1 9
2 7 1 1 0 9
2 0 8 1 7 2
0 2 8 3 5 2
3 2 5
（仅有第二组才是最优的一个解。）
§3.3 栈的应用实例
§3.3.1 中缀表达式和后缀表达式
对于高级语言程序中的表达式，在编译时求解用栈来实现。任何一个表达式是由操作数（常量、常量名、变量名）、运算符（算术、关系和逻辑三种运算符）和界限符（左、右圆括号，结束符）所组成。
运算符在两个操作数之间的表达式，如a+b、e*f-d等，称为中缀表达式。求值时，一般会有运算符号的优先权和结合权问题。例如：a+b*c-d，我们知道b*c要先求，但编译器只能从左到有逐一检查，检查到加号时尚无法知道是否可执行，待检查到乘号时，因乘号运算优先级比加号高，所有a+b不可以被执行，待继续基础到减号时，方可执行b*c。
而后缀表达式是运算符在两个操作数之后，如ab*，也称为“逆波兰式”。后缀表达式可以顺序计算求值，所以编译程序常把中缀表达式变换成后缀表达式，然后再求值。
下表是中缀表达式所对应的后缀表达式：
(一)、将中缀表达式转换成后缀表达式
在转换过程中为了确定计算次序，要按运算符的优先级进行，各运算符优先级如下表，优先级数大的先执行。
【例3.3.1】将中缀表达式转换成后缀表达式。
输入：中缀表达式，如：B * (D-C) + A
输出：后缀表达式，如：BDC-*A+
【算法思想】
设立一个栈来实现中缀表达式变后缀表达式。
设中缀表达式在字符数组E中，E的末尾再加‘#’作为结束符，将转成后缀表达式，存于字符串A中。
对E中表达式自左向右扫描，遇数直接送到A中，若遇到运算符就考虑进栈，进栈的原则是保持栈顶的运算符优先级最高。即若欲进栈的算符是‘( ’或欲进栈的运算符优先级大于栈顶运算符的优先级，则将算符入栈，否则从栈中退出算符送至A中，直至欲进栈
的算符优先级大于栈顶算符的优先级，这时才将欲进栈的算符入栈。若遇到‘)’时，将栈中算符退出送入A 中，直至退出‘( ’为止。若遇表达式结束符‘#’，则依次退出栈中算符送入A 中。
根据上述算法，将中缀表达式B * (D -C) + A 转换成后缀表达式BDC -*A+ 的过程图3_1所示。
【参考程序段】
const m=100;
var E , A , S : array [1..m] of char;
{ E 中为中缀式，A 中为后缀式，S 为栈}
i , j , t : integer; procedure postexp; begin
i:=1; j:=1; t:=0;
while E[ i ]<>’#’ do begin case E[ i ] of
‘a ’.. ‘z ’, ‘A ’.. ‘Z ’ : begin
A[ j ]:=E[ i ]; j:=j+1; end; ‘(’ : begin
t:=t+1; S[ t ]:= ‘(’; end; ‘)’ : begin
while s[ t ]< > ‘(’ do begin
A[ j ]:=s[ t ]; j:=j+1; t:=t -1; end; t:=t -1; end; ‘+’, ‘-’ : begin
while (t< >0) and (s[t]< > ‘(’) do begin A[ j ]:=S[ t ]; j:=j+1; t:=t -1; end;
t:=t+1; s[ t ]:=E[ i ]; end; ‘*’, ‘/’ : begin
while (t< >0) and (S[ t ]= ‘*’ or S[ t ]= ‘/’) do begin
A[ j ]:=S[ t ]; j:=j+1; t:=t -1;
扫描E 栈S 转换至A B * B * * ( B ( * ( B D * ( - BD -
* ( -
BD
C * BDC
) + BDC -
+ + BDC -*
A BDC -*A
# BDC -*A+ 图3_1
end; {while}
t:=t+1; S[ t ]:=E[ i ];
end;
end; {case}
i:=i+1;
end; {while}
while t< >0 do begin
A[ j ]:=S[ t ]; j:=j+1; t:=t-1;
end;
A[ j ]:= ‘#’;
end;
(二)、对后缀表达式求值
计算一个后缀表达式的值，在算法上比中缀表达式要简单得多，这是因为后缀表达式有两个优点：表达式无括号，也不需考虑运算符的优先级。
【算法思想】
对后缀表达式求值要使用一个栈来实现。
自左至右扫描后缀表达式，若遇数就入栈，若遇到运算符就从栈中退出两个数进行运算，并把计算结果入栈。如此下去，直至遇到结束符“#”为止。最后栈底元素值为所求得的结果。
【练习】将一个中缀表达式转换成后缀表达式，并对后缀表达式求值。
输入格式：（输入文件bds.in）
第一行：中缀表达式，运算数均为大写字母，运算符含乘方‘^’
第二行开始：每行为表达式中字母，及其对应的值，输入顺序按字典排序输出格式：（输入文件bds.out）
第一行：该中缀表达式所对应的后缀表达式
第二行：该表达式的值
输入输出举例：
§3.3.2 地图着色问题
对地图着色，可使用“四染色”定理，它是计算机科学中的著名定理之一，可以用不多于四色对地图着色，使相邻的行政区域不重色。应用这个定理的结论，利用回溯算法可对一幅给定的地图染色。作为地图四色的示例如图 3_3所示，图中01、02、03、04、05、06、07为行政区编号，1色、2色、3色、4色为各区域的颜色，称为色数。 【算法思想】
从编号为01的区域开始逐一进行染色，对每个区域用色数1，2，3，4依次进行试探，并尽可能取小色数。若当前所取色数与周围已染色的区域不重色，则把该区的色数入栈，否则依次使用下一色数进行试探。若从1色至4色均与相邻的某区域发生重色，则需退栈回溯，修改栈顶区域的色数。
在实现此算法时，可用一个关系矩阵R ( 1: n , 1: n )来描述各区域之间的边界关系。若 第i 区与第j 区相邻（有共同边界），则R[ i , j ]的值为1，否则为0。图 3_3中所示的地图关系矩阵如图 3_4所示。为了记下每个区域当前染色结果而设立一个栈S( 1 : n )，栈的下标值表示区域号，栈中的内容是色数，如S[ 6 ] = 3表示06区域当前染色的色数是3。
【参考程序段】 const n=7; {地图中区域数} type adjar=array[1..n,1..n] of 0..1; ads=array[1..n] of 1..4;
procedure mapcolor (var r:adjr; var s:ads);
begin
s[ 1]:=1; {01区染1色}
i:=2; j:=1; { i 为区域号，j 为染色号} while i while ( j< =4 ) and ( i while ( kj ) do begin k:=k+1; { 判断相邻区是否已染色} if k 图 3_3 j 1 2 3 4 5 6 7 R i 图3_4 end; { 与相邻区不重色，染色结果进栈，继续对下 一区从1色进行试探} end; if j.> 4 then begin i:= i -1; j:=s[ i ]+1; end; { 变更栈顶区域的染色色数} end; end; end; 按图3_3所示地图执行上述算法时，栈的变化情况如图3_5所示。 → → → → → → 从关系矩阵R 可以看出，当i = 6时，无论色数j ＝1 , 2 , 3 , 4都产生与相邻区重色问题 （因与i = 6相邻的区是1，2，4，5区，从栈S 可见这四个区色数分别1，2，3，4，四种色全部用完。6区再用四种色数之一，必然重色）。因此必须变更栈顶色数，而5区当前色数为“4”，也不存在除4以外的可染色色数，则需继续退栈，变更S[ 4 ]:=4，由此S[ 5 ]:=3，然而此时仍然6区与相邻区重色，再次退栈，将S[ 3 ]改为S[ 3 ]:=3时才求得所有地区的染色解。 §3.4 栈与递归 §3.4.1 递归形式一般有两种——直接递归和间接递归，而栈是实现递归的重要手段。 (一)、直接递归——子程序自己调用自己 【例2】 fac (n) = n ! = 按上述递归定义形式写出fac(n) 函数如下： function fac(n:integer):integer; begin if n=0 then fac:=1 else fac:=n*fac(n-1); 1 n=0 n ×fac (n -1) n>1 S 图3_5 它的执行流程如下： 一般来说，递归子程序在调用本身前应有条件语句控制何时进行递归，何时递归结束。这个条件语句就是递归边界。例如，fac 函数体中的“ if n=0 then fac:=1 ”。 (二)、间接递归——子程序A 调用子程序B ，子程序B 又调用子程序A 子程序A 和B 组合起来有两种结构形式： 1．B 是A 的局部对象 例： procedure A; procedure B; begin … A; {在B 中调用A} … end begin … B; {在A 中调用B} … end; 2．A 和B 是两个地位相同的子程序 例： procedure B (形式参数表): forward; {B 的完整说明在后} procedurde A; begin … B (实参表); {在A 中调用B} end; procedure B; {B 的首部缩写，形式参数表不再列出} begin … A; {在B 中调用A} … 3×fac (2) 2×fac (1) 1×fac (0) fac (0) = 1 6 A 的子过程B 的过程说明 【例题3】 求出一个在8×8的棋盘上，放置8个不能互相捕捉的“皇后”的所有布局。 显然，一个使“皇后”间不能互相捕捉的合理布局应该是——每列、每行确定有一个“皇后”，且在每条对角线上最多只有一个“皇后”。 【数据结构设计】 从8×8的棋盘，我们很容易想到用二维数组来存 储布局。 但是，进一步分析，每行有且仅有一个“皇后”， 我们可以仅用一维数组来存储布局。 S 1 2 3 4 5 6 7 8 S[ i ] 表示第i行“皇后”所处的列。 这一数据结构的改进，将大大简化编程。 【算法思路】 1、从空配置开始，在第1行至第top行为合理配置的基础上，递归调用自己而完成top+1 行上的配置，直至第8行配置也是合理时，就找到一个解。因此，top=9是递归边界。 2、在任一行上可能的配置有8种。开始时配置在第1列，以后改变时，顺次选择第2列， 第3列，……，直至第8列，当8列配置全不合理或者选中某一列配置时，则退出递归过程，通过恢复步数的形式回溯，直到所有布局为止。 3、要在( i , top) 配置“皇后”（S[ top ]:= i）的条件有两个： ①第1至top-1行的第i 列不能有“皇后”，即S[j]≠i，1≤j≤top-1； ②经( i , top) 的两条对角线上不能有“皇后”， 即：| S[ j ]-i | ≠| j -top |，1≤j≤top-1； 【参考程序】 program queen; var total : integer; {布局数} s : array[1..8] of 1..8; {布局} procedure search(top:integer); var i,j : integer; p : boolean; {p=true表示找到某列的配置} begin if top>8 then begin {配置成功，打印布局} writeln(total,' step: '); for i:=1 to 8 do write(s[i],' '); writeln; end else begin for i:=1 to 8 do begin {由第1行开始，顺序选择} p:=true; if top>1 then begin j:=1; {确定可否在(i,top)位置配置皇后} while (j if (s[j]=i) or (abs(s[j]-i)=abs(j-top)) then p:=false; j:=j+1; end; end; if p then begin {top列配置成功} s[top]:=i; search(top+1); {递归执行top+1列上的配置} end; end; end; end; Begin total:=0; {布局数计数器清0} search(1); End. §3.4.2 递归算法适用的场合 1、数据的定义形式按递归定义 如斐波那契数列的定义：f n = f n-1 + f n-2；f0 = 1 ；f1 = 2 ； 【练习3】对应的递归程序为： function fib ( n : integer ) : integer; begin if n=0 then {递归边界} else {递归} end; {fib} f [0]:= 1; f [1]:= 2; {递推边界} for i:=2 to n do f [ i ]:= f [ i-1 ]+ f [ i-2 ]; fib:= f [ n ]; 2、数据之间的关系（即数据结构）按递归定义，如树的遍历、图的搜索等； 3、问题解法按递归算法实现，如回溯法、分治法等； 递归算法效率较低，费时费空间，但递归算法可以使一个蕴含递归关系的程序简洁精炼。 P。（相关知识见《数学基础补充§【练习4】输出N元集的R排列，及其排列种数r n 1》） （输入：N R） C。 【练习5】输出N元集的R组合，及其排列种数r n （输入：N R） 练习3答案：① fib:=2 ② fib:=fib(n-2)+fib(n-1); 第3章栈和队列 一、选择题 1.栈结构通常采用的两种存储结构是（A ）。 A、顺序存储结构和链表存储结构 B、散列和索引方式 C、链表存储结构和数组 D、线性链表结构和非线性存储结构 2.设栈ST 用顺序存储结构表示，则栈ST 为空的条件是（ B ） A、ST.top-ST.base<>0 B、ST.top-ST.base==0 C、ST.top-ST.base<>n D、ST.top-ST.base==n 3.向一个栈顶指针为HS 的链栈中插入一个s 结点时，则执行（ C ） A、HS->next=s; B、s->next=HS->next；HS->next=s; C、s->next=HS；HS=s; D、s->next=HS；HS=HS->next; 4.从一个栈顶指针为HS 的链栈中删除一个结点，用x 保存被删除结点的值，则执行（ C） A 、x=HS；HS=HS->next; B 、HS=HS->next；x=HS->data; C 、x=HS->data；HS=HS->next; D 、s->next=Hs；Hs=HS->next; 5.表达式a*(b+c)-d 的后缀表达式为（ B ） A、abcdd+- B、abc+*d- C、abc*+d- D、-+*abcd 6.中缀表达式A-（B+C/D）*E 的后缀形式是（ D ） A、AB-C+D/E* B、ABC+D/E* C、ABCD/E*+- D、ABCD/+E*- 7.一个队列的入列序列是1，2，3，4，则队列的输出序列是（ B ） A、4，3，2，1 B、1，2，3，4 C、1，4，3，2 D、3，2，4，1 8.循环队列SQ 采用数组空间SQ.base[0,n-1]存放其元素值，已知其头尾指针分别是front 和rear，则判定此循环队列为空的条件是（） A、Q.rear-Q.front==n B、Q.rear-Q.front-1==n C、Q.front==Q.rear D、Q.front==Q.rear+1 9.循环队列SQ 采用数组空间SQ.base[0,n-1]存放其元素值，已知其头尾指针分别是front 和rear，则判定此循环队列为满的条件是（） A、Q.front==Q.rear B、Q.front!=Q.rear C、Q.front==(Q.rear+1)%n D、Q.front!=(Q.rear+1)%n 10.若在一个大小为6 的数组上实现循环队列，且当前rear 和front 的值分别为0 和3，当从 队列中删除一个元素，再加入两个元素后，rear 和front 的值分别为（） A、1，5 B、2, 4 C、4，2 D、5，1 11.用单链表表示的链式队列的队头在链表的（）位置 A、链头 B、链尾 C、链中 12.判定一个链队列Q（最多元素为n 个）为空的条件是（） A、Q.front==Q.rear B、Q.front!=Q.rear C、Q.front==(Q.rear+1)%n D、Q.front!=(Q.rear+1)%n 13.在链队列Q 中，插入s 所指结点需顺序执行的指令是（） A 、Q.front->next=s；f=s; B 、Q.rear->next=s；Q.rear=s; 实验三栈和队列的应用 1、实验目的 （1）熟练掌握栈和队列的结构以及这两种数据结构的特点、栈与队列的基本操作。 （2）能够在两种存储结构上实现栈的基本运算，特别注意栈满和栈空的判断条件及描述方法； （3）熟练掌握链队列和循环队列的基本运算，并特别注意队列满和队列空的判断条件和描述方法； （4）掌握栈和队列的应用； 2、实验内容 1）栈和队列基本操作实现 （1）栈的基本操作：采用顺序存储或链式存储结构（数据类型自定义），实现初始化栈、判栈是否为空、入栈、出栈、读取栈顶元素等基本操作，栈的存储结构自定义。 （2）队列的基本操作：实现循环队列或链队列的初始化、入队列、出队列、求队列中元素个数、判队列空等操作，队列的存储结构自定义。 2）栈和队列的应用 （1）利用栈的基本操作将一个十进制的正整数转换成二进制数据，并将其转换结果输出。 提示：利用栈的基本操作实现将任意一个十进制整数转化为R进制整数算法为： 十进制整数X和R作为形参 初始化栈 只要Ｘ不为0重复做下列动作 将x%R入栈 X=X/R 只要栈不为空重复做下列动作 栈顶出栈 输出栈顶元素 (2) 利用栈的基本操作对给定的字符串判断其是否是回文，若是则输出“Right”，否则输出“Wrong”。 (3) 假设循环队列中只设rear（队尾）和quelen（元素个数据）来分别表示队尾元素的位置和队中元素的个数，写出相应的入队和出队程序。 （4）选作题：编写程序实现对一个输入表达式的括号配对。 3、实验步骤 （1）理解栈的基本工作原理； （2）仔细分析实验内容，给出其算法和流程图； （3）用C语言实现该算法； （4）给出测试数据，并分析其结果； （5）在实验报告册上写出实验过程。 4、实验帮助 算法为： 1) 定义栈的顺序存取结构 2) 分别定义栈的基本操作（初始化栈、判栈为空、出栈、入栈等） 3) 定义一个函数用来实现上面问题： 十进制整数X和R作为形参 初始化栈 只要X不为0重复做下列动作 将X % R入栈 X=X/R 只要栈不为空重复做下列动作 栈顶出栈 输出栈顶元素 5、算法描述 （1））初始化栈S (创建一个空栈S) void initstack(sqstack *S) { S->base=(ElemType *) malloc(INITSIZE*sizeof(ElemType)); if(!S->base) exit (-1); S->top=0; /*空栈标志*/ S->stacksize = INITSIZE; } (2) 获取栈顶元素 int gettop(sqstack S,ElemType *e) //顺序钱 { if ( S.top==0 ) /* 栈空 */ 实验编号：3四川师大《数据结构》实验报告2016年10月29日 实验三栈和队列及其应用_ 一．实验目的及要求 （1）掌握栈和队列这两种特殊的线性表，熟悉它们的特性，在实际问题背景下灵活运用它们； （2）本实验训练的要点是“栈”的观点及其典型用法； （3）掌握问题求解的状态表示及其递归算法，以及由递归程序到非递归程序的转化方法。 二．实验内容 （1）编程实现栈在两种存储结构中的基本操作（栈的初始化、判栈空、入栈、出栈等）； （2）应用栈的基本操作，实现数制转换（任意进制）； （3）编程实现队列在两种存储结构中的基本操作（队列的初始化、判队列空、入队列、出队列）； （4）利用栈实现任一个表达式中的语法检查（括号的匹配）。 （5）利用栈实现表达式的求值。 注：（1）～（3）必做，（4）～（5）选做。 三．主要仪器设备及软件 （1）PC机 （2）Dev C++ ,Visual C++, VS2010等 四．实验主要流程、基本操作或核心代码、算法片段（该部分如不够填写，请另加附页）（1）编程实现栈在两种存储结构中的基本操作（栈的初始化、判栈空、入栈、出栈等）； A.顺序储存： 代码部分： 栈" << endl; cout << " 2.出栈" << endl; cout << " 3.判栈空" << endl; cout << " 4.返回栈顶部数据" << endl; cout << " 5.栈长" << endl; cout << " 0.退出系统" << endl; cout << "你的选择是：" ; } 链式储存： 代码部分： 栈"< 数据结构：栈和队列 单选题： 1.在一个具有n个单元的顺序栈中，假定以地址低端作为栈底，以top作为栈顶指针，则当做退栈处 理时，top变化为_____。 A. top不变 B. top＝-n C. top＝top-1 D.top=top+1 2.向顺序栈中压入元素时，是_____。 A.先移动栈顶指针，后存入元素 B.先存入元素，后移动栈顶指针 3.在一个顺序存储的循环队列中，队首指针指向队首元素的_____。 A.前一个位置 B.后一个位置 C.队首元素位置 4.若进栈序列为1,2,3,4,进栈过程中可以出栈，则_____不可能是一个出栈序列。 A.3,4,2,1 B.2,4,3,1 C.1,4,3,2 D.3,2,1,4 5.在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队首指针和队尾指针，则判断队 空的条件是_____。 A.front= =rear+1 B.front+1= =rear C.front= =rear D.front= =0 6.在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队首指针和队尾指针，则判断队 满的条件是_____。 A.\rear % n= =front B.(rear-1) % n= =front C.(rear-1) % n= =rear D.(rear+1) % n= =front 7.向一个栈项指针为hs的链栈中插入一个*s结点时，则执行_____。 A.hs->next=s; B.s->next=hs->next; hs->next=s; C.s->next=hs；hs=s; D.s->next=hs; hs=hs->next; 8.在一个链队列中，假定front和rear分别为队首指针和队尾指针，则进行插入*s结点的操作时应执 行_____。 A.front->next=s; front=s; B.rear->next=s; rear=s; C.front=front->next; D.front=rear->next; 9.栈的特点是_______队的特点是______ A.先进先出 B.先进后出B|A 10.栈和队列的共同点是_______。 A.都是先进后出 B.都是先进先出 C.只允许在端点处插入和删除元素 D.没有共同点 11.一个栈的进栈序列是a,b,c,d,e,则栈的不可能的输出序列是________。 A.edcba B.decba C.dceab D.abcde 12.若己知一个栈的进栈序列是1,2,3,…,n,其输出序列为p1,p2,p3,…,pn,若p1=n,则pi(1 实验二堆栈和队列 实验目的： 1.熟悉栈这种特殊线性结构的特性； 2.熟练并掌握栈在顺序存储结构和链表存储结构下的基本运算； 3.熟悉队列这种特殊线性结构的特性； 3.熟练掌握队列在链表存储结构下的基本运算。 实验原理： 堆栈顺序存储结构下的基本算法； 堆栈链式存储结构下的基本算法； 队列顺序存储结构下的基本算法； 队列链式存储结构下的基本算法； 实验内容： 第一题链式堆栈设计。要求 （1）用链式堆栈设计实现堆栈，堆栈的操作集合要求包括：初始化StackInitiate（S）,非空否StackNotEmpty(S)，入栈StackiPush(S,x),出栈StackPop（S,d）,取栈顶数据元素StackTop(S,d); （2）设计一个主函数对链式堆栈进行测试。测试方法为：依次把数据元素1，2，3，4，5入栈，然后出栈并在屏幕上显示出栈的数据元素； （3）定义数据元素的数据类型为如下形式的结构体， Typedef struct { char taskName[10]; int taskNo; }DataType; 首先设计一个包含5个数据元素的测试数据，然后设计一个主函数对链式堆栈进行测试，测试方法为：依次吧5个数据元素入栈，然后出栈并在屏幕上显示出栈的数据元素。 第二题对顺序循环队列，常规的设计方法是使用対尾指针和对头指针，对尾指针用于指示当前的対尾位置下标，对头指针用于指示当前的対头位置下标。现要求： （1）设计一个使用对头指针和计数器的顺序循环队列抽象数据类型，其中操作包括：初始化，入队列，出队列，取对头元素和判断队列是否为空； （2）编写主函数进行测试。 程序代码： 第一题： （1）源程序"LinStack.h"如下： #define NULL 0 typedef struct snode { DataType data; struct snode *next; } LSNode; /*（1）初始化StackInitiate(LSNode ** head) */ void StackInitiate(LSNode ** head) /*初始化带头结点链式堆栈*/ 实验二栈、队列的实现及应用 实验课程名：数据结构与算法 专业班级：学号：： /*构造空顺序栈*/ int InitStack(SqStack *S) //InitStack() sub-function { S->base = (SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType)); if (!S->base) { printf("分配空间失败!\n"); return (ERROR); } S->top = S->base; S->stacksize = STACK_INIT_SIZE; printf("栈初始化成功！\n"); return (OK); } //InitStack() end /*取顺序栈顶元素*/ int GetTop(SqStack *S, SElemType *e) //GetTop() sub-function { if (S->top == S->base) { printf("栈为空!\n"); //if empty SqStack return (ERROR); } *e = *(S->top - 1); return (OK); } //GetTop() end /*将元素压入顺序栈*/ int Push(SqStack *S) //Push() sub-function { SElemType e; if (S->top - S->base>S->stacksize) { S->base = (SElemType *)realloc(S->base, (S->stacksize + STACKINCREMENT*sizeof(SElemType))); if (!S->base) { printf("存储空间分配失败!\n"); return (ERROR); } S->top = S->base + S->stacksize; S->stacksize += STACKINCREMENT; } fflush(stdin);//清除输入缓冲区，否则原来的输入会默认送给变量x 第三章栈和队列试题 一、单项选择题 1.栈的插入和删除操作在（）进行。 A. 栈顶 B. 栈底 C. 任意位置 D. 指定位置 2.当利用大小为n的数组顺序存储一个栈时，假定用top==n表示栈空，则向这个栈插入一个元素时， 首先应执行（）语句修改top指针。 A. top++; B. top--; C. top = 0; D. top; 3.若让元素1,2,3依次进栈，则出栈次序不可能出现（）种情况。 A. 3, 2, 1 B. 2, 1, 3 C. 3, 1, 2 D. 1, 3, 2 4.在一个顺序存储的循环队列中，队头指针指向队头元素的（）位置。 A. 前一个 B. 后一个 C. 当前 D. 后面 5.当利用大小为n的数组顺序存储一个队列时，该队列的最大长度为（）。 A. n-2 B. n-1 C. n D. n+1 6.从一个顺序存储的循环队列中删除一个元素时，需要（）。 A. 队头指针加一 B. 队头指针减一 C. 取出队头指针所指的元素 D. 取出队尾指针所指的元素 7.假定一个顺序存储的循环队列的队头和队尾指针分别为front和rear，则判断队空的条件为（）。 A. front+1 == rear B. rear+1 == front C. front == 0 D. front == rear 8.假定一个链式队列的队头和队尾指针分别为front和rear，则判断队空的条件为（）。 A. front == rear B. front != NULL C. rear != NULL D. front == NULL 9.设链式栈中结点的结构为（data, link），且top是指向栈顶的指针。若想在链式栈的栈顶插入一 个由指针s所指的结点，则应执行操作（）。 A. top->link = s; B.s->link = top->link; top->link = s; C. s->link = top; top = s; D. s->link = top; top = top->link; 10.设链式栈中结点的结构为（data, link），且top是指向栈顶的指针。若想摘除链式栈的栈顶结点， 并将被摘除结点的值保存到x中，则应执行操作（）。 A. x = top->data; top = top->link; B. top = top->link; x = top->data; C. x = top; top = top->link; D. x = top->data; 11.设循环队列的结构是 #define MaxSize 100 typedef int ElemType; 数据结构练习第三章栈和队列 一、选择题 1．栈和队列的共同特点是( )。 A.只允许在端点处插入和删除元素 B.都是先进后出 C.都是先进先出 D.没有共同点 2．向顺序栈中压入新元素时，应当（）。 A．先移动栈顶指针，再存入元素 B．先存入元素，再移动栈顶指针C．先后次序无关紧要 D．同时进行 3．允许对队列进行的操作有( )。 A. 对队列中的元素排序 B. 取出最近进队的元素 C. 在队头元素之前插入元素 D. 删除队头元素 4．用链接方式存储的队列，在进行插入运算时( ). A. 仅修改头指针 B. 头、尾指针都要修改 C. 仅修改尾指针 D.头、尾指针可能都要修改 5．设用链表作为栈的存储结构则退栈操作（）。 A. 必须判别栈是否为满 B. 必须判别栈是否为空 C. 判别栈元素的类型 D.对栈不作任何判别 6．设指针变量front表示链式队列的队头指针，指针变量rear表示链式队列的队尾指针，指针变量s指向将要入队列的结点X，则入队列的操作序列为（）。 A.front->next=s；front=s； B. s->next=rear；rear=s； C. rear->next=s；rear=s； D. s->next=front；front=s； 7．设指针变量top指向当前链式栈的栈顶，则删除栈顶元素的操作序列为（）。 A.top=top+1; B. top=top-1; C. top->next=top; D. top=top->next; 8．队列是一种（）的线性表。 A. 先进先出 B. 先进后出 C. 只能插入 D. 只能删除 9．设输入序列1、2、3、…、n经过栈作用后，输出序列中的第一个元素是n，则输出序列中的第i个输出元素是（）。 A. n-i B. n-1-i C. n+l -i D.不能确定 10．设输入序列为1、2、3、4、5、6，则通过栈的作用后可以得到的输出序列为（）。 A. 5，3，4，6，1，2 B. 3，2，5，6，4，1 C. 3，1，2，5，4，6 D. 1，5，4，6，2，3 11．队列的删除操作是在（）进行。 A．队首 B．队尾 C．队前 D．队后 12．当利用大小为N 的数组顺序存储一个栈时，假定用top = = N表示栈空，则退栈时，用（）语句修改top指针。 A．top++; B．top=0; C．top--; D．top=N; 13．队列的插入操作是在（）进行。 南京信息工程大学实验（实习）报告 实验（实习）名称栈和队列日期2017.11.8 得分指导老师崔萌萌 系计算机系专业软件工程年级2016 班次(1) 姓名学号 一、实验目的 1、学习栈的顺序存储和实现，会进行栈的基本操作 2、掌握递归 3、学习队列的顺序存储、链式存储，会进行队列的基本操作 4、掌握循环队列的表示和基本操作 二、实验内容 1、用栈解决以下问题： （1）对于输入的任意一个非负十进制数，显示输出与其等值的八进制数，写出程序。（2）表达式求值，写出程序。 2、用递归写出以下程序： （1）求n！。 （2）汉诺塔程序，并截图显示3、4、5个盘子的移动步骤,写出移动6个盘子的移动次数。 3、编程实现：（1）创建队列，将asdfghjkl依次入队。（2）将队列asdfghjkl依次出队。 4、编程实现创建一个最多6个元素的循环队列、将ABCDEF依次入队，判断循环队列是否队满。 三、实验步骤 1.栈的使用 1.1 用栈实现进制的转换： 代码如下： #include printf("转换为%d进制： ",radix); while(n) { s.push(n%radix); n /= radix; } while(!s.empty()) { //非空 printf("%d",s.top()); s.pop(); } printf("\n"); return 0; } 运行结果如下： 2.2 求表达式的值 代码如下： #include 百度文库-让每个人平等地提升自我 实验二栈、队列的实现及应用 实验课程名：数据结构与算法 专业班级：_ 学号：__________ 姓名： _ 实验时间： ____ 实验地点：指导教师：冯珊__________ 一、实验目的 1掌握栈和队列的顺序存储结构和链式存储结构，以便在实际背景下灵活运用。 2、掌握栈和队列的特点，即先进后出与先进先出的原则。 3、掌握栈和队列的基本操作实现方法。 /*顺序栈的存储类型*/ typedef struct 1 2 3 4 5远 兀 1 一 7U- 元 谴 段 囑 :> o 1 2 3 R * 元 元 栈 書 t 出 一 ^ 零 遐 次 :± 谨 虚 1 2 3 ^ 5 I B D 认戯握结IVl 匚on&ol eAp pli cation!\[>ebu g\Con 5 o-leApp li cation 1 .exe :1 刖人操作谊睪代码(05):2 : h E s 选 的 操 一 兀 一 b 一 丁 一 丁 栈 ? 遐 次 嘆 區 1 2 3 4 5 5 ^ 元 元 栈 S 退 、 灵 岀 祓 S I ■ i 9 I I I i 主 至 ..T' 一 兀 元 栈 ￡ 1 2 3 4 5 \Z 百度文库 -让每个人平等地提升自我 P入操隹选择代码（0-5>:4 派元素的是 ; 栈 化 出 取 示 艮 i元一一 选 的 操 元 -> 入 中 >c 1- 苴翻（05）: 5 栈 化 亍 1 2 元 元 Is 务一（2）:完成下列程序，该程序实现栈的链式存储结构，构建链栈（栈中的元素依次为China , Japan, France，India ，Australia ），依次进行进栈和出栈操作，判断栈空和栈满操作，返回栈顶元素操作。 要求生成链栈时，从键盘上读取数据元素。 （1）源代码：#i nclude<> #in clude<> #in clude<> # define OK 1 # define ERROR 0 typedef char DataType; /*链式栈的存储类型*/ typedef struct SNode 习题三栈和队列 一单项选择题 1. 在作进栈运算时,应先判别栈是否(① ),在作退栈运算时应先判别栈是否(② )。当栈中元素为n个,作进栈运算时发生上溢,则说明该栈的最大容量为(③ )。 ①, ②: A. 空 B. 满 C. 上溢 D. 下溢 ③: A. n-1 B. n C. n+1 D. n/2 2．若已知一个栈的进栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，...，pn，若p1＝3，则p2为( )。 A 可能是2 B 一定是2 C 可能是1 D 一定是1 3. 有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？（） A. 5 4 3 6 1 2 B. 4 5 3 1 2 6 C. 3 4 6 5 2 1 D. 2 3 4 1 5 6 4.设有一顺序栈S，元素s1,s2,s3,s4,s5,s6依次进栈，如果6个元素出栈的顺序是s2,s3,s4, s6, s5,s1,则栈的容量至少应该是（） A.2 B. 3 C. 5 D.6 5. 若栈采用顺序存储方式存储，现两栈共享空间V[1..m]，top[i]代表第i个栈( i =1,2)栈顶，栈1的底在v[1]，栈2的底在V[m]，则栈满的条件是（）。 A. |top[2]-top[1]|=0 B. top[1]+1=top[2] C. top[1]+top[2]=m D. top[1]=top[2] 6. 执行完下列语句段后，i值为：（） int f(int x) { return ((x>0) ? x* f(x-1):2);} int i ; i =f(f(1)); A．2 B. 4 C. 8 D. 无限递归 7. 表达式3* 2^(4+2*2-6*3)-5求值过程中当扫描到6时，对象栈和算符栈为（），其中^为乘幂。 A. 3,2,4,1,1；(*^(+*- B. 3,2,8；(*^- C. 3,2,4,2,2；(*^(- D. 3,2,8；(*^(- 8. 用链接方式存储的队列，在进行删除运算时（）。 A. 仅修改头指针 B. 仅修改尾指针 C. 头、尾指针都要修改 D. 头、尾指针可能都要修改 9. 递归过程或函数调用时，处理参数及返回地址，要用一种称为（）的数据结构。 A．队列 B．多维数组 C．栈 D. 线性表 10．设C语言数组Data[m+1]作为循环队列SQ的存储空间， front为队头指针，rear为队尾指针，则执行出队操作的语句为（） A.front=front+1 B. front=（front+1）% m C.rear=(rear+1)%(m+1) D. front=(front+1)%(m+1) 11.循环队列的队满条件为 ( ) A. (sq.rear+1) % maxsize ==(sq.front+1) % maxsize; B. (sq.front+1) % maxsize ==sq.rear C. (sq.rear+1) % maxsize ==sq.front D.sq.rear ==sq.front 实验二栈和队列 一、实验目的 1. 掌握栈的顺序表示和实现 2. 掌握队列的链式表示和实现 二、实验内容 1. 编写一个程序实现顺序栈的各种基本运算。 2. 实现队列的链式表示和实现。 三、实验步骤 1. 初始化顺序栈 2. 插入元素 3. 删除栈顶元素 4. 取栈顶元素 5. 遍历顺序栈 6. 置空顺序栈 7. 初始化并建立链队列 8. 入链队列 9. 出链队列 10. 遍历链队列 四、实现提示 1. /*定义顺序栈的存储结构*/ typedef struct { ElemType stack[MAXNUM]; int top; }SqStack; /*初始化顺序栈函数*/ void InitStack(SqStack *p) {q=(SqStack*)malloc(sizeof(SqStack) /*申请空间*/) /*入栈函数*/ void Push(SqStack *p,ElemType x) {if(p->top 《数据结构》课程实验报告 实验名称栈和队列实验序号实验日期 姓名院系班级学号 专业指导教师成绩 教师评语 一、实验目的和要求 (1)理解栈和队列的特征以及它们之间的差异，知道在何时使用那种数据结构。 (2)重点掌握在顺序栈上和链栈上实现栈的基本运算算法，注意栈满和栈空的条件。 (3)重点掌握在顺序队上和链队上实现队列的基本运算算法，注意循环队队列满和队空的条件。 (4)灵活运用栈和队列这两种数据结构解决一些综合应用问题。 二、实验项目摘要 编写一个程序algo3-1.cpp，实现顺序栈的各种基本运算，并在此基础上设计一个主程序并完成如下功能：（1）初始化栈s； （2）判断栈s是否非空； （3）依次进栈元素a,b,c,d,e； （4）判断栈s是否非空； （5）输出栈长度； （6）输出从栈顶到栈底元素； （7）输出出栈序列； （8）判断栈s是否非空； （9）释放栈。 编写一个程序algo3-3.cpp，实现顺序环形队列的各种基本运算，并在此基础上设计一个主程序并完成如下功能： （1）初始化队列q； （2）判断队列q是否非空； （3）依次进队列a,b,c； （4）出队一个元素，输出该元素； （5）输出队列q的元素个数； （6）依次进队列元素d,e,f； （7）输出队列q的元素个数； （8）输出出队序列； （9）释放队列。 三、实验预习内容 栈的顺序存储结构及其基本运算实现（初始化栈，销毁栈，求栈的长度，判断栈是否为空，进栈，取栈顶元素，显示栈中元素） 队列的顺序存储结构及其基本运算实现（初始化队列，销毁队列，判断队列是否为空，入队列，出队列） 三、实验结果与分析 3-1 #define maxsize 100 #include 栈和队列综合实验报告 一、实验目的 （1）能够利用栈和队列的基本运算进行相关操作。 （2）进一步熟悉文件的应用 （3）加深队列和栈的数据结构理解，逐步培养解决实际问题的编程能力。 二、实验环境 装有Visual C＋＋的计算机。 本次实验共计4学时。 三、实验内容 以下两个实验任选一个。 1、迷宫求解 设计一个迷宫求解程序，要求如下： 以M × N表示长方阵表示迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。 能任意设定的迷宫 （选作）如果有通路，列出所有通路 提示： 以一个二维数组来表示迷宫，0和1分别表示迷宫中的通路和障碍，如下图迷宫数据为：11 01 01 01 01 01 01 01 11 入口位置：1 1 出口位置：8 8 四、重要数据结构 typedef struct{ int j[100]; int top;栈顶指针，一直指向栈顶 }stack;//存放路径的栈 int s[4][2]={{0,0},{0,0},{0,0},{0,0}}; //用于存放最近的四步路径坐标的数组，是即使改变的，即走一步，便将之前的坐标向前移一步，将最早的一步坐标覆盖掉，新的一步放入数组末尾其实功能和队列一样。 其作用是用来判断是否产生了由于本程序算法产生的“田”字方格内的死循环而准备的，用于帮助跳出循环。 五、实现思路分析 if(a[m][n+1]==0&&k!=3){ n++; k=1; o=0; }else if(a[m+1][n]==0&&k!=4){ m++; k=2; o=0; }else if(a[m][n-1]==0&&k!=1){ n--; k=3; o=0; }else if(a[m-1][n]==0&&k!=2){ m--; k=4; o=0; }else{ o++;} if(o>=2){ k=0; }//向所在方格的四个方向探路，探路顺序为→↓←↑（顺时针），其中if判断条件内的&&k!=n和每个语句块中的对k赋值是为防止其走回头路进入死循环，而最后一个else{}内语句是为了防止进入死路时，不能走回头路而造成的死循环。 push(q,m,n);//没进行一次循环都会讲前进的路径入栈。 if (pushf(&s[0][0],m,n)==0){ k=3;}//用来判断是否产生了由于本程序探路算法产生的“田”字方格内的死循环而准备的，用于帮助跳出田字循环。同时会将路径存入用于下次判断 六、程序调试问题分析 最开始写完时是没有死路回头机制的，然后添加了两步内寻路不回头机制。 第二个是“田”字循环问题，解决方法是加入了一个记录最近四步用的数组和一个判断田字循环的函数pushf。 栈和队列 1 简述栈和线性表的区别。 2 简述栈和队列这两种数据结构的相同点和不同点。 3 如果进栈的元素序列为A，B，C，D，则可能得到的出栈序列有多少种？写出全部的可能序列。 4 如果进栈的元素序列为1，2，3，4，5，6，能否得到4，3，5，6，1，2和1，3，5，4，2，6的出栈序列？并说明为什么不能得到或如何得到。 5 写出下列程序段的运行结果（栈中的元素类型是char）： main( ) { SEQSTACK s,*p; char x, y; p = &s; initstack(p); x = ′c′; y = ′k′; push(p,x); push(p,′a′); push(p,y); x = pop(p); push(p,′t′); push(p,x); x = pop(p); push(p,′s′); while(!empty(p)) { y = pop(p); printf(″%c″,y);} printf(″%c＼n″,x); } 6 将一个非负十进制整数转换成二进制数，用非递归算法和递归算法来实现。 7 写一算法将一顺序栈中的元素依次取出，并打印元素值。 8 设单链表中存放着n个字符，试编一算法，判断该字符串是否有中心对称关系，例如xyzzyx，xyzyx都算是中心对称的字符串。 9 写出下列程序段的运行结果（队列中的元素类型是char）： main( ) { SEQQUEUE a, *q; char x, y; q = &a; x=′e′; y=′c′; initqueue(q); enqueue(q,′h′); enqueue(q,′r′); enqueue(q,y); x = dequeue(q); 数据结构实验报告 实验名称：栈和队列及其应用 班级：12级电气本2 学号：2012081227 姓名：赵雪磊 指导教师：梁海丽 日期：2013年9月23日 数学与信息技术学院 一、实验目的 1. 掌握栈和队列的概念。 2．掌握栈和队列的基本操作（插入、删除、取栈顶元素、出队、入队等）。 3．理解栈和队列的顺序、链式存储。 二、实验要求 利用顺序栈将任意一个给定的十进制数转换成二进制、八进制、十六进制数并输出。 三、算法描述 #include "stdafx.h" #include "iomanip.h" void D10to2_8_16(int i,char radix) { char m; if(i>=radix) D10to2_8_16(i/radix,radix); if((m=i%radix+'0')>0x39) m+=7; cout << m; } void main(void) { int nDec; cout << "请输入一个十进制正整数...\n" << "nDec="; cin >> nDec; cout << "转换为二进制是:"; D10to2_8_16(nDec,2); cout << endl; cout << "转换为八进制是:0"; D10to2_8_16(nDec,8); cout << endl; cout << "转换为十六进制是:0x"; D10to2_8_16(nDec,16); cout << endl; } 四、程序清单 #include 《数据结构》实验指导及报告书 2014 / 2015 学年第 1学期 姓名： 学号： 班级： 指导教师：徐江 计算机科学与工程学院 2014 实验二栈和队列 一、实验目的 1、掌握栈的结构特性及其入栈，出栈操作； 2、掌握队列的结构特性及其入队、出队的操作，掌握循环队列的特点及其操作。 二、实验内容和要求 1、阅读下面程序，将函数Push和函数Pop补充完整。要求输入元素序列1 2 3 4 5 e，运行结果如下所示。 #include完整版数据结构习题集第3章栈和队列
实验三 栈和队列的应用
数据结构_实验三_栈和队列及其应用
数据结构：栈和队列学习资料
数据结构堆栈与队列实验报告
实验二_栈、队列地实现与应用
数据结构第三章栈和队列3习题
数据结构练习 第三章 栈和队列
数据结构栈和队列实验报告.doc
实验二栈队列的实现及应用
数据结构栈和队列习题及答案
数据结构栈和队列
数据结构栈和队列实验报告
栈和队列综合实验报告
《数据结构练习题》栈和队列
栈和队列及其应用实验报告
《数据结构》实验二 栈和队列
相关主题
文本预览