第3章 栈与队列
- 格式：doc
- 大小：40.00 KB
- 文档页数：4
下载文档原格式
合集下载
数据结构课件第3章
0
1
2
3
4
5
6
7
a1
a2
a3
a4
a5
a6
a7
队头 F＝0
队尾 R＝7
a3 2 1 3 0 4 7 a3 5 6 3 a2 2 1 a1 0 F=0 a4 4 a5 5 6 a6 7 a7 R=0 R=7 3 a2 2 1 a1 0
a4 4 a5 5 6 a6 7
a8
F=0
a7
R=0
F=0
删除所有元素
top X W … B top
top=0 空栈
top
W
…
B A
top=m-1 元素X出栈
top
A
A
top=m 满栈
top=1 元素A入栈
例：堆栈的插入、删除操作。 出栈操作程序如下： # define m 1000; /*最大栈空间*/ 出栈操作算法： 1）栈顶指针top是否为0： typedef struct stack_stru 若是，则返回；若不是， { int s[m]; int top; }; 则执行2。 void pop (stack, y) 2）将栈顶元素送给y， struct stack_stru stack; 栈顶指针减1。 int *y; { if (stack.top = = 0) printf (“The stack is empty ! \n”); top Y Y else { top B B *y=stack.s[stack.top]; A A stack.top - -; } 出栈操作 }
top=p;
} 栈的入栈、出栈操作的时间复杂度都为O(1)。
栈的应用
一、 表达式求值 表达式由操作数、运算符和界限符组成。 运算符可包括算术运算符、关系运算符、逻辑运算符。
大学数据结构课件--第3章 栈和队列
top top 栈空 F E D C B A
栈满 top-base=stacksize
top
F
E
D C B
top top top top top top base
入栈PUSH(s,x):s[top++]=x; top 出栈 POP(s,x):x=s[--top]; top
base
4
A
3.1 栈
例1：一个栈的输入序列为1,2,3，若在入栈的过程中 允许出栈，则可能得到的出栈序列是什么？ 答： 可以通过穷举所有可能性来求解：
3.2 栈的应用举例
二、表达式求值
“算符优先法”
一个表达式由操作数、运算符和界限符组成。 # 例如：3*（7-2*3） （1）要正确求值，首先了解算术四则运算的规则 a.从左算到右 b.先乘除后加减 c.先括号内，后括号外 所以，3*（7-2*3）=3*(7-6)=3*1=3
9
3.2 栈的应用举例
InitStack(S); while (!QueueEmpty(Q))
{DeQueue(Q,d);push(S,d);}
while (!StackEmpty(S)) {pop(S,d);EnQueue(Q,d);} }
第3章 栈和队列
教学要求：
1、掌握栈和队列的定义、特性，并能正确应用它们解决实 际问题；
用一组地址连续的存储单元依次存放从队头到队尾的元素， 设指针front和rear分别指示队头元素和队尾元素的位置。
Q.rear 5 4 Q.rear 3 2 3 2 5 4 Q.rear 3 3 5 4 5 4
F E D C
C B A
Q.front
2 1 0
C B
Q.front 2 1 0
栈满 top-base=stacksize
top
F
E
D C B
top top top top top top base
入栈PUSH(s,x):s[top++]=x; top 出栈 POP(s,x):x=s[--top]; top
base
4
A
3.1 栈
例1：一个栈的输入序列为1,2,3，若在入栈的过程中 允许出栈，则可能得到的出栈序列是什么？ 答： 可以通过穷举所有可能性来求解：
3.2 栈的应用举例
二、表达式求值
“算符优先法”
一个表达式由操作数、运算符和界限符组成。 # 例如：3*（7-2*3） （1）要正确求值，首先了解算术四则运算的规则 a.从左算到右 b.先乘除后加减 c.先括号内，后括号外 所以，3*（7-2*3）=3*(7-6)=3*1=3
9
3.2 栈的应用举例
InitStack(S); while (!QueueEmpty(Q))
{DeQueue(Q,d);push(S,d);}
while (!StackEmpty(S)) {pop(S,d);EnQueue(Q,d);} }
第3章 栈和队列
教学要求：
1、掌握栈和队列的定义、特性，并能正确应用它们解决实 际问题；
用一组地址连续的存储单元依次存放从队头到队尾的元素， 设指针front和rear分别指示队头元素和队尾元素的位置。
Q.rear 5 4 Q.rear 3 2 3 2 5 4 Q.rear 3 3 5 4 5 4
F E D C
C B A
Q.front
2 1 0
C B
Q.front 2 1 0
数据结构栈和队列ppt课件
栈的运用 例3.1 将一个十进制正整数N转换成r进制的数
N 〕
1835
229
28
3
N / 8 〔整除〕 N % 8〔求余
229
3
低
28
5
3
4
0
3
高
❖例3.2 算术表达式中括号匹配的检查
❖用栈来实现括号匹配检查的原那么是，对表达式从左 到右扫描。
❖〔1〕当遇到左括号时，左括号入栈；
❖〔2〕当遇到右括号时，首先检查栈能否空，假设栈 空，那么阐明该“右括弧〞多余；否那么比较栈顶左 括号能否与当前右括号匹配，假设匹配，将栈顶左括 号出栈，继续操作；否那么，阐明不匹配，停顿操作 。
❖在顺序栈上实现五种根本运算的C函数 ❖〔3〕入栈 ❖int push (SeqStack *s, DataType x) ❖{ if (s->top==MAXSIZE-1) /*栈满不能入栈*/ ❖{ printf("overflow"); ❖return 0; ❖} ❖ s->top++; ❖ s->data[s->top]=x; ❖ return 1; ❖}
链队列及运算的实现
采用链接方法存储的队列称为链队列〔Linked Queue〕
采用带头结点的单链表来实现链队列，链队列中 的t结ype点de类f st型ruc与t N单od链e 表一样。将头指针front和尾指针 re{arD封at装aTy在pe一da个ta;构造体中，链队列用C言语描画如 下：struct Node *next;
❖只设了一个尾指针r ❖头结点的指针，即r->next ❖队头元素的指针为r->next->next ❖队空的断定条件是r->next==r
《数据结构(C语言)》第3章 栈和队列
Data structures
栈
❖ 栈的顺序存储与操作 ❖ 1.顺序栈的定义
(1) 栈的静态分配顺序存储结构描述 ② top为整数且指向栈顶元素 当top为整数且指向栈顶元素时，栈空、入栈、栈满 及出栈的情况如图3.2所示。初始化条件为 S.top=-1。
(a) 栈空S.top==-1 (b) 元素入栈S.stack[++S.top]=e (c) 栈满S.top>=StackSize-1 (d) 元素出栈e=S.stack[S.top--]
/*栈顶指针，可以指向栈顶
元素的下一个位置或者指向栈顶元素*/
int StackSize; /*当前分配的栈可使用的以 元素为单位的最大存储容量*/
}SqStack;
/*顺序栈*/
Data structures
栈
❖ 栈的顺序存储与操作 ❖ 1.顺序栈的定义
(2) 栈的动态分配顺序存储结构描述 ① top为指针且指向栈顶元素的下一个位置 当top为指针且指向栈顶元素的下一个位置时，栈空 、入栈、栈满及出栈的情况如图3.3所示。初始化条 件为S.top=S.base。
…，n-1，n≥0} 数据关系：R={< ai-1，ai>| ai-1，ai∈D，i=1，2
，…，n-1 } 约定an-1端为栈顶，a0端为栈底 基本操作：
(1) 初始化操作：InitStack(&S) 需要条件：栈S没有被创建过 操作结果：构建一个空的栈S (2) 销毁栈：DestroyStack(&S) 需要条件：栈S已经被创建 操作结果：清空栈S的所有值，释放栈S占用的内存空间
return 1;
}
Data structures
栈
栈
❖ 栈的顺序存储与操作 ❖ 1.顺序栈的定义
(1) 栈的静态分配顺序存储结构描述 ② top为整数且指向栈顶元素 当top为整数且指向栈顶元素时，栈空、入栈、栈满 及出栈的情况如图3.2所示。初始化条件为 S.top=-1。
(a) 栈空S.top==-1 (b) 元素入栈S.stack[++S.top]=e (c) 栈满S.top>=StackSize-1 (d) 元素出栈e=S.stack[S.top--]
/*栈顶指针，可以指向栈顶
元素的下一个位置或者指向栈顶元素*/
int StackSize; /*当前分配的栈可使用的以 元素为单位的最大存储容量*/
}SqStack;
/*顺序栈*/
Data structures
栈
❖ 栈的顺序存储与操作 ❖ 1.顺序栈的定义
(2) 栈的动态分配顺序存储结构描述 ① top为指针且指向栈顶元素的下一个位置 当top为指针且指向栈顶元素的下一个位置时，栈空 、入栈、栈满及出栈的情况如图3.3所示。初始化条 件为S.top=S.base。
…，n-1，n≥0} 数据关系：R={< ai-1，ai>| ai-1，ai∈D，i=1，2
，…，n-1 } 约定an-1端为栈顶，a0端为栈底 基本操作：
(1) 初始化操作：InitStack(&S) 需要条件：栈S没有被创建过 操作结果：构建一个空的栈S (2) 销毁栈：DestroyStack(&S) 需要条件：栈S已经被创建 操作结果：清空栈S的所有值，释放栈S占用的内存空间
return 1;
}
Data structures
栈
第3章_栈和队列
第三章 栈和队列
（Chapter 3. பைடு நூலகம்tack and Queue)
栈的概念、存储结构及其基本操作
栈的应用举例 队列的概念、存储结构及其基本操作
§3.1 栈
3.1.1 栈的定义及基本运算
• 定义：只能在表尾（栈顶）进行插入和删除操 作进行的线性表。 • 特点: 后进先出(LIFO—Last In First Out )
top 栈顶
an an-1
. . .
a1 ∧
栈底
空栈： top == NULL
16
入栈
LinkStack Push_LS (LinkStack top，datatype x) { StackNode *p ; top p = (StackNode *) malloc (sizeof( StackNode)); p->data = x; top p->next = top; top = p; return top; }
23
2
括号匹配的检验：
问题：两种括号，可以嵌套使用，但不能重叠 解决：使用栈。 ｛（［ ］［ ］）｝ 左括号进栈， 右括号就从栈顶出栈一个左括号， 检查是否能够匹配。 算法开始和结束时，栈都应该是空的。
匹配一个字符串中的左、右括号。如
[ a * ( b + c ) + d ]
( 出栈
( )匹配
[ 出栈
3.1.2 栈的存储及运算实现
顺序栈 -- 栈的顺序存储表示 链栈 -- 栈的链式存储表示
4
1 顺序栈
顺序栈类型的定义 – 本质 顺序表的简化，唯一需要确定的是栈顶、栈底。 – 通常 栈底：下标为0的一端 栈顶：由top指示，空栈时top=-1
（Chapter 3. பைடு நூலகம்tack and Queue)
栈的概念、存储结构及其基本操作
栈的应用举例 队列的概念、存储结构及其基本操作
§3.1 栈
3.1.1 栈的定义及基本运算
• 定义：只能在表尾（栈顶）进行插入和删除操 作进行的线性表。 • 特点: 后进先出(LIFO—Last In First Out )
top 栈顶
an an-1
. . .
a1 ∧
栈底
空栈： top == NULL
16
入栈
LinkStack Push_LS (LinkStack top，datatype x) { StackNode *p ; top p = (StackNode *) malloc (sizeof( StackNode)); p->data = x; top p->next = top; top = p; return top; }
23
2
括号匹配的检验：
问题：两种括号，可以嵌套使用，但不能重叠 解决：使用栈。 ｛（［ ］［ ］）｝ 左括号进栈， 右括号就从栈顶出栈一个左括号， 检查是否能够匹配。 算法开始和结束时，栈都应该是空的。
匹配一个字符串中的左、右括号。如
[ a * ( b + c ) + d ]
( 出栈
( )匹配
[ 出栈
3.1.2 栈的存储及运算实现
顺序栈 -- 栈的顺序存储表示 链栈 -- 栈的链式存储表示
4
1 顺序栈
顺序栈类型的定义 – 本质 顺序表的简化，唯一需要确定的是栈顶、栈底。 – 通常 栈底：下标为0的一端 栈顶：由top指示，空栈时top=-1
第3章 栈和队列
例五、 表达式求值 例五、
限于二元运算符的表达式定义:
操作数) 运算符 运算符) 操作数 操作数) 表达式 ::= (操作数 + (运算符 + (操作数 操作数 操作数 ::= 简单变量 | 表达式 简单变量 :: = 标识符 | 无符号整数
表达式的三种标识方法： 表达式的三种标识方法： 设 Exp = S1 + OP + S2 则称 OP + S1 + S2 S1 + OP + S2 S1 + S2 + OP 为前缀表示法 前缀表示法 为中缀表示法 中缀表示法 为后缀表示法 后缀表示法
例如：（1348)10 = (2504)8 ，其 例如： 运算过程如下：
计 算 顺 序
N N div 8 N mod 8 1348 168 4 168 21 0 21 2 5 2 0 2
输 出 顺 序
void conversion () { InitStack(S); scanf ("%d",&N); while (N) { Push(S, N % 8); N = N/8; } while (!StackEmpty(S)) { Pop(S,e); printf ( "%d", e ); } } // conversion
栈和队列是两种常用的数据类型
3.1 栈的类型定义 3.2 栈的应用举例 3.3 栈类型的实现 3.4 队列的类型定义 3.5 队列类型的实现
3.1 栈的类型定义
ADT Stack { 数据对象： 数据对象 D＝{ ai | ai ∈ElemSet, i=1,2,...,n, n≥0 } 数据关系： 数据关系 R1＝{ <ai-1, ai >| ai-1, ai∈D, i=2,...,n } 约定an 端为栈顶，a1 端为栈底。 基本操作： 基本操作： } ADT Stack
第三章栈和队列
–
*
/
（
=
）
#
=
2019/9/4
26
例如: #4+ 2 3 10 / 5 #
+
+
2
#
4
OPTR OPND
2019/9/4
27
算符间的优先级关系
1 2 +
–
*
/ （） #
+
}
例2 Hanoi 塔问题
a
2019/9/4
b
c
40
例2 Hanoi 塔问题
a
2019/9/4
b
c
41
例2 Hanoi 塔问题
a
2019/9/4
b
c
42
例2 Hanoi 塔问题
a
2019/9/4
b
c
43
void hanoi (int n, char x, char y, char z) {
3
2
2019/9/4
栈顶
1
9
Top
2. 栈的压入操作
Push(&S, e) //栈 S 已存在，压入元素 e
{ if (s.top== Maxsize -1)
printf("栈满溢出");
else
{ S.top++;
4
S.ST[top]=e;
}
3
return OK;
2
}
1
2019/9/4
Top
10
/
数据结构课件第3篇章栈和队列
循环队列实现原理
01
循环队列定义
将一维数组看作首尾相接的环形结构，通过两个指针（队头和队尾指针）
在数组中循环移动来实现队列的操作。当队尾指针到达数组末端时，再
回到数组起始位置，形成循环。
02
判空与判满条件
在循环队列中，设置一个标志位来区分队列为空还是已满。当队头指针
等于队尾指针时，认为队列为空；当队尾指针加1等于队头指针时，认
栈在函数调用中应用
函数调用栈
在程序执行过程中，每当发生函数调用时，系统会将当前函数的执行上下文压入一个专门的栈中，称为函数调用 栈。该栈用于保存函数的局部变量、返回地址等信息。当函数执行完毕后，系统会从函数调用栈中弹出相应的执 行上下文，并恢复上一个函数的执行状态。
递归调用实现
递归调用是一种特殊的函数调用方式，它通过在函数调用栈中反复压入和弹出同一函数的执行上下文来实现对问 题的分解和求解。在递归调用过程中，系统会根据递归深度动态地分配和管理函数调用栈的空间资源。
栈和队列的应用
栈和队列在计算机科学中有着广泛的应用，如函数调用栈、表达式求 值、缓冲区管理等。
常见误区澄清说明
误区一
栈和队列的混淆。虽然栈和队列都是线性数据结构，但它们的操作方式和应用场景是不同的。栈是后进先出，而队列 是先进先出。
误区二
认为栈和队列只能通过数组实现。实际上，栈和队列可以通过多种数据结构实现，如链表、循环数组等。具体实现方 式取决于应用场景和需求。
后缀表达式求值
利用栈可以方便地实现后缀表达式的求值。具体步骤 为：从左到右扫描表达式，遇到数字则入栈，遇到运 算符则从栈中弹出所需的操作数进行计算，并将结果 入栈，最终栈中剩下的元素即为表达式的结果。
中缀表达式转换为后缀表达式
第3章 栈和队列
显然，为循环队列所分配的空间可以被充分利 用，除非向量空间真的被队列元素全部占用， 否则不会上溢。因此，真正实用的顺序队列是循环队列。 例：设有循环队列QU[0，5]，其初始状态是 front=rear=0，各种操作后队列的头、尾指针的状态变 化情况如下图3-7所示。
rear front front 1 2 4 3 rear
队尾(rear) ：允许进行插入的一端称为队尾。
队列中没有元素时称为空队列。在空队列中依次加入元 素a1, a2, …, an之后，a1是队首元素，an是队尾元素。显然 退出队列的次序也只能是a1, a2, …, an ，即队列的修改是 依先进先出的原则进行的，如图3-5所示。
出队
a1 , a2 , … , an
◆ 入队：将新元素插入rear所指的位置，然后rear加1。
在非空队列里，队首指针始终指向队头元素，而队尾指 针始终指向队尾元素的下一位置。 顺序队列中存在“假溢出”现象。因为在入队和出队操 作中，头、尾指针只增加不减小，致使被删除元素的空间 永远无法重新利用。因此，尽管队列中实际元素个数可能 远远小于数组大小，但可能由于尾指针已超出向量空间的 上界而不能做入队操作。该现象称为假溢出。
结点进栈：首先将数据元素保存到栈顶(top所指的当前位置)，然后执
行top加1，使top指向栈顶的下一个存储位置;
结点出栈：首先执行top减1，使top指向栈顶元素的存储位置，然后将栈
顶元素取出。
3.1.2.2 栈的静态顺序存储表示
采用静态一维数组来存储栈。
◆ 栈底固定不变的；栈顶则随着进栈和退栈操作而变化，用一个整型变量top(称为 栈顶指针)来指示当前栈顶位置。 ◆ 用top=0表示栈空的初始状态，每次top指向栈顶在数组中的存储位置。 ◆
第3章 限定性线性表——栈和队列
两栈共享技术（双端栈）：
主要利用了栈“栈底位置不变，而栈顶位置动态变
化”的特性。首先为两个栈申请一个共享的一维数 组空间S[M]，将两个栈的栈底分别放在一维数组的 两端，分别是0，M-1。
共享栈的空间示意为：top[0]和top[1]分别为两个 栈顶指示器 。
Stack：0
M-1
top[0]
top[1]
(1)第i号栈的进栈操作 int pushi(LinkStack top[M], int i, StackElementType x) { /*将元素x进入第i号链栈*/
LinkStackNode *temp; temp=(LinkStackNode * )malloc(sizeof(LinkStackNode)); if(temp==NULL) return(FALSE); /* 申请空间失败 */ temp->data=x; temp->next=top[i]->next; top[i]->next=temp; /* 修改当前栈顶指针 */ return(TRUE); }
case 1:if(S->top[1]==M) return(FALSE);
*x=S->Stack[S->top[1]];S->top[1]++;break;
default: return(FALSE);
}
return(TRUE);
返回主目录
}
【思考题】
说明读栈顶与退栈顶的处理异同，并标明将已知 的退栈顶算法改为读栈顶算法时应做哪些改动。
返回主目录
链栈的进栈操作
int Push(LinkStack top, StackElementType x)
第3章栈和队列
第3章栈和队列
3.1.2 栈的表示和算法实现
1.顺序栈 2.链栈
第3章栈和队列
1. 顺序栈 顺序栈是用顺序存储结构实现的栈，即利 用一组地址连续的存储单元依次存放自栈 底到栈顶的数据元素，同时由于栈的操作 的特殊性，还必须附设一个位置指针top（ 栈顶指针）来动态地指示栈顶元素在顺序 栈中的位置。通常以top=-1表示空栈。
第 3 章 栈和队列
3.1 栈 3.2 队列 3.3 栈和队列的应用
第3章栈和队列
3.1 栈
3.1.1 栈的抽象数据类型定义 3.1.2 栈的表示和算法实现
第3章栈和队列
3.1.1 栈的定义
1．栈的定义 栈（stack）是一种只允许在一端进行插入和删除的线 性表，它是一种操作受限的线性表。在表中只允许进
行插入和删除的一端称为栈顶（top），另一端称为 栈 底 (bottom) 。 栈 的 插 入 操 作 通 常 称 为 入 栈 或 进 栈 (push)，而栈的删除操作则称为出栈或退栈(pop)。 当栈中无数据元素时，称为空栈。
栈是按照后进先出 （LIFO）的原则组 织数据的，因此， 栈也被称为“后进 先出”的线性表。
第3章栈和队列
（2）入栈操作
Status Push(SqStack &S, Elemtype e)
【算法3.2 栈的入栈操作】
{ /*将元素e插入到栈S中，作为S的新栈顶*/
if (S->top>= Stack_Size -1) return ERROR;
else { S->top++;
S->elem[S->top]=e;
return OK;}
Push(S,’you’)
3.1.2 栈的表示和算法实现
1.顺序栈 2.链栈
第3章栈和队列
1. 顺序栈 顺序栈是用顺序存储结构实现的栈，即利 用一组地址连续的存储单元依次存放自栈 底到栈顶的数据元素，同时由于栈的操作 的特殊性，还必须附设一个位置指针top（ 栈顶指针）来动态地指示栈顶元素在顺序 栈中的位置。通常以top=-1表示空栈。
第 3 章 栈和队列
3.1 栈 3.2 队列 3.3 栈和队列的应用
第3章栈和队列
3.1 栈
3.1.1 栈的抽象数据类型定义 3.1.2 栈的表示和算法实现
第3章栈和队列
3.1.1 栈的定义
1．栈的定义 栈（stack）是一种只允许在一端进行插入和删除的线 性表，它是一种操作受限的线性表。在表中只允许进
行插入和删除的一端称为栈顶（top），另一端称为 栈 底 (bottom) 。 栈 的 插 入 操 作 通 常 称 为 入 栈 或 进 栈 (push)，而栈的删除操作则称为出栈或退栈(pop)。 当栈中无数据元素时，称为空栈。
栈是按照后进先出 （LIFO）的原则组 织数据的，因此， 栈也被称为“后进 先出”的线性表。
第3章栈和队列
（2）入栈操作
Status Push(SqStack &S, Elemtype e)
【算法3.2 栈的入栈操作】
{ /*将元素e插入到栈S中，作为S的新栈顶*/
if (S->top>= Stack_Size -1) return ERROR;
else { S->top++;
S->elem[S->top]=e;
return OK;}
Push(S,’you’)
第3章栈和队列
设计思路： 设计思路：用栈暂存低位值
例2：括号匹配的检验 ：括号匹配的检验——P49
设计思路： 设计思路：用栈暂存左括号
例3 ：表达式求值 表达式求值——P52
设计思路： 设计思路：用栈暂存运算符
例4：汉诺仪（Hanoi）塔——P55 ：汉诺仪（ ）
设计思路： 设计思路：用栈实现递归调用
例5：迷宫求解 ：迷宫求解——P50
9
3.1 栈（Stack） ）
3.1.1 栈是什么？ 3.1.2 栈的表示和实现 3.1.3 栈的应用举例
10
3.1.2 栈的表示和实现
• 顺序栈：即栈的存储结构是顺序存储结 构。利用一组地址连续的存储单元依次 存放自栈底到栈顶的数据元素，同时附 设指针top指示核顶元素在顺序栈中的位 置。 • 链栈：即栈的存储结构是链式存储结构。
6
栈的抽象数据类型定义
ADT Stack { 数据对象：D＝{ ai | ai ∈ElemSet, i=1,2,...,n, n≥0 } 数据对象 数据关系：R1＝{ <ai-1, ai >| ai-1, ai∈D, i=2,...,n } 数据关系 约定an 端为栈顶，a1 端为栈底。 基本操作： 基本操作 InitStack(&S) 操作结果：构造一个空栈S。 DestroyStack(&S) 初始条件：栈S已存在。 操作结果：栈S被销毁。
例3 表达式求值
• • 每个运算符的运算次序要由它之后的一个运算符来 若当前运算符的优先数小，则暂不进行; 定，若当前运算符的优先数小，则暂不进行 否则立 即进行。 即进行。 运算符优先级别： 表达式结束标志)详 运算符优先级别：+ -<* /<( < #(表达式结束标志 详 表达式结束标志 见Page53表3.1。 表 。
例2：括号匹配的检验 ：括号匹配的检验——P49
设计思路： 设计思路：用栈暂存左括号
例3 ：表达式求值 表达式求值——P52
设计思路： 设计思路：用栈暂存运算符
例4：汉诺仪（Hanoi）塔——P55 ：汉诺仪（ ）
设计思路： 设计思路：用栈实现递归调用
例5：迷宫求解 ：迷宫求解——P50
9
3.1 栈（Stack） ）
3.1.1 栈是什么？ 3.1.2 栈的表示和实现 3.1.3 栈的应用举例
10
3.1.2 栈的表示和实现
• 顺序栈：即栈的存储结构是顺序存储结 构。利用一组地址连续的存储单元依次 存放自栈底到栈顶的数据元素，同时附 设指针top指示核顶元素在顺序栈中的位 置。 • 链栈：即栈的存储结构是链式存储结构。
6
栈的抽象数据类型定义
ADT Stack { 数据对象：D＝{ ai | ai ∈ElemSet, i=1,2,...,n, n≥0 } 数据对象 数据关系：R1＝{ <ai-1, ai >| ai-1, ai∈D, i=2,...,n } 数据关系 约定an 端为栈顶，a1 端为栈底。 基本操作： 基本操作 InitStack(&S) 操作结果：构造一个空栈S。 DestroyStack(&S) 初始条件：栈S已存在。 操作结果：栈S被销毁。
例3 表达式求值
• • 每个运算符的运算次序要由它之后的一个运算符来 若当前运算符的优先数小，则暂不进行; 定，若当前运算符的优先数小，则暂不进行 否则立 即进行。 即进行。 运算符优先级别： 表达式结束标志)详 运算符优先级别：+ -<* /<( < #(表达式结束标志 详 表达式结束标志 见Page53表3.1。 表 。
第3章 栈和队列
本章的基本内容是：两种特殊的线性表——栈和队列Ø从数据结构角度看，栈和队列是操作受限的线性表，它们的逻辑结构相同。
Ø从抽象数据类型角度看，栈和队列是两种重要的抽象数据类型。
5 4 3 2 1初态： front ＝rear ＝0；入队： 判满；base[rear]=e ； rear ＝( rear+1)%MaxQsize; 出队： 判空；e=base[front]; front=(front+1)%MaxQsize;队空： front==rear;队满： (rear+1)%MaxQsize==front;循环队列的定义＃define MAXQSIZE 100 //队列的最大长度typedef struct {QElemType *base;int front; //头指针 int rear ; //尾指针 }SqQueue;Status DeQueue(LinkQueue &Q, QElemType &e) {if(Q.front==Q.rear) return ERROR; p=Q.ront->next;Q.front->next=p->next; if(Q.rear==p)Q.rear=Q.front; e=p->data; free(p);return OK; }伪代码：①判断是否为空表；②让p 指向被删结点③把p 从链上摘下来；④特殊情况判断；⑤取元素；⑥释放p 。
当前位置=出口；从当前位置出发{ 寻找下一个“可通的位置”；若找到{把当前位置纳入路径，继续前进}否则{ 后退}}重复上述操作，直到当前位置为出口①当前位置now=入口；作标记；②while(now!=出口）{寻找下一个可通的位置new; if(找到）{ 把now压入栈中；now=new;作标记；}else{ if(栈空） break;else now=出栈；}}伪代码：基本思想：特殊线性表栈队列逻辑结构存储结构逻辑结构存储结构。
第3章数据结构栈和队列
第3章数据结构栈和队列数据结构是计算机科学中重要的基础知识之一，它是用于组织和管理数据的方法。
栈和队列是其中两种常见的数据结构，它们分别以后进先出（Last In First Out，LIFO）和先进先出（First In First Out，FIFO）的方式操作数据。
本文将详细介绍栈和队列的概念、特点以及应用。
一、栈栈是一种限制仅在表尾进行插入和删除操作的线性表。
插入和删除操作称为入栈和出栈，即数据项的入栈相当于把数据项放入栈顶，而数据项的出栈相当于从栈顶移除数据项。
栈具有后进先出的特点，即后入栈的数据项先出栈，而最先入栈的数据项最后出栈。
类比现实生活中的例子就是一叠盘子，我们只能从最上面取盘子或放盘子。
栈的实现方式有两种：基于数组和基于链表。
基于数组的栈实现相对简单，通过一个数组和一个指向栈顶的指针来完成栈的操作。
基于链表的栈实现则需要定义一个节点结构，每个节点包含一个数据域和一个指向下一个节点的指针，通过头指针来操作栈。
栈的应用非常广泛，比如浏览器中的返回功能就是通过栈来实现的。
当我们点击浏览器的返回按钮时，当前页面会入栈，点击前进按钮时，当前页面会出栈。
在编程中，栈也被广泛应用，比如函数调用栈用于存储函数调用的上下文信息。
二、队列队列是一种限制仅在表头删除和在表尾插入的线性表。
表头删除操作称为出队列，表尾插入操作称为入队列。
和栈不同，队列采用先进先出的原则，即最先入队列的元素最先出队列。
队列的实现方式也有两种：基于数组和基于链表。
基于数组的队列实现和栈类似，通过一个数组和两个指针（一个指向队头，一个指向队尾）来完成队列的操作。
基于链表的队列实现则需要定义一个节点结构，每个节点包含一个数据域和一个指向下一个节点的指针，通过头指针和尾指针来操作队列。
队列同样具有广泛的应用，比如操作系统中的进程调度就是通过队列来实现的。
CPU会按照进程到达的顺序，依次从队列中取出进程进行执行。
在编程中，队列也常用于解决一些需要按顺序处理数据的问题。
数据结构第三章栈和队列
性能比较与选择依据
性能比较
栈和队列的时间复杂度均为O(1)，空间复杂度均为O(n)。在实际应用中，栈通常用于 需要后进先出（LIFO）的场景，而队列则用于需要先进先出（FIFO）的场景。
选择依据
在选择使用栈还是队列时，应根据具体需求和应用场景进行判断。如果需要后进先出的 特性，应选择栈；如果需要先进先出的特性，则应选择队列。同时，还需要考虑数据结
栈中的元素只能在栈顶进行插入和删 除操作。
栈具有记忆功能，能保存数据元素进 入栈的先后顺序。
栈的基本操作
01
入栈（Push）：在栈顶 插入一个元素。
02
出栈（Pop）：删除栈 顶元素并返回其值。
03
查看栈顶元素（Top） ：返回栈顶元素的值， 但不删除该元素。
04
判断栈是否为空（ IsEmpty）：检查栈中 是否还有元素。
回溯到上一个状态。
广度优先搜索中的队列应用
搜索队列
广度优先搜索使用队列来保存待 搜索的节点，按照先进先出的原
则进行搜索。
状态转移
在广度优先搜索中，队列用于保存 状态转移的信息，以便在搜索过程 中根据状态转移规则进行状态的扩 展和搜索。
最短路径问题
广度优先搜索可用于解决最短路径 问题，通过队列保存待访问的节点 ，并按照距离起始节点的远近进行 排序和访问。
其他算法中的栈和队列应用
深度优先搜索
在深度优先搜索中，栈用于保存当前路径的状态信息，以便在需要时 回溯到上一个状态。
括号匹配问题
栈可用于解决括号匹配问题，遇到左括号时将其压入栈中，遇到右括 号时从栈中弹出左括号并判断是否匹配。
表达式求值
栈可用于表达式求值中，保存操作数和运算符，并按照运算优先级进 行求值。
教学课件第三章栈和队列
A( ){ …
B( ) { …
C( ) { …
A( ) ;
C( );
B( );
… }
… }
… }
A 直接调用自己
B间接调用自己
递归算法的编写 1）将问题用递归的方式描述（定义） 2）根据问题的递归描述（定义）编写递归算法
问题的递归描述（定义） 递归定义包括两项 基本项（终止项）：描述递归终止时问题的求解； 递归项：将问题分解为与原问题性质相同，但规模较小 的问题；
}
top
f(1) 1
f(1)=1
f(2) 2*f(1) f(2)=2*f(1)
f(3) 3*f(2) f(3)=3*f(2)
f(4) 4*f(3) f(4)=4*f(3)
f(5) 5*f(4) f(5)=5*f(4)
例2 递归的执行情况分析
void print(int w) { int i;
if ( w!=0) { print(w-1);
（LIFO）。
a2
栈的特点
a1
后进先出(LIFO)
栈的示意图
栈在函数嵌套调用中的应用：
主函数 a 函数
b 函数
c 函数
r
s
t
函数的嵌套调用与返回
t
s
s
s
r
r
r
r
r
(a) 调用a函数, r进栈 (c) 调用c函数,t进栈 (e) 返回a函数,s退栈 (b) 调用b函数,s进栈 (d) 返回b函数,t退栈 (f) 返回主程序,r退栈
1
m
栈1底
栈1顶
栈2顶
栈2底
常采用将两个栈底设在可用空间的两端。
仅当两个栈顶相遇时，才产生上溢，即所有可用空间已用完。对 每个栈可用的最大空间就可能大于整个可用空间的一半m/2。
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
第三章栈与队列
一、判断题：
( ) 1．栈和队列都是线性表，只是在插入和删除时受到了一些限制。
( ) 2．若输入序列为1，2，3，4，5，6，则通过一个栈可以输出序列1，5，4，6，2，3。
( )3．循环队列也存在空间溢出问题。
( )4．两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。
( )5．即使对不含相同元素的同一输入序列进行两组不同的合法的入栈和出栈组合操作，所得的输出序列也一定相同。
( )6．队列是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。
( )7．栈与队列是一种特殊操作的线性表。
( )8．若输入序列为1,2,3,4,5,6,则通过一个栈可输出序列3,2,5,6,4,1。
( )9．栈和队列都是限制存取点的线性结构。
( )10．队列和栈都是运算受限的线性表，只允许在表的两端进行运算。
( )11．队列逻辑上是一个下端和上端既能增加又能减少的线性表。
( )12．循环队列通常用指针来实现队列的头尾相接。
二、填空题：
1．栈是_________的线性表，其运算遵循_________的原则。
2．_________是限定仅在表尾进行插入或删除操作的线性表。
3．一个栈的输入序列是：1，2，3则不可能的栈输出序列是___________。
4．当两个栈共享一存储区时，栈利用一维数组stack(1,n)表示，两栈顶指针为top[1]与top[2]，则当栈1空时，top[1]为_______，栈2空时，top[2]为_______，栈满时为_______。
5．两个栈共享空间时栈满的条件_____________。
6．在作进栈运算时应先判别栈是否_____；在作退栈运算时应先判别栈是否__________；当栈中元素为n个，作进栈运算时发生上溢，则说明该栈的最大容量为__________。
为了增加内存空间的利用率和减少溢出的可能性，由两个栈共享一片连续的空间时，应将两栈的____________分别设在内存空间的两端，这样只有当_________________________时才产生溢出。
7．多个栈共存时，最好用____________作为存储结构。
8．用S表示入栈操作，X表示出栈操作，若元素入栈的顺序为1234，为了得到1342出栈顺序，相应的S和X的操作串为_________________。
9．顺序栈用data[1．．n]存储数据，栈顶指针是top,则值为x的元素入栈的操作是_________________。
10．区分循环队列的满与空，只有两种方法，它们是___________和___________。
11．循环队列的引入，目的是为了克服___________________。
12．用下标0开始的N元数组实现循环队列时，为实现下标变量M加1后在数组有效下标范围内循环，可采用的表达式是：M：=_______。
13．_____________又称作先进先出表。
14．队列的特点是_______________________。
15．队列是限制插入只能在表的一端，而删除在表的另一端进行的线性表，其特点是_______________________。
16．设循环队列用数组A[1．．M]表示，队首、队尾指针分别是FRONT和TAIL，判定队满的条件为___________________。
三、选择题：
1．对于栈操作数据的原则是（）。
A．先进先出 B．后进先出 C．后进后出 D．不分顺序
2．在作进栈运算时,应先判别栈是否( ① ),在作退栈运算时应先判别栈是否( ②)。
当栈中元素为n个,作进栈运算时发生上溢,则说明该栈的最大容量为( ③ )。
为了增加内存空间的利用率和减少溢出的可能性,由两个栈共享一片连续的内存空间时,应将两栈的 ( ④ )分别设在这片内存空间的两端,这样,当( ⑤ )时，才产生上溢。
①, ②: A．空 B．满 C．上溢 D．下溢
③: A．n-1 B．n C．n+1 D．n/2
④: A．长度 B．深度 C．栈顶 D．栈底
⑤: A．两个栈的栈顶同时到达栈空间的中心点
B．其中一个栈的栈顶到达栈空间的中心点
C．两个栈的栈顶在栈空间的某一位置相遇
D．两个栈均不空,且一个栈的栈顶到达另一个栈的栈底
3．一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i （1<=i<=n）个元素是（）。
A．不确定 B．n-i+1 C．i D．n-i
4．若一个栈的输入序列为1,2,3,…,n，输出序列的第一个元素是i，则第j个
输出元素是（）。
A．i-j-1 B．i-j C．j-i+1 D．不确定
5．若已知一个栈的入栈序列是1,2,3,…,n，其输出序列为p1,p2,p3，…，pN,若pN是n，则pi是( )。
A．i B．n-i C．n-i+1 D．不确定
6．有六个元素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 7．设栈的输入序列是1，2，3，4，则（）不可能是其出栈序列。
A．1，2，4，3， B．2，1，3，4， C．1，4，3，2， D．4，3，1，2 8．一个栈的输入序列为 1 2 3 4 5，则下列序列中不可能是栈的输出序列的是（）。
A．2 3 4 1 5 B．5 4 1 3 C．2 3 1 4 5 D．1 5 4 3 2 9．设一个栈的输入序列是 1，2，3，4，5，则下列序列中，是栈的合法输出序列的是（）。
A．5 1 2 3 4 B．4 5 1 3 2 C．4 3 1 2 5 D．3 2 1 5 4 10．某堆栈的输入序列为a, b，c ，d,下面的四个序列中，不可能是它的输出序列的是（）。
A．a，c，b，d B．b, c，d，a C．c, d，b, a D．d, c，a，b 11．设abcdef以所给的次序进栈，若在进栈操作时，允许退栈操作,则下面得不到的序列为（）。
A．fedcba B． bcafed C． dcefba D． cabdef
12．设有三个元素X，Y，Z顺序进栈（进的过程中允许出栈），下列得不到的出栈排列是( )。
A．XYZ B．YZX C．ZXY D．ZYX
13．输入序列为ABC，可以变为CBA时，经过的栈操作为（）。
A．push,pop,push,pop,push,pop B．push,push,push,pop,pop,pop C．push,push,pop,pop,push,pop D．push,pop,push,push,pop,pop
14．若一个栈以向量V[1．．n]存储，初始栈顶指针top为n+1，则下面x进栈的正确操作是( )。
A．top:=top+1; V [top]:=x B．V [top]:=x; top:=top+1
C．top:=top-1; V [top]:=x D．V [top]:=x; top:=top-1
15．若栈采用顺序存储方式存储，现两栈共享空间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]
参考答案
一、判断题：
1．√ 2．× 3．√ 4．√ 5．× 6．×
7．√ 8．√ 9．√ 10．× 11．√ 12．×
二、填空题：
1．操作受限（或限定仅在表尾进行插入和删除操作）后进先出
2．栈
3．3 1 2
4．0 n+1 top[1]+1=top[2]
5．两栈顶指针值相减的绝对值为1（或两栈顶指针相邻）
6．(1)满 (2)空 (3)n (4)栈底 (5)两栈顶指针相邻（即值之差的绝对值为1）
7．链式存储结构
8．S×SS×S××
9．data[++top]=x
10.牺牲一个存储单元设标记
11．假溢出时大量移动数据元素
12．(M+1)% N
13．队列
14．先进先出
15．先进先出
16．（TAIL+1）% M=FRONT
三、选择题：
1． B 2．1 B 2．2 A 2．3 B 2．4 D 2．5．C
3． B 4． D 5． D 6． C 7． D 8． B
9． D 10． D 11． D 12． C 13． B 14． C 15． B。