计算机专业 80● 网上教学改革 数据结构（本） 授课教师：范颖
计算机专业 网上教学改革 数 据 结 构（本） 授课教师：范颖
二、第三章栈和队列解析 本章课程主要介绍栈和队列的定义和特点，栈 和队列在顺序存储和链式存储结构下的有关运 算。理解循环队列的概念和相应操作的实现。 理解栈和队列的简单应用和栈在递归算法设计 技术中的作用。 www.open.ha.cn
www.open.ha.cn 二、第三章栈和队列解析 ▪ 本章课程主要介绍栈和队列的定义和特点，栈 和队列在顺序存储和链式存储结构下的有关运 算。理解循环队列的概念和相应操作的实现。 理解栈和队列的简单应用和栈在递归算法设计 技术中的作用
二、第三章栈和队列解析 1、什么是栈？什么是队列？ 栈是只允许在表的一端进行插入和删除的线性表。 ■ 栈的特点是先进后出。 ·队列是只允许在一端插入，在另一端删除的线性 表。队列的特点是先进先出。 出栈 进栈 栈顶 a 出队 入队 al a2 栈底 a 队头 队尾 a www.open.ha.cn )
www.open.ha.cn 二、第三章栈和队列解析 ▪ 1、什么是栈？什么是队列？ ▪ 栈是只允许在表的一端进行插入和删除的线性表。 栈的特点是先进后出。 ▪ 队列是只允许在一端插入，在另一端删除的线性 表。队列的特点是先进先出。 a1 a2 a3 …… an 栈顶 栈底 出栈 进栈 a1 a2 …… an 出队 入队 队头 队尾
二、第三章栈和队列解析 ■ 2、顺序栈的存储结构和相关操作有哪些？ ·顺序栈类似于顺序表，要分配一块连续的存储空 间存放栈中的元素，通常用一个足够长度的一维 数组来实现。需要一个栈顶指针top。 struct SeqStack an ElemType data[MaxSize]; 3 … int top; s栈 a3 ; 1 a2 struct SeqStack *s; top 0 a www.open.ha.cn t
www.open.ha.cn 二、第三章栈和队列解析 ▪ 2、顺序栈的存储结构和相关操作有哪些？ ▪ 顺序栈类似于顺序表，要分配一块连续的存储空 间存放栈中的元素，通常用一个足够长度的一维 数组来实现。需要一个栈顶指针top 。 struct SeqStack { ElemType data[MaxSize]; int top; }; struct SeqStack *s; a1 a2 a3 …… an top 4 3 2 1 0 s栈
二、 第三章栈和队列解析 ·2、顺序栈的存储结构和相关操作有哪些？ ·顺序栈的基本操作 （1)判断栈空：s>top==-1 (2)判断栈满：s->top=MaxSize-1 (3)进栈：①s>top++; ②s->data[s->top]=x; 2 top 1 X top o a1 初始 进栈 www.open.ha.cn
www.open.ha.cn 二、第三章栈和队列解析 ▪ 2、顺序栈的存储结构和相关操作有哪些？ ▪ 顺序栈的基本操作 （1）判断栈空：s->top==-1 （2）判断栈满：s-> top==MaxSize-1 （3）进栈： ① s->top++; ② s->data[s->top]=x; a1 top 2 1 0 a1 x top 2 1 0 初始 进栈 ① ①
二、第三章栈和队列解析 2、顺序栈的存储结构和相关操作有哪些？ ·顺序栈的基本操作 (4)出栈：①s->top- top 2 a3 1 top a2 1 a2 a 0 0 a 初始 出栈 (5)取栈顶元素：topelem=s->data[s->top]; www.open.ha.cn ⑦
www.open.ha.cn 二、第三章栈和队列解析 ▪ 2、顺序栈的存储结构和相关操作有哪些？ ▪ 顺序栈的基本操作 （4）出栈： ① s->top--; （5）取栈顶元素：topelem=s->data[s->top]; a1 a2 a3 top 2 1 0 a1 a2 top 2 1 0 初始 出栈 ①
二、第三章栈和队列解析 ■3、 链栈的存储结构和相关操作有哪些？ ◆ 链栈的结点结构与单链表的结点结构相同。由于 栈的插入和删除操作仅限制在表头结点进行，所 以用不带头结点的单链表实现栈的链式存储结构 以使链栈的操作运算更加方便。 struct node top an 栈顶 ElemType data; an-1 struct node *next; ; struct node *top; 栈底 www.open.ha.cn 0
www.open.ha.cn 二、第三章栈和队列解析 ▪ 3、链栈的存储结构和相关操作有哪些？ ▪ 链栈的结点结构与单链表的结点结构相同。由于 栈的插入和删除操作仅限制在表头结点进行，所 以用不带头结点的单链表实现栈的链式存储结构 以使链栈的操作运算更加方便。 struct node { ElemType data; struct node *next; }; struct node *top; an an-1 a1 ^ …… top 栈顶 栈底
二、第三章栈和队列解析 。3、链栈的存储结构和相关操作有哪些？ 链栈的基本操作 (1)判断栈空：top=NULL (2)进栈： p ①p->data=x; ◇ X ②p->next=top; top a; top ③top=p; a a 初始 进栈 www.open.ha.cn
www.open.ha.cn 二、第三章栈和队列解析 ▪ 3、链栈的存储结构和相关操作有哪些？ ▪ 链栈的基本操作 （1）判断栈空：top==NULL （2）进栈： ① p->data =x; ② p->next=top; ③ top=p; a3 a2 a1 ^ top 初始 X p a3 a2 a1 ^ 进栈 ① ① ① top
二、第三章栈和队列解析 ·3、链栈的存储结构和相关操作有哪些？ 链栈的基本操作 ■ (3)出栈： ◇ ①p=top; top a3 top a3 ②x=p->data; a2 ☐x=p->data ☐free(p); ③top=p->next; a a ④free(p); 初始 出栈 (4)取栈顶元素： topelem=(top )->data; www.open.ha.cn e
www.open.ha.cn 二、第三章栈和队列解析 ▪ 3、链栈的存储结构和相关操作有哪些？ ▪ 链栈的基本操作 （3）出栈： ① p=top; ② x=p->data; ③ top=p->next; ④ free（p）; （4）取栈顶元素： topelem=（top）->data; ① ① a3 a2 a1 ^ top 初始 a3 p a2 a1 ^ 出栈 top ① x=p->data; ① free（p）;
二、第三章栈和队列解析 ◆ 4、栈的应用 （1)算术表达式求值 ·根据运算符在表达式中的位置不同，表达式有 三种表示形式： (1)中缀表示： 例如：A+B (2)前缀表示： 例如：+AB (3)后缀表示： 例如：AB+ www.open.ha.cn
www.open.ha.cn 二、第三章栈和队列解析 ▪ 4、栈的应用 （1）算术表达式求值 ▪ 根据运算符在表达式中的位置不同，表达式有 三种表示形式： （1）中缀表示： 例如： A+B （2）前缀表示： 例如： +AB （3）后缀表示： 例如： AB+