第三章 栈和队列

第三章栈和队列3.1栈3.1.1栈的定义3.1.2栈的表示和实现3.2栈的应用举例

3.1栈3.1.1栈的定义及基本运算栈(Stack)是限制在表的一端进行插入和删除运算的线性表，通常称插入、删除的这一端为栈顶(Top)，另一端为栈底(Bottom)。当表中没有元素时称为空栈。假设栈S=(a1，a2，a3，…an)，则a1称为栈底元素，an为栈顶元素。栈中元素按a1，a2，a3，…an的次序进栈，退栈的第一个元素应为栈顶元素。因此，栈的修改是按后进先出的原则进行的，所以，栈称为后进先出（先进后出）表（LIFO，FILO）。3.1.2顺序存储栈栈是线性表的特例，因此线性表的存储结构对栈也适应。栈的顺序存储结构简称为顺序栈，可用数组来实现顺序栈。因为栈底位置是固定不变的，所以可以将栈底位置设置在数组的两端的任何一个端点；栈顶位置是随着进栈和退栈操作而变化的，故需用一个整型变量top（栈顶指针）来指出栈顶。栈顶栈底例、一叠盘子、弹夹等。

anan-1…...a2a1入出-1空栈top016为指示当前栈顶的位置，需top为栈顶指针（MAXSIZE代表栈容量）。初始化:x进栈：退栈：top=-1;if(top==MAXSIZE-1

上溢处理；

else{top++;stack[top]=x;}if(top==-1)下溢处理；

else{y=stack[top]; top--;}3.1.3链栈栈的链式存储结构称为链栈，插入和删除操作仅限制在链头位置上进行。栈顶指针就是链表的头指针。初始化：top=NULLX进栈：p=newStackNode;p->data=x;p->next=top;top=p;退栈:if(top==NULL)

下溢处理；else{ y=top->data; p=top; top=p->next; deletep;}∧top3.2栈的应用举例由于栈结构具有的后进先出的固有特性，致使栈成为程序设计中常用的工具。以下是几个栈应用的例子。

3.2.1数制转换

十进制N和其它进制数的转换是计算机实现计算的基本问题,其解决方法很多,其中一个简单算法基于下列原理:

N=(n/d)*d+n%d例如(1348)10=(2504)8，其运算过程如下：

nn/8n%8134816841682102125202

voidconversion(){initstack(s);cin>>n;while(n){push(s,n%8);n=n/8;}while(!Stackempty(s)){pop(s,e); cout<<e;}}3.2.2括号匹配的检验假设在表达式中（［］（））或［（［］［］）］等为正确的格式，［（］）或（［（））或（（）］)均为不正确的格式。算法的设计思想：1）凡出现左括弧，则进栈；2）凡出现右括弧，首先检查栈是否空

若栈空，则表明该“右括弧”多余，

否则和栈顶元素比较，

若相匹配，则“左括弧出栈”

，

否则表明不匹配。3）表达式检验结束时，若栈空，则表明表达式中匹配正确，

否则表明“左括弧”有余。3.2.3行编辑程序

在编辑程序中，设立一个输入缓冲区，用于接受用户输入的一行字符，然后逐行存入用户数据区。允许用户输入错误，并在发现有误时可以及时更正。

出口3.2.4迷宫求解

入口3.2.4迷宫求解

3.2.4迷宫求解

3.2.4迷宫求解

3.2.4迷宫求解

3.2.4迷宫求解

3.2.4迷宫求解

3.2.4迷宫求解

3.2.4迷宫求解

3.2.4迷宫求解

3.2.4迷宫求解

3.2.4迷宫求解

3.2.4迷宫求解

3.2.4迷宫求解

3.2.4迷宫求解

3.2.4迷宫求解

3.2.4迷宫求解

3.2.4迷宫求解

3.2.4迷宫求解

求迷宫路径算法的基本思想是：若当前位置“可通”，则纳入路径，继续前进;若当前位置“不可通”，则后退，换方向继续探索;若四周“均无通路”，则将当前位置从路径中删除出去。设定初值为入口位置,以正东为起始方向；

do｛if(当前位置可通)则｛将当前位置插入栈顶；

if(该位置是出口位置)exit(0)；

else按顺时针下一方向为新的当前位置；｝

else{………….}}while(栈不空）；求迷宫中一条从入口到出口的路径的算法：若栈空，则表明迷宫没有通路。if(栈不空&&栈顶位置尚有其他方向未被探索){新的当前位置为:沿顺时针方向旋转找到的栈顶位置的下一相邻块；}if(栈不空&&栈顶位置的四周均不可通)则｛删去栈顶位置；//从路径中删去该通道块若栈不空，则重新测试新的栈顶位置，直至找到一个可通的相邻块或出栈至栈空；｝3.2.5表达式求解

表达式的三种标识方法：设

exp=S1OP

S2则称OP

S1

S2

为前缀表示法

S1

OP

S2

为中缀表示法

S1

S2

OP

为后缀表示法

例如:exp=a

b

+

(c

d/e)

f前缀式:+

ab

c/def中缀式:a

b

+

c

d/e

f后缀式:ab

cde/

f

+结论:1）操作数之间的相对次序不变;2）运算符的相对次序不同;例如:exp=a

b

+

(c

d/e)

f前缀式:+

ab

c/def中缀式:a

b

+

c

d/e

f后缀式:ab

cde/

f

+结论:3）中缀式丢失了括弧信息，致使运算的次序不确定;例如:exp=a

b

+

(c

d/e)

f前缀式:+

ab

c/def中缀式:a

b

+

c

d/e

f后缀式:ab

cde/

f

+结论:4)前缀式的运算规则为:连续出现的两个操作数和在它们之前且紧靠它们的运算符构成一个最小表达式;例如:exp=a

b

+

(c

d/e)

f前缀式:+

ab

c/def中缀式:a

b

+

c

d/e

f后缀式:ab

cde/

f

+结论:5)后缀式的运算规则为:

运算符在式中出现的顺序恰为表达式的运算顺序;每个运算符和在它之前出现且紧靠它的两个操作数构成一个最小表达式。如何从后缀式求值？先找运算符，再找操作数例如：

ab

cde/

f

+a

bd/ec-d/e(c-d/e)

fa

b-(c-d/e)

f如何从原表达式求得后缀式？

每个运算符的运算次序要由它之后的一个运算符来定，在后缀式中，优先数高的运算符领先于优先数低的运算符。分析“原表达式”和“后缀式”中的运算符:原表达式:a+b

c

d/e

f

后缀式:abc

+de/f

从原表达式求得后缀式的规律为：1)设立运算符栈2)设表达式的结束符为“#”，预设运算符栈的栈底为“#”3)若当前字符是操作数，则直接发送给后缀式4)若当前运算符的优先数高于栈顶运算符，则进栈5)否则，退出栈顶运算符发送给后缀式；

7)

遇表达式结束“#”，连续将栈中运算符退到后缀式。6)“(”对它之前后的运算符起隔离作用，可理解为优先级最低的运算符号，进栈；“)”可视为自相应左括弧开始的表达式的结束符。一直退到栈顶是“(”（符号送后缀式），最后“（”退栈。a

b+(c

d/e)

f##栈后缀表达式：a

b+(c

d/e)

f##栈后缀表达式：a

b+(c

d/e)

f##a后缀表达式：栈a

b+(c

d/e)

f##a

后缀表达式：栈a

b+(c

d/e)

f##a

后缀表达式：栈a

b+(c

d/e)

f##a

b后缀表达式：栈a

b+(c

d/e)

f##ab

后缀表达式：栈a

b+(c

d/e)

f##ab后缀表达式：栈a

b+(c

d/e)

f##ab

后缀表达式：栈a

b+(c

d/e)

f##a+b

后缀表达式：栈a

b+(c

d/e)

f##a+b

后缀表达式：栈a

b+(c

d/e)

f##栈a+b

（后缀表达式：a

b+(c

d/e)

f##栈a+b

（后缀表达式：a

b+(c

d/e)

f##栈a+b

（c后缀表达式：a

b+(c

d/e)

f##a+b

（c后缀表达式：栈a

b+(c

d/e)

f##a+b

（c—后缀表达式：栈a

b+(c

d/e)

f##a+b

（c—后缀表达式：栈a

b+(c

d/e)

f##a+b

（c—d后缀表达式：栈a

b+(c

d/e)

f##a+b

（c—d后缀表达式：栈a

b+(c

d/e)

f##a+b

（c—d/后缀表达式：栈a

b+(c

d/e)

f##a+b

（c—d/后缀表达式：栈a

b+(c

d/e)

f##a+b

（c—d/e后缀表达式：栈a

b+(c

d/e)

f##a+b

（c—d/e后缀表达式：栈a

b+(c

d/e)

f##a+b

（c—de后缀表达式：栈a

b+(c

d/e)

f##a+b

（c—de/后缀表达式：栈a

b+(c

d/e)

f##a+b

（cde/

后缀表达式：栈a

b+(c

d/e)

f##a+b

cde/

后缀表达式：栈a

b+(c

d/e)

f##