第b章-栈和队列-课件(ppt·精·选)

04 栈和队列的比较与选择
栈和队列的区别
01 02
操作方向
栈是后进先出（LIFO）的数据结构，只允许在固定的一端进行插入和删 除操作；而队列是先进先出（FIFO）的数据结构，允许在两端进行插入 和删除操作。
限制性
栈的操作是有记忆性的，只能按照后进先出的顺序进行操作，而队列没 有这种限制。
03
应用场景
链表实现栈
链表实现栈的原理
使用链表来存储栈中的元 素，通过指针来访问和操 作栈顶元素。
链表实现栈的优点
插入和删除操作效率高， 不需要移动大量元素。
链表实现栈的缺点
空间利用率较低，因为链 表中的节点通常会有一些 额外的空间开销。
栈的常见操作
push：将一个元素压入栈顶。
pop：删除栈顶元素并返回 其值。
数据流处理：在数据流处理中，使用 队列来缓冲数据，以便按顺序处理数 据。
02 栈的实现方式
数组实现栈
01
02
03
数组实现栈的原理
使用数组来存储栈中的元 素，通过索引来访问和操 作栈顶元素。
数组实现栈的优点
空间利用率高，因为数组 的大小是固定的，不会造 成空间的浪费。
数组实现栈的缺点
在某些情况下，插入和删 除操作可能需要移动大量 元素，效率较低。
02
01
03
peek/top：返回栈顶元素的 值，但不删除它。
isEmpty：判断栈是否为空。
04
05
size/length：返回栈中元素 的数量。
03 队列的实现方式
数组实现队列
总结词
数组实现队列时，队列的头部和尾部操作都能够在常数时间内完成，但队列的 长度固定，无法动态扩展。

在操作系统中，任务按照 优先级顺序进入队列，系 统按照队列的先进先出原 则进行任务调度。
网络通信
在网络通信中，数据包按 照到达顺序进入队列，等 待处理。
打印任务管理
打印任务按照到达顺序进 入队列，等待打印机的空 闲时间进行处理。
05
栈与队列的比较
结构比较
栈和队列是两种不同的数据结构，它们在结构上有明显的区 别。
课程目标
掌握栈和队列的基本 概念、原理和应用场 景；
能够运用栈和队列解 决实际问题和算法设 计。
理解栈和队列在解决 实际问题中的作用和 优势；
02
数据结构概述
数据结构定义
数据结构定义
数据结构是数据元素之间相互关系和数据元素属性的 抽象表示。
数据结构组成
数据元素、数据元素之间的关系和数据元素的属性。
表达式求值：例如，括号内的运算优先级高于括号外的运算，可以使用栈来保存括 号和运算符，以便正确地计算表达式的值。
深度优先搜索（DFS）：在图的遍历中，可以使用栈来保存待访问的节点，实现深 度优先搜索。
04
队列（Queue）
队列的定义
01
队列是一种先进先出（FIFO）的数据结构，用于存储元素的集 合。
07
总结与展望
本章总结
栈和队列是两种常见的数据结构，具有特定的操作规则和特性。
通过学习栈和队列，我们掌握了先进先出（FIFO）和后进先出（LIFO）的 原理，以及如何在程序中实现这些数据结构。
本章还介绍了栈和队列在实际问题中的应用，如括号匹配、表达式求值等 。
数据结构的发展趋势与未来展望
01
随着计算机技术的不断发展，数据结构也在不断演进
02
队列中的元素遵循先入队后出队的规则，即最早进入队列的元

初始条件：栈 S 已存在且非空。 操作结果：删除 S 的栈顶元素，并用 e 返回其值。
.
15
栈的抽象数据类型定义
StackTraverse(S, visit( )) 初始条件：栈 S 已存在且非空，visit( )为元素的访问
函数。 操作结果：从栈底到栈顶依次对S的每个元素调用函数
visit( )，一旦visit( )失败，则操作失败。 } ADT Stack
.
29
3.1.2.2 栈的静态顺序存储表示
4 弹栈(元素出栈)
Status pop( SqStack S, ElemType *e ) /*弹出栈顶元素*/ { if ( S.top==0 ) return ERROR ; /* 栈空，返回错误标志 */ *e=S.stack_array[S.top] ; S.top-- ; return OK ; }
.
11
3.1.1 栈的基本概念
2 栈的抽象数据类型定义
ADT Stack{ 数据对象：D ={ ai|ai∈ElemSet, i=1,2,…,n，n≥0 } 数据关系：R ={<ai-1, ai>|ai-1，ai∈D, i=2,3,…,n } 基本操作：初始化、进栈、出栈、取栈顶元素等
} ADT Stack
进栈（push） 出栈(pop)
top
an
⋯⋯
ai ⋯⋯
a2
bottom
a1
图3-1 顺序栈示意图
.
6
栈的示意图
入栈
• 特点
• 先进后出（FILO） 出栈 • 后进先出（LIFO）
栈顶 栈顶 栈顶
a3 a2
插入：入栈、进栈、压栈 删除：出栈、弹栈

二、栈的应用举例
★若读出的运算符的优先级不大于运算符栈栈顶 运算符的优先级，则从操作数栈连续推出两个操 作数，并从运算符栈推出一个运算符，然后作相 应的运算，并将运算结果压入操作数栈。在这种 情况下，当前读出的运算符下次重新考虑（即不 再读下一个符号）。
分析：表达式2+3*4-9/3;的计算过程
二、栈的应用举例
出栈时，在栈非空时，先将栈顶元素赋给指定的变 量，再将栈顶指针退一。
void pop(Stack &S, int &e) {
if(S.top==0) { cout<<"空栈";return; } e=S.data[S.top-1]; --S.top; return; }
2．栈的顺序存储及其实现
(4) 读栈顶元素：将栈顶元素赋给一个指定的变量
2 递归的实现
从递归的基本思想可以看出，计算机 执行递归过程时，需要记忆各步的状 态，以便问题的返回。这可以用栈来 实现。
a[4]={2,3,7,5} max(a,m,n) { if(m!=n)
{x=max(a,m,(m+n)/2); 2 7 y=max(a,(m+n)/2+1,n); 3 5
return x>y?x:y;} x=3 7 y=7
Struct LQueue{ node *front; node *rear;
} LQueue *LQ;
四、队列
链队的说明如下
★队头指针为LQfront,队尾指针为LQrear, 对头元素的引用为LQfrontdata,对尾元素的引用 为LQreardata. ★初始化时，设置LQfront=LQrear=NULL.
Q(1:6)

对比分析
总结词
各有优缺点
详细描述
数组实现和链表实现各有优缺点。数组实现具有简单直观的优点，但在实际应用中可能会受到数组大 小限制的影响。链表实现更加灵活，但需要注意指针操作和内存管ห้องสมุดไป่ตู้问题。具体选择哪种实现方式需 要根据实际需求和应用场景来决定。
05
栈和队列的常见问题与解 决方案
栈溢出问题
栈溢出问题
当栈的大小不足以容纳新元素时 ，会发生栈溢出。这通常是由于 递归深度过深或栈空间分配不足
导致的。
解决方案
为栈分配足够的空间，避免过深的 递归，或者使用循环代替递归。
优化建议
使用动态内存分配函数（如malloc 和free）来动态调整栈的大小，以 适应不同的情况。
队列空指针问题
队列空指针问题
优化建议
栈的特性
先进后出（FILO）
栈中的元素必须遵循后进先出的原则，即最后一个进入栈的元素 将是第一个出去的元素。
插入和删除操作在栈顶进行
栈只允许在固定的一端（称为栈顶）进行插入和删除操作。
动态性
栈的大小可以根据需要进行动态调整。
栈的应用场景
后进先出（LIFO）的场景
01
如括号匹配、函数调用堆栈等，需要最后进入的元素最先出来
队列主要有入队、出队 、查看队首元素等操作
。
队列的应用场景
01
02
03
任务调度
在多任务系统中，可以使 用队列来实现任务的调度 和管理。
缓冲处理
在输入输出系统中，可以 使用队列来缓存数据，实 现数据的缓冲处理。
事件处理
在事件驱动的系统中，可 以使用队列来管理事件， 实现事件的顺序处理和并 发处理。

获取队头元素（Front）： 返回队列头部的元素值， 但不删除该元素。
获取队尾元素（Rear）： 返回队列尾部的元素值， 但不删除该元素。
04 栈和队列的应用
栈在括号匹配中的应用
总结词
栈在括号匹配中起到关键作用，通过后进先 出的原则，可以判断括号是否匹配。
详细描述
栈在括号匹配中起到关键作用，它遵循后进 先出的原则，即最后进入的元素最先出来。 通过使用栈，我们可以有效地判断一个括号 的序列是否匹配。当遇到左括号时，将其压 入栈中；当遇到右括号时，从栈顶取出一个 元素进行匹配。如果栈为空或者取出的元素 与右括号不匹配，则说明括号序列不匹配。
返回栈顶的元素值，但不删除该元素。
判断栈是否为空（isEmpty）
判断栈是否为空，如果是空则返回true，否 则返回false。
03 队列的概念和操作
队列的定义
01
队列是一种特殊的线性表，它只允 许在表的前端（front）进行删除 操作，在表的后端（rear）进行插 入操作。
02
队列具有先进先出（FIFO）的特性， 最早进入队列的元素将最先出队。
作。
课程目标
掌握栈和队列的基本 概念、特性和操作。
能够实现栈和队列的 基本操作，并解决实 际问题。
理解栈和队列在算法 设计中的应用。
02 栈的概念和操作
栈的定义
栈是一种特殊的线性表，只允 许在表的一端进行插入和删除 操作。
栈的插入操作称为压栈，删除 操作称为弹栈。
栈具有后进先出（Last In First Out，LIFO）的特性。
THANKS FOR WATCHING
感谢您的观看
队列的性质
队列是一种线性数据结构，遵循先进 先出原则。

栈与队列的区别
数据存储方式
栈是后进先出（Last In First Out, LIFO）的数据结构，新元素总是被添加到栈顶，移除 元素时也是从栈顶开始。而队列是先进先出（First In First Out, FIFO）的数据结构，新 元素被添加到队列的尾部，移除元素时从队列的头部开始。
操作方式
栈的主要操作有push（添加元素）和pop（移除元素），而队列的主要操作有enqueue （添加元素）和dequeue（移除元素）。
《栈和队列》ppt课件
目录
CONTENTS
• 栈的定义与特性 • 队列的定义与特性 • 栈与队列的区别与联系 • 栈和队列的实现方式 • 栈和队列的算法实现 • 总结与思考
01 栈的定义与特性
CHAPTER
栈的定义
栈是一种特殊的线性 数据结构，遵循后进 先出（LIFO）原则。
栈中的元素按照后进 先出的顺序排列，最 新加入的元素总是位 于栈顶。
02
如何实现一个队列，并 实现其基本操作（ enqueue、dequeue、 front）？
03
栈和队列在应用上有哪 些区别？请举例说明。
04
请设计一个算法，使用 栈实现括号匹配的功能 ，并给出测试用例。
谢谢
THANKS
。
队列的应用场景
任务调度
在任务调度中，可以将任 务按照优先级放入队列中 ，按照先进先出的原则进 行调度。
网络通信
在网络通信中，可以将数 据包放入队列中，按照先 进先出的原则进行发送和 接收。
事件处理
在事件处理中，可以将事 件放入队列中，按照先进 先出的原则进行处理。
03 栈与队列的区别与联系
CHAPTER
应用场景

p=Q.front->next;
e=p->data;
Q.front->next=p->next;
if(Q.rear==p) Q.rear=Q.front;
free(p);
return OK;
}
经营者提供商品或者服务有欺诈行为 的，应 当按照 消费者 的要求 增加赔 偿其受 到的损 失，增 加赔偿 的金额 为消费 者购买 商品的 价款或 接受服 务的费 用
typedef struct
{ Selemtype *base; //在栈构造之前和销毁之后，base的值为NULL
Selemtype *top; //栈顶指针
int
stacksize; //当前已分配的存储空间，以元素为单位
} sqstack;
栈的基本操作：P46
经营者提供商品或者服务有欺诈行为 的，应 当按照 消费者 的要求 增加赔 偿其受 到的损 失，增 加赔偿 的金额 为消费 者购买 商品的 价款或 接受服 务的费 用
x
x
y^ rear
y^ rear
经营者提供商品或者服务有欺诈行为 的，应 当按照 消费者 的要求 增加赔 偿其受 到的损 失，增 加赔偿 的金额 为消费 者购买 商品的 价款或 接受服 务的费 用
❖构造空队列
status InitQueue(LinkQueue &Q) {
Q.front=Q.rear=(QueuePtr)malloc(sizeof(Qnode));
若表达式未输入完，转1
例 计算 4+3*5
后缀表达式：435*+
top 3
top 4
4
top 5 3
7
top top

1.读入字符串
d
top 2.压入栈
a
3.原串字符与出栈字符依次比较
d
若不等，非回文
字符串：“madam I madam”
若直到栈空都相等，则是回文
“上海自来水来自海上” 有没有更简洁的办法呢？
(读入字符串，压入n/2个字符,n为字符个数)
❖多进制输出：
例 把十进制数159转换成八进制数
8 159 余 7
8 19
余3
82
余2
0
(159)10=(237)8
23 7
top 7
电气信息学院 计算机系
top 3 7
top top
2 3 7
第5页
数据结构
❖多进制输出：
例 把十进制数159转换成八进制数
top
8 159
8 19 82
0
余7 余3 余2
23 7
top 7
top 3 7
top 2 3
7
(159)10=(237)8
}
}
System.out.println(binStr);
电气信息学院 计算机系
第6页
数据结
❖多进制输出：
例 把十进制数159转换成八进制数
import java.util.*;
class T
{
public static void main(String[] args)
{
System.out.println(toOctal(159));
}
}
电气信息学院 计算机系
构
第7页
数据结构
❖ 表达式求值( 这是栈应用的典型例子 )
这里，表达式求值的算法是 “算符优先法”。

top
d
c
bHale Waihona Puke af 进栈溢出b a b 进栈
e d c b a e 退栈
教学进度
top d c b a
d 退栈
top c b a
c 退栈
计算机科学与工程系
top b a
b 退栈
top a
top
a 退栈
空栈
教学进度
Status InitStack（ SqStack &S) //构造空栈S {
计算机科学与工程系
教学进度
Quiz
计算机科学与工程系
• 一个栈的入栈序列是（a,b,c,d,e），不 可能得到的输出序列有 ( C ) A．edcba B．decba
• 特点：先进后出（FILO）或后进先出（LIFO）
进栈
栈
顶
an
a2
栈底
a1
... ……...
出栈 栈s=(a1,a2,……,an)
教学进度
计算机科学与工程系
教学进度
栈的类型定义 计算机科学与工程系
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 端为栈底。 基本操作：
Typedef struct {
SElemType *base; //栈元素数组的首地址
SElemType *top; //栈顶指针
int stacksize;
//栈最大容量
} SqStack；
教学进度
计算机科学与工程系