2001-3-19
华中科技大学计算机学院 (4)数据结构第三章 栈和队列引言：对线性表 L=(a1,a2,,...,an),
可在任意第 i(i=1,2,,...n,n+1)个位置插入新元素，
或删除任意第 i(i=1,2,,...n)个元素受限数据结构 ---- 插入和删除受限制的线性表。
1.栈 (stack),2.队列 (queue),3.双队列 (deque)
3.1栈 (stack)
3.1.1栈的定义和操作
1.定义和术语
▲ 栈 ----限定在表尾作插入、删除操作的线性表。
(a1,a2,,...,an） ← 插入元素 (进栈 )
↑ ↑ ↘ 删除元素 (出栈）
表头 表尾
(栈底 ) (栈顶）
an
a1
栈顶 (top)
栈底 (bottom)
出栈 (pop) 进栈 (push)
▲ 进栈 ----插入一个元素到栈中。或,入栈、推入、压入,push。
▲ 出栈 ----从栈删除一个元素。或,退栈、上托、弹出,pop。
▲ 栈顶 ----表中允许插入、删除元素的一端 (表尾 )。
▲ 栈顶元素 ----处在栈顶位置的元素。
▲ 栈底 ----表中不允许插入、删除元素的一端。
▲ 空栈 ----不含元素的栈。
栈的示意图
▲ 栈的元素的进出原则,―后进先出,,―Last In First Out‖。
▲ 栈的别名,―后进先出,表,,LIFO‖表、反转存储器、地窖、
堆栈 。
2.栈的基本操作
(1) Initstack(s)----置 s为空栈。
(2) Push(s,e)----元素 e进栈 s。
若 s已满，则发生溢出。
若不能解决溢出，重新分配空间失败，则插入失败。
(3) Pop(s,e)----删除栈 s的顶元素，并送入 e 。
若 s为空栈,发生,下溢,(underflow)；
为空栈时，表示某项任务已完成。
(4) Gettop(s,e)----栈 s的顶元素拷贝到 e。
若 s为空栈，则结束拷贝。
(5) Empty(s)----判断 s是否为空栈。
若 s为空栈,则 Empty(s)为 true；否则为 false。
3.模拟 铁路调度站讨论：
假设依次输入 3个元素 (车厢 )A,B,C到栈 (调度站 )中,
可得当哪几种不同输出？
输入端
A,B,C 进栈进栈出栈输出端调度站 (栈）
(1)输入 A,B,C,产生输出 A,B,C的过程：
A
B,C
(1)A进栈
B,C
(2)A出栈
B
C
(3)B进栈
(4)B出栈
C
(5)C进栈 (6)C出栈
C A,B,C
A
A,B A,B
A
(2)输入 A,B,C,产生输出 C,B,A的过程：
A
B,C
(1)A进栈
B
A
C
(2)B进栈
C
B
A
(3)C进栈
B
A
(4)C出栈
C
(5)B出栈 (6)A出栈
C,B,AC C,B
(3)输入 A,B,C,产生输出 B,C,A的过程,
A
B,C
(1)A进栈
B
A
C
(2)B进栈
A
C
(3)B出栈
C
A
(4)C进栈
A
(5)C出栈 (6)A出栈
B,C,AB B,C
B
当 A,B,C依次进栈,C出栈后，由于栈顶元素是 B,栈底元素是 A,而 A不能先于 B出栈,所以不能在输出序列中,使 A
成为 C的直接后继,即不可能由输入 A,B,C产生输出 C,A,B。
一般地，输入序列 (...,ai,...,aj,...,ak,...)到栈中,不能得到输出序列 (...,ak,...,ai,...,aj,...)。
(1)初始状态
C
B
A
(2)A,B,C进栈
B
A
(3)C出栈
CA,B,C
(4)输入 A,B,C,不能产生输出 C,A,B:
设依次输入元素 A,B,C到栈中,可得哪几种输出?
设依次输入元素 C,B,A到栈中,可得哪几种输出?
A,B,C (1) A,B,C
(2) A,C,B
(3) B,A,C
(4) B,C,A
(5) C,A,B
(6) C,B,A
C,B,A (1) A,B,C
(2) A,C,B
(3) B,A,C
(4) B,C,A
(5) C,A,B
(6) C,B,A
讨论,
假定输入元素 A,B,C,D
到栈中,能得当哪几种输出?
不能得到哪几种输出序列？
(1) A,B,C,D (7) B,A,C,D (13) C,A,B,D (19) D,B,C,A
(2) A,B,D,C (8) B,A,D,C (14) C,A,D,B (20) D,B,A,C
(3) A,C,B,D (9) B,C,A,D (15) C,B,A,D (21) D,C,B,A
(4) A,C,D,B (10) B,C,D,A (16) C,B,D,A (22) D,C,A,B
(5) A,D,B,C (11) B,D,A,C (17) C,D,A,B (23) D,A,B,C
(6) A,D,C,B (12) B,D,C,A (18) C,D,B,A (24) D,A,C,B
共 5+5+3+1=14种
A,B,C,D 输入输出
5种 5种 3种 1种
3.1.2 栈的存储表示和操作实现
1.顺序栈 ----用顺序空间表示的栈。
假设栈空间为 s[1..maxleng]
(1)顶指针指向顶元素所在位置：
top →
栈顶指针栈顶栈底
maxleng
n
2
1
///
///
///
///
///
///
maxleng
2
1
0
自由区自由区
(a) 非空栈,top>0
顶元素 ==s[top] (b) 空栈,top==0
若删除元素，将发生,下溢,
///
///
an
...
a2
a1
序号
top →
序号
top → 栈顶栈底
maxleng
2
1
///
///
an
...
a2
a1
maxleng-1
n-1
1
0
top →
自由区
(c)满栈,top==maxleng
若插入元素,将发生,溢出,
,Overflow‖
(d)设栈空间为,s[0..maxleng-1]
元素的下标,0,1,...,n-1
top==n-1
an
...
...
...
a2
a1 栈底栈顶
(2)顶指针指向顶元素所在位置的下一个空位置设栈空间为 s[1..maxleng]：
top →
栈顶栈底
maxleng
n+1
n
1
///
///
///
///
///
///
maxleng
2
1
(a)非空栈,top>=2
顶元素 ==s[top-1]
(b)空栈,top==1
s[top]无意义
///
///
///
an
...
a1 top →
(2)顶指针指向顶元素所在位置的下一个空位置设栈空间为 s[1..maxleng]：
an
...
ai
...
a2
a1
maxleng+1
maxleng
2
1
(c)满栈,top==maxleng+1
s[top]不存在
top →
2.顺序栈的描述,进栈、出栈算法
(1)栈的元素空间 s与顶指针 top分别定义
a) s和 top的分别定义
#define maxleng 100
Elemtype s[maxleng+1]；
int st=0,*top=&st； //初始化
b) 进栈算法
void push_s(Elemtype s[ ],int *top,Elemtype e)
//将元素 e压入栈 s中,(*top)指向顶元素
{ if ((*top)==maxleng)
exit("Overflow")； //会发生溢出,退出
(*top)++； //修改顶指针
s[*top]=e； //装入元素 e
}
maxleng
2
1
0top → st →
空栈,st==0
*top==0
c) 出栈算法
void pop_s(Elemtype s[],int *top,Elemtype *e)
//将栈 s的顶元素送 e所指的变量,并删除顶元素
{ if ((*top)==0) //为空栈
exit("underflow")； //会发生下溢,退出
(*e)=s[*top]； //顶元素送 e所指的变量
(*top)—； //修改顶指针
}
(2) 栈元素与顶指针合并定义为一个 记录 (结构 )
<a> 静态分配
typedef struct
{ ElemType elem[maxleng+1]； //栈元素空间
int top； //顶指针
}sqstack； //sqstack为结构类型
sqstack s； //s为结构类型变量其中,s.top----顶指针； s.elem[s.top]----顶元素
<b> 动态分配
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
typedef struct
{ ElemType *base； //栈元素空间
int top； //顶指针
int stacksize
}SqStack； // SqStack为结构类型
SqStack s； //s为结构类型变量其中,s.top----顶指针； s.base[s.top]----顶元素
3.链式栈 ----使用不带表头结点的单链表
(1)结点和指针的定义
struct node
{ ElemType data； //data为抽象元素类型
struct node *next； //next为指针类型
} *top=NULL； //初始化,置 top为 空栈
(2)非空链式栈 的一般形式
an
a(n-1)
a1 ^
data next
top 栈顶栈底
(3)链式栈的 进栈算法,//压入元素 e到 top为顶指针的链式栈
struct node *push_link(struct node *top,Elemtype e)
{ struct node *p；
int leng=sizeof(struct node)； //确定新结点空间的大小
p=(struct node *)malloc(leng)； //生成新结点
p->data=e； //装入元素 e
p->next=top； //插入新结点
top=p； //top指向新结点
return top； //返回指针 top
}
an a1 ^ 栈底top
ep
X
an a1 ^ 栈底top e
...
...
栈顶栈顶
(1)插入 e之前：
(2)插入 e之后：
3.1栈的应用举例栈的基本用途 ----保存暂时不用的数或存储地址。
3.2.1 数制转换例,给定十进制数 N=1348,转换为八进制数 R=2504
1.依次求余数,并送入栈中，直到商为 0。
(1) r1=1348%8=4 //求余数
n1=1348/8=168 //求商
(2) r2=168%8=0 //求余数
n2=168/8=21 //求商
(3) r3=21%8=5 //求余数
n3=21/8=2 //求商
(4) r4=2%8=2 //求余数
n4=2/8=0 //求商
2.依次退栈,得 R=2504
4
0
4
5
0
4
2
5
0
4
(1) 4进栈 (2) 0进栈
(3) 5进栈 (4) 2进栈
3.2.2 判定表达式中的刮号匹配
1.刮号匹配的表达式例,{...(...( )...)...}
[...{...( )...( )...}...]
2.刮号不匹配的表达式例,{...[ }...]
[...(...( )...)...)
3.判定刮号不匹配的方法例,(,..{,..{,..}...]
↑ ↑ ↑ ↑ ↑
(1) (2) (3) (4) (5)
(
{
(
{
{
(
{
(
(1)―(‖进栈 (2)―{‖进栈
(3)―{‖进栈 (4)―{‖退栈
{
(
(5)―]‖与,{‖不匹配
3.2.3 行编辑程序例,data stru**cture
↑ ↑
栈底 栈顶
← 输入文本 (进栈 )
data stru
↑ ↑
栈底 栈顶
e,r,u,t,c,*,*退栈
data stru
↑ ↑
栈底 栈顶
← 再输入文本 cture
data structure
↑ ↑
栈底 栈顶
3.2.4 表达式求值例,4 + 2 * 3 – 10 / ( 7 – 5 )
① ③
② ④
⑤
求值规则,
1.先乘除,后加减；
2.先括号内,后括号外；
3.同类运算,从左至右。
约定,
1----左算符
2----右算符
1=#，为开始符
2=#，为结束符算符优先关系表
+ - * / （ ） #
+
-
*
/
（
）
#
> > < < < > >
> > < < < > >
> > > > < > >
> > > > < > >
< < < < < =
> > > > > >
< < < < < =
1?2
算法思想,
设立,s1----操作数栈,存放暂不运算的数和中间结果
s2----算符栈,存放暂不运算的算符
1,置 s1,s2为空栈；开始符 #进 s2；
2,从表达式读取,单词,w----操作数 /算符
3,当 w!=?#‘ || s2的顶算符 !=?#‘ 时重复：
3.1 若 w为操作数，则 w进 s1,读取下一,单词,w；
3.2 若 w为算符，则：
3.2.1 若 w(?2)>s2的顶算符 (?1)，则 w进 s2；读取下一,单词,w；
3.2.2 若 w(?2)=s2的顶算符 (?1)，且 w=―)‖，则取括号，
pop(s2)； 读取下一,单词,w；
3.2.3 若 w(?2)<s2的顶算符 (?1)，则：
{ pop(s1,a)； pop(s1,b)； pop(s2,op)；
c=b op a； push(s1,c)； /*op为?1*/
}
4,s1的栈顶元素为表达式的值。
s1 s2
例,# 4 + 2 * 3 – 12 / ( 7 – 5 ) #
4 #
2
4
+
#
3
2
4
*
+
# 4
+
#
6
4
+
# # 10 #
12
10
/
-
#
s1 s2 s1 s2 s1 s2 s1 s2
s1 s2 s1 s2 s1 s2 s1 s2
a=3； b=2； op=*； c=2*3=6；
a=6； b=4； op=+； c=4+6=10；
例,# 4 + 2 * 3 – 12 / ( 7 – 5 ) #
12
10
（
/
-
#
5
7
12
10
-
（
/
-
#
12
10
（
/
-
#
a=5； b=7； 0p=“-”； c=7-5=2；
2
12
10
（
/
-
#
2
12
10
/
-
# 10
-
#
a=2； b=12； 0p=“/”； c=12/2=6； a=6； b=10； c=10-6=4；
6
10
-
# #
s1 s2 s1 s2 s1 s2 s1 s2
s1 s2 s1 s2 s1 s2 s1 s2
例,# 4 + 2 * 3 – 12 / ( 7 – 5 ) #
4 #
s1 s2
栈 s1最后的顶 (底 )元素为表达式的值
→
3.4 队列（排队,queue)
3.4.1 队列及其操作
1.定义和术语
▲ 队列 ----只允许在表的一端删除元素,在另一端插入元素的线性表 。
▲ 空队列 ----不含元素的队列 。
▲ 队首 ----队列中只允许删除元素的一端 。 head,front
▲ 队尾 ----队列中只允许插入元素的一端 。 rear,tail
▲ 队首元素 ----处于队首的元素 。
▲ 队尾元素 ----处于队尾的元素 。
▲ 进队 ----插入一个元素到队列中 。 又称：入队 。
▲ 出队 ----从队列删除一个元素 。
2.元素的进出原则,―先进先出”，,First In First Out‖
队列的别名,―先进先出,表,,FIFO‖ 表，排队,queue
队列示意图
a1,a2,......,an
↑ ↑
head(front) rear(tail)
队首 队尾
← 进队出队 ←
3.队列的基本操作：
(1)InitQueue(q)---- 初始化,将 q置为空队列。
(2)QueueEmpty(q)----判断 q是否为空队列。
(3)EnQueue(q,e)---- 将 e插入队列 q的尾端。
(4)DeQueue(q,e)---- 取走队列 q的首元素,送 e。
(5)QetHead(q,e)---- 读取队列 q的首元素,送 e 。
(6)QueueClear(q)----置 q为空队列。
4.双队列 （ 双端队列,deque----double ended queue)
(1)双队列 ----只许在表的两端插入、删除元素的线性表。
双队列示意图
a1,a2,.....,an 进队出队输出受限双队列示意图
a1,a2,.....,an 进队出队
(2)输出受限双队列 ----只许在表的两端插入、在一端删除元素的线性表。
队首 队尾队首 队尾输入受限双队列示意图
a1,a2,.....,an 进队出队
(3)输入受限双队列 ----只允许在表的一端插入、在两端删除元素的线性表。
队首 队尾作业：
1.设输入元素 B,C,A,D到栈中,能得当哪几种输出?
不能得到哪几种输出序列？
(1) A,B,C,D (7) B,A,C,D (13) C,A,B,D (19) D,B,C,A
(2) A,B,D,C (8) B,A,D,C (14) C,A,D,B (20) D,B,A,C
(3) A,C,B,D (9) B,C,A,D (15) C,B,A,D (21) D,C,B,A
(4) A,C,D,B (10) B,C,D,A (16) C,B,D,A (22) D,C,A,B
(5) A,D,B,C (11) B,D,A,C (17) C,D,A,B (23) D,A,B,C
(6) A,D,C,B (12) B,D,C,A (18) C,D,B,A (24) D,A,C,B
2.设链式栈的栈顶头指针为 top，弹出栈顶元素送 e,试写出退栈算法 pop(top,e)。
华中科技大学计算机学院 (4)数据结构第三章 栈和队列引言：对线性表 L=(a1,a2,,...,an),
可在任意第 i(i=1,2,,...n,n+1)个位置插入新元素，
或删除任意第 i(i=1,2,,...n)个元素受限数据结构 ---- 插入和删除受限制的线性表。
1.栈 (stack),2.队列 (queue),3.双队列 (deque)
3.1栈 (stack)
3.1.1栈的定义和操作
1.定义和术语
▲ 栈 ----限定在表尾作插入、删除操作的线性表。
(a1,a2,,...,an） ← 插入元素 (进栈 )
↑ ↑ ↘ 删除元素 (出栈）
表头 表尾
(栈底 ) (栈顶）
an
a1
栈顶 (top)
栈底 (bottom)
出栈 (pop) 进栈 (push)
▲ 进栈 ----插入一个元素到栈中。或,入栈、推入、压入,push。
▲ 出栈 ----从栈删除一个元素。或,退栈、上托、弹出,pop。
▲ 栈顶 ----表中允许插入、删除元素的一端 (表尾 )。
▲ 栈顶元素 ----处在栈顶位置的元素。
▲ 栈底 ----表中不允许插入、删除元素的一端。
▲ 空栈 ----不含元素的栈。
栈的示意图
▲ 栈的元素的进出原则,―后进先出,,―Last In First Out‖。
▲ 栈的别名,―后进先出,表,,LIFO‖表、反转存储器、地窖、
堆栈 。
2.栈的基本操作
(1) Initstack(s)----置 s为空栈。
(2) Push(s,e)----元素 e进栈 s。
若 s已满，则发生溢出。
若不能解决溢出，重新分配空间失败，则插入失败。
(3) Pop(s,e)----删除栈 s的顶元素，并送入 e 。
若 s为空栈,发生,下溢,(underflow)；
为空栈时，表示某项任务已完成。
(4) Gettop(s,e)----栈 s的顶元素拷贝到 e。
若 s为空栈，则结束拷贝。
(5) Empty(s)----判断 s是否为空栈。
若 s为空栈,则 Empty(s)为 true；否则为 false。
3.模拟 铁路调度站讨论：
假设依次输入 3个元素 (车厢 )A,B,C到栈 (调度站 )中,
可得当哪几种不同输出？
输入端
A,B,C 进栈进栈出栈输出端调度站 (栈）
(1)输入 A,B,C,产生输出 A,B,C的过程：
A
B,C
(1)A进栈
B,C
(2)A出栈
B
C
(3)B进栈
(4)B出栈
C
(5)C进栈 (6)C出栈
C A,B,C
A
A,B A,B
A
(2)输入 A,B,C,产生输出 C,B,A的过程：
A
B,C
(1)A进栈
B
A
C
(2)B进栈
C
B
A
(3)C进栈
B
A
(4)C出栈
C
(5)B出栈 (6)A出栈
C,B,AC C,B
(3)输入 A,B,C,产生输出 B,C,A的过程,
A
B,C
(1)A进栈
B
A
C
(2)B进栈
A
C
(3)B出栈
C
A
(4)C进栈
A
(5)C出栈 (6)A出栈
B,C,AB B,C
B
当 A,B,C依次进栈,C出栈后，由于栈顶元素是 B,栈底元素是 A,而 A不能先于 B出栈,所以不能在输出序列中,使 A
成为 C的直接后继,即不可能由输入 A,B,C产生输出 C,A,B。
一般地，输入序列 (...,ai,...,aj,...,ak,...)到栈中,不能得到输出序列 (...,ak,...,ai,...,aj,...)。
(1)初始状态
C
B
A
(2)A,B,C进栈
B
A
(3)C出栈
CA,B,C
(4)输入 A,B,C,不能产生输出 C,A,B:
设依次输入元素 A,B,C到栈中,可得哪几种输出?
设依次输入元素 C,B,A到栈中,可得哪几种输出?
A,B,C (1) A,B,C
(2) A,C,B
(3) B,A,C
(4) B,C,A
(5) C,A,B
(6) C,B,A
C,B,A (1) A,B,C
(2) A,C,B
(3) B,A,C
(4) B,C,A
(5) C,A,B
(6) C,B,A
讨论,
假定输入元素 A,B,C,D
到栈中,能得当哪几种输出?
不能得到哪几种输出序列？
(1) A,B,C,D (7) B,A,C,D (13) C,A,B,D (19) D,B,C,A
(2) A,B,D,C (8) B,A,D,C (14) C,A,D,B (20) D,B,A,C
(3) A,C,B,D (9) B,C,A,D (15) C,B,A,D (21) D,C,B,A
(4) A,C,D,B (10) B,C,D,A (16) C,B,D,A (22) D,C,A,B
(5) A,D,B,C (11) B,D,A,C (17) C,D,A,B (23) D,A,B,C
(6) A,D,C,B (12) B,D,C,A (18) C,D,B,A (24) D,A,C,B
共 5+5+3+1=14种
A,B,C,D 输入输出
5种 5种 3种 1种
3.1.2 栈的存储表示和操作实现
1.顺序栈 ----用顺序空间表示的栈。
假设栈空间为 s[1..maxleng]
(1)顶指针指向顶元素所在位置：
top →
栈顶指针栈顶栈底
maxleng
n
2
1
///
///
///
///
///
///
maxleng
2
1
0
自由区自由区
(a) 非空栈,top>0
顶元素 ==s[top] (b) 空栈,top==0
若删除元素，将发生,下溢,
///
///
an
...
a2
a1
序号
top →
序号
top → 栈顶栈底
maxleng
2
1
///
///
an
...
a2
a1
maxleng-1
n-1
1
0
top →
自由区
(c)满栈,top==maxleng
若插入元素,将发生,溢出,
,Overflow‖
(d)设栈空间为,s[0..maxleng-1]
元素的下标,0,1,...,n-1
top==n-1
an
...
...
...
a2
a1 栈底栈顶
(2)顶指针指向顶元素所在位置的下一个空位置设栈空间为 s[1..maxleng]：
top →
栈顶栈底
maxleng
n+1
n
1
///
///
///
///
///
///
maxleng
2
1
(a)非空栈,top>=2
顶元素 ==s[top-1]
(b)空栈,top==1
s[top]无意义
///
///
///
an
...
a1 top →
(2)顶指针指向顶元素所在位置的下一个空位置设栈空间为 s[1..maxleng]：
an
...
ai
...
a2
a1
maxleng+1
maxleng
2
1
(c)满栈,top==maxleng+1
s[top]不存在
top →
2.顺序栈的描述,进栈、出栈算法
(1)栈的元素空间 s与顶指针 top分别定义
a) s和 top的分别定义
#define maxleng 100
Elemtype s[maxleng+1]；
int st=0,*top=&st； //初始化
b) 进栈算法
void push_s(Elemtype s[ ],int *top,Elemtype e)
//将元素 e压入栈 s中,(*top)指向顶元素
{ if ((*top)==maxleng)
exit("Overflow")； //会发生溢出,退出
(*top)++； //修改顶指针
s[*top]=e； //装入元素 e
}
maxleng
2
1
0top → st →
空栈,st==0
*top==0
c) 出栈算法
void pop_s(Elemtype s[],int *top,Elemtype *e)
//将栈 s的顶元素送 e所指的变量,并删除顶元素
{ if ((*top)==0) //为空栈
exit("underflow")； //会发生下溢,退出
(*e)=s[*top]； //顶元素送 e所指的变量
(*top)—； //修改顶指针
}
(2) 栈元素与顶指针合并定义为一个 记录 (结构 )
<a> 静态分配
typedef struct
{ ElemType elem[maxleng+1]； //栈元素空间
int top； //顶指针
}sqstack； //sqstack为结构类型
sqstack s； //s为结构类型变量其中,s.top----顶指针； s.elem[s.top]----顶元素
<b> 动态分配
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
typedef struct
{ ElemType *base； //栈元素空间
int top； //顶指针
int stacksize
}SqStack； // SqStack为结构类型
SqStack s； //s为结构类型变量其中,s.top----顶指针； s.base[s.top]----顶元素
3.链式栈 ----使用不带表头结点的单链表
(1)结点和指针的定义
struct node
{ ElemType data； //data为抽象元素类型
struct node *next； //next为指针类型
} *top=NULL； //初始化,置 top为 空栈
(2)非空链式栈 的一般形式
an
a(n-1)
a1 ^
data next
top 栈顶栈底
(3)链式栈的 进栈算法,//压入元素 e到 top为顶指针的链式栈
struct node *push_link(struct node *top,Elemtype e)
{ struct node *p；
int leng=sizeof(struct node)； //确定新结点空间的大小
p=(struct node *)malloc(leng)； //生成新结点
p->data=e； //装入元素 e
p->next=top； //插入新结点
top=p； //top指向新结点
return top； //返回指针 top
}
an a1 ^ 栈底top
ep
X
an a1 ^ 栈底top e
...
...
栈顶栈顶
(1)插入 e之前：
(2)插入 e之后：
3.1栈的应用举例栈的基本用途 ----保存暂时不用的数或存储地址。
3.2.1 数制转换例,给定十进制数 N=1348,转换为八进制数 R=2504
1.依次求余数,并送入栈中，直到商为 0。
(1) r1=1348%8=4 //求余数
n1=1348/8=168 //求商
(2) r2=168%8=0 //求余数
n2=168/8=21 //求商
(3) r3=21%8=5 //求余数
n3=21/8=2 //求商
(4) r4=2%8=2 //求余数
n4=2/8=0 //求商
2.依次退栈,得 R=2504
4
0
4
5
0
4
2
5
0
4
(1) 4进栈 (2) 0进栈
(3) 5进栈 (4) 2进栈
3.2.2 判定表达式中的刮号匹配
1.刮号匹配的表达式例,{...(...( )...)...}
[...{...( )...( )...}...]
2.刮号不匹配的表达式例,{...[ }...]
[...(...( )...)...)
3.判定刮号不匹配的方法例,(,..{,..{,..}...]
↑ ↑ ↑ ↑ ↑
(1) (2) (3) (4) (5)
(
{
(
{
{
(
{
(
(1)―(‖进栈 (2)―{‖进栈
(3)―{‖进栈 (4)―{‖退栈
{
(
(5)―]‖与,{‖不匹配
3.2.3 行编辑程序例,data stru**cture
↑ ↑
栈底 栈顶
← 输入文本 (进栈 )
data stru
↑ ↑
栈底 栈顶
e,r,u,t,c,*,*退栈
data stru
↑ ↑
栈底 栈顶
← 再输入文本 cture
data structure
↑ ↑
栈底 栈顶
3.2.4 表达式求值例,4 + 2 * 3 – 10 / ( 7 – 5 )
① ③
② ④
⑤
求值规则,
1.先乘除,后加减；
2.先括号内,后括号外；
3.同类运算,从左至右。
约定,
1----左算符
2----右算符
1=#，为开始符
2=#，为结束符算符优先关系表
+ - * / （ ） #
+
-
*
/
（
）
#
> > < < < > >
> > < < < > >
> > > > < > >
> > > > < > >
< < < < < =
> > > > > >
< < < < < =
1?2
算法思想,
设立,s1----操作数栈,存放暂不运算的数和中间结果
s2----算符栈,存放暂不运算的算符
1,置 s1,s2为空栈；开始符 #进 s2；
2,从表达式读取,单词,w----操作数 /算符
3,当 w!=?#‘ || s2的顶算符 !=?#‘ 时重复：
3.1 若 w为操作数，则 w进 s1,读取下一,单词,w；
3.2 若 w为算符，则：
3.2.1 若 w(?2)>s2的顶算符 (?1)，则 w进 s2；读取下一,单词,w；
3.2.2 若 w(?2)=s2的顶算符 (?1)，且 w=―)‖，则取括号，
pop(s2)； 读取下一,单词,w；
3.2.3 若 w(?2)<s2的顶算符 (?1)，则：
{ pop(s1,a)； pop(s1,b)； pop(s2,op)；
c=b op a； push(s1,c)； /*op为?1*/
}
4,s1的栈顶元素为表达式的值。
s1 s2
例,# 4 + 2 * 3 – 12 / ( 7 – 5 ) #
4 #
2
4
+
#
3
2
4
*
+
# 4
+
#
6
4
+
# # 10 #
12
10
/
-
#
s1 s2 s1 s2 s1 s2 s1 s2
s1 s2 s1 s2 s1 s2 s1 s2
a=3； b=2； op=*； c=2*3=6；
a=6； b=4； op=+； c=4+6=10；
例,# 4 + 2 * 3 – 12 / ( 7 – 5 ) #
12
10
（
/
-
#
5
7
12
10
-
（
/
-
#
12
10
（
/
-
#
a=5； b=7； 0p=“-”； c=7-5=2；
2
12
10
（
/
-
#
2
12
10
/
-
# 10
-
#
a=2； b=12； 0p=“/”； c=12/2=6； a=6； b=10； c=10-6=4；
6
10
-
# #
s1 s2 s1 s2 s1 s2 s1 s2
s1 s2 s1 s2 s1 s2 s1 s2
例,# 4 + 2 * 3 – 12 / ( 7 – 5 ) #
4 #
s1 s2
栈 s1最后的顶 (底 )元素为表达式的值
→
3.4 队列（排队,queue)
3.4.1 队列及其操作
1.定义和术语
▲ 队列 ----只允许在表的一端删除元素,在另一端插入元素的线性表 。
▲ 空队列 ----不含元素的队列 。
▲ 队首 ----队列中只允许删除元素的一端 。 head,front
▲ 队尾 ----队列中只允许插入元素的一端 。 rear,tail
▲ 队首元素 ----处于队首的元素 。
▲ 队尾元素 ----处于队尾的元素 。
▲ 进队 ----插入一个元素到队列中 。 又称：入队 。
▲ 出队 ----从队列删除一个元素 。
2.元素的进出原则,―先进先出”，,First In First Out‖
队列的别名,―先进先出,表,,FIFO‖ 表，排队,queue
队列示意图
a1,a2,......,an
↑ ↑
head(front) rear(tail)
队首 队尾
← 进队出队 ←
3.队列的基本操作：
(1)InitQueue(q)---- 初始化,将 q置为空队列。
(2)QueueEmpty(q)----判断 q是否为空队列。
(3)EnQueue(q,e)---- 将 e插入队列 q的尾端。
(4)DeQueue(q,e)---- 取走队列 q的首元素,送 e。
(5)QetHead(q,e)---- 读取队列 q的首元素,送 e 。
(6)QueueClear(q)----置 q为空队列。
4.双队列 （ 双端队列,deque----double ended queue)
(1)双队列 ----只许在表的两端插入、删除元素的线性表。
双队列示意图
a1,a2,.....,an 进队出队输出受限双队列示意图
a1,a2,.....,an 进队出队
(2)输出受限双队列 ----只许在表的两端插入、在一端删除元素的线性表。
队首 队尾队首 队尾输入受限双队列示意图
a1,a2,.....,an 进队出队
(3)输入受限双队列 ----只允许在表的一端插入、在两端删除元素的线性表。
队首 队尾作业：
1.设输入元素 B,C,A,D到栈中,能得当哪几种输出?
不能得到哪几种输出序列？
(1) A,B,C,D (7) B,A,C,D (13) C,A,B,D (19) D,B,C,A
(2) A,B,D,C (8) B,A,D,C (14) C,A,D,B (20) D,B,A,C
(3) A,C,B,D (9) B,C,A,D (15) C,B,A,D (21) D,C,B,A
(4) A,C,D,B (10) B,C,D,A (16) C,B,D,A (22) D,C,A,B
(5) A,D,B,C (11) B,D,A,C (17) C,D,A,B (23) D,A,B,C
(6) A,D,C,B (12) B,D,C,A (18) C,D,B,A (24) D,A,C,B
2.设链式栈的栈顶头指针为 top，弹出栈顶元素送 e,试写出退栈算法 pop(top,e)。
