安徽理工大学：《数据结构》课程教学资源（课件讲稿，C语言版）第3章 栈和队列

学习要求 第三章栈和队列 ■ 理解栈和队列的基本概念和各种存储结构； ■掌握栈和队列的各种基本操作 一1- 145

— 1— — 1— 学习要求  理解栈和队列的基本概念和各种存储结构；  掌握栈和队列的各种基本操作 第三章 栈和队列

基本特征 通常称，栈和队列是限定插入和删除只能在表 的“端点”进行的线性表。 线性表 栈 队列 Insert(L,i,x)Insert(S,n+1,x) Insert(Q,n+1,x) 1≤i≤n+1 Delete(L,i,x)Delete(S,n,x) Delete(Q,1,x) 1≤isn CIENC 一2 1945

— 2— — 2— 基本特征 通常称，栈和队列是限定插入和删除只能在表 的“端点”进行的线性表。 线性表 栈 队列 Insert(L, i, x) Insert(S, n+1, x) Insert(Q, n+1, x) 1≤i≤n+1 Delete(L, i, x) Delete(S, n, x) Delete(Q, 1, x) 1≤i≤n

目录页 Contents Page 栈 第三章 栈的应用举例 栈和队列 栈和递归的实现 队列 一3一 1945

— 3— — 3— Contents Page 目录页 栈的应用举例 栈和递归的实现 栈 队列

3.1栈 -4- 145

— 4— 3.1 栈

3.1栈 3.1.1抽象数据类型栈的定义 入栈 出栈 栈(Stack)是限定仅能在表 栈顶 的一端进行插入和删除操作的 线性表。能进行插入、删除的 an-1 一端称为栈顶(Top),另一端称 栈底(Bottom)。当表中没有元 素时称为空栈。 栈底 a2 al (a1,a2,…,an) 栈的示意图 删除！插入 1945

— 5— 3.1 栈 an an-1 … a2 a1 入栈 出栈 栈顶 栈底 栈的示意图 栈(Stack)是限定仅能在表 的一端进行插入和删除操作的 线性表。能进行插入、删除的 一端称为栈顶(Top)，另一端称 栈底(Bottom)。当表中没有元 素时称为空栈。 （a1, a2, ... , an） 删除 插入 3.1.1 抽象数据类型栈的定义

3.1栈 栈的特点 后进先出(LFO) 3.1.1抽象数据类型栈的定义 入栈 出栈 栈顶：对栈进行操作的一端。 栈顶指针：指示栈顶位置的指针。 栈顶 栈的长度：栈中元素的个数。 假设栈S=(a1,a2,a3,an). 3n-1 则a称为栈底元素，an为栈顶元 素。插入的过程称为入栈，删除 82 的过程称为出栈。 栈底 a 栈称为后进先出表 (LIFO)。 栈的示意图，父 -6

— 6— 3.1 栈  栈顶：对栈进行操作的一端。  栈顶指针：指示栈顶位置的指针。  栈的长度：栈中元素的个数。  假设栈S=(a1, a2, a3, …,, an)， 则a1称为栈底元素，an为栈顶元 素。插入的过程称为入栈，删除 的过程称为出栈。  栈称为后进先出表（LIFO）。 an an-1 … a2 a1 入栈 出栈 栈顶 栈底 栈的示意图 栈的特点 后进先出(LIFO) 3.1.1 抽象数据类型栈的定义

3.1栈 栈的特点 后进先出 3.1.1抽象数据类型栈的定义 (LIFO) 栈的示意图 出栈 进栈 第一个进栈的元素在栈底； 栈顶 最后一个进栈的元素在栈顶； Ap an-1 第一个出栈的元素为栈顶元素； 最后一个出栈的元素为栈底元素。 a, 栈底 1945

— 7— 3.1 栈  栈的示意图 an an-1 … a2 a1 栈顶 栈底 出栈 进栈 第一个进栈的元素在栈底； 最后一个进栈的元素在栈顶； 第一个出栈的元素为栈顶元素； 最后一个出栈的元素为栈底元素。 栈的特点 后进先出 3.1.1 抽象数据类型栈的定义 （LIFO）

前课回顾 SqList L 定位 ListInsert Sq(&L,i,e) 移动 elem 顺序表 插入表长 length listsize 定位 ListDelete Sq(&L,i,&e) 赋值 移动/表长 定位 LNode ListInsert L(L,i,e) 分配结点 链表 data next 插入 LinkList L 定位 ListDelete L(L,i,&e) 删除 释放结点刀 -8

— 8— — 8— 前课回顾 顺序表 链表 SqList L elem length listsize data next LNode LinkList L ListInsert_L(L, i, e) ListInsert_Sq(&L, i, e) 定位 移动 插入/表长 ListDelete_Sq(&L, i, &e) 定位 赋值 移动/表长 定位 分配结点 插入 ListDelete_L(L, i, &e) 定位 删除 释放结点

3.1栈 3.1.1抽象数据类型栈的定义 ADT Stack 数据对象： D={a;a,∈ElemSet,i=1,2,,n,n≥0} 数据关系： R1={|a-1wa;∈D,i=2,,n} 约定an端为栈顶，a1端为栈底。 基本操作： ADT Stack -9 1945

— 9— 3.1 栈 ADT Stack { 数据对象： D＝{ ai | ai ∈ElemSet, i=1,2,...,n, n≥0 } 数据关系： R1＝{ | ai-1, ai∈D, i=2,...,n } 约定an 端为栈顶，a1 端为栈底。 基本操作： } ADT Stack 3.1.1 抽象数据类型栈的定义

3.1栈 一3.1.1抽象数据类型栈的定义 ■栈的基本操作 DestroyStack(&S) InitStack(&S) StackEmpty(S) GetTop(S,&e) ClearStack(&S) Push(&S,e) Pop(&S,&e) -10 1945

— 10 — 3.1 栈 InitStack(&S) ClearStack(&S) StackEmpty(S) GetTop(S, &e) Push(&S, e) Pop(&S, &e)  栈的基本操作 DestroyStack(&S) 3.1.1 抽象数据类型栈的定义