当前位置：文档之家 › 数据结构CH3 栈和队列 12-03-12

数据结构CH3 栈和队列 12-03-12

  • 格式：ppt
  • 大小：2.60 MB
  • 文档页数：91

下载文档原格式

  / 91

合集下载

ch3栈和队列课件PPT

ch3栈和队列课件PPT


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

数据结构--栈和队列基础知识

数据结构--栈和队列基础知识⼀概述栈和队列，严格意义上来说，也属于线性表，因为它们也都⽤于存储逻辑关系为 "⼀对⼀" 的数据，但由于它们⽐较特殊，因此将其单独作为⼀篇⽂章，做重点讲解。

既然栈和队列都属于线性表，根据线性表分为顺序表和链表的特点，栈也可分为顺序栈和链表，队列也分为顺序队列和链队列，这些内容都会在本章做详细讲解。

使⽤栈结构存储数据，讲究“先进后出”，即最先进栈的数据，最后出栈；使⽤队列存储数据，讲究 "先进先出"，即最先进队列的数据，也最先出队列。

⼆栈2.1 栈的基本概念同顺序表和链表⼀样，栈也是⽤来存储逻辑关系为 "⼀对⼀" 数据的线性存储结构，如下图所⽰。

从上图我们看到，栈存储结构与之前所了解的线性存储结构有所差异，这缘于栈对数据 "存" 和 "取" 的过程有特殊的要求：1. 栈只能从表的⼀端存取数据，另⼀端是封闭的；2. 在栈中，⽆论是存数据还是取数据，都必须遵循"先进后出"的原则，即最先进栈的元素最后出栈。

拿图 1 的栈来说，从图中数据的存储状态可判断出，元素 1 是最先进的栈。

因此，当需要从栈中取出元素 1 时，根据"先进后出"的原则，需提前将元素 3 和元素 2 从栈中取出，然后才能成功取出元素 1。

因此，我们可以给栈下⼀个定义，即栈是⼀种只能从表的⼀端存取数据且遵循 "先进后出" 原则的线性存储结构。

通常，栈的开⼝端被称为栈顶；相应地，封⼝端被称为栈底。

因此，栈顶元素指的就是距离栈顶最近的元素，拿下图中的栈顶元素为元素 4；同理，栈底元素指的是位于栈最底部的元素，下中的栈底元素为元素 1。

2.2 进栈和出栈基于栈结构的特点，在实际应⽤中，通常只会对栈执⾏以下两种操作：向栈中添加元素，此过程被称为"进栈"（⼊栈或压栈）；从栈中提取出指定元素，此过程被称为"出栈"（或弹栈）；2.3 栈的具体实现栈是⼀种 "特殊" 的线性存储结构，因此栈的具体实现有以下两种⽅式：1. 顺序栈：采⽤顺序存储结构可以模拟栈存储数据的特点，从⽽实现栈存储结构。

数据结构3栈和队列PPT教学课件

数据结构3栈和队列PPT教学课件


~AStack() { delete [] elements; } // Destructor
void clear() { top = 0; }
注意：这里top在第I个位置
2020/12/12
8
一些重要的条件
栈满：top==maxSize-1； 栈空：top==-1
2020/12/12
9
链式栈
{
private:
int MaxSize;
// 栈中最大元素个数
int top;
// 栈中实际元素个数
T *elements; // 存储栈元素的数组
public:
AStack(int sz =DefaultListSize) // Constructor
{ size = sz; top = 0; elements = new T[sz]; }
virtual void MakeEmpty() = 0; virtual int isEmpty（） virtual int isFull（）=0
};
2020/12/12
5
顺序栈
由于栈是运算受限的线性表，因此 线性表的存储结构对栈也适应。
栈的顺序存储结构简称为顺序栈， 它是运算受限的线性表。因此，可用 数组来实现顺序栈。因为栈底位置是 固定不变的，所以可以将栈底位置设 置在数组的两端的任何一个端点；栈 顶位置是随着进栈和退栈操作而变化 的，故需用一个整型变量top
时间上：顺序栈为O(1),链式栈为O(1) 空间上：顺序栈要一个固定的长度，当栈不够
满时，空间浪费；链式栈长度可变，但对于每 个元素需要一个链接域，产生结构性开销。 何时使用顺序栈？ 当要实现多个栈时，可用一个数组存储两个栈， 且最好是一个栈增长时另一个栈缩短。
数据结构第三章 数据结构堆栈和队列

数据结构第三章 数据结构堆栈和队列

数据结构第三章数据结构堆栈和队列在计算机科学中，数据结构是组织和存储数据的方式，以便能够高效地访问和操作这些数据。

在数据结构的众多类型中，堆栈和队列是两种非常重要且常用的结构。

首先，让我们来了解一下堆栈。

堆栈就像是一个垂直堆放的容器，遵循着“后进先出”（Last In First Out，简称LIFO）的原则。

想象一下，你有一堆盘子，每次你把新盘子放在最上面，而当你要取盘子时，也只能从最上面拿。

这就是堆栈的工作方式。

在编程中，堆栈有着广泛的应用。

比如，函数调用就是一个典型的例子。

当一个函数调用另一个函数时，新函数的信息被压入堆栈。

当被调用的函数执行完毕后，其信息从堆栈中弹出，程序回到原来的函数继续执行。

此外，表达式求值也常常会用到堆栈。

例如，计算一个复杂的算术表达式时，可以将操作数和运算符依次压入堆栈，然后按照特定的规则进行计算。

堆栈的实现可以通过数组或者链表来完成。

如果使用数组实现，需要注意堆栈的大小可能会有限制。

而链表实现则相对灵活，但其操作的复杂度可能会略高一些。

接下来，我们再看看队列。

队列则像是一条排队的队伍，遵循“先进先出”（First In First Out，简称 FIFO）的原则。

就好比在银行排队办理业务，先来的人先得到服务并离开队伍。

在实际应用中，队列也非常有用。

例如，打印机的打印任务队列就是一个典型的例子。

新的打印任务被添加到队列的末尾，而打印机按照任务进入队列的顺序依次处理。

还有操作系统中的任务调度，也常常会用到队列来管理等待执行的任务。

队列同样可以通过数组或者链表来实现。

使用数组实现时，可能会面临队列前端元素删除后空间浪费的问题。

而链表实现虽然可以避免这个问题，但需要额外的指针操作。

那么，堆栈和队列在操作上有哪些不同呢？对于堆栈，主要的操作是入栈（push）和出栈（pop）。

入栈就是将元素添加到堆栈的顶部，出栈则是从堆栈的顶部取出元素。

而对于队列，主要的操作是入队（enqueue）和出队（dequeue）。

数据结构实验报告 栈和队列

数据结构实验报告 栈和队列

数据结构实验报告栈和队列
栈（Stack）和队列（Queue）都是常用的数据结构。

它们都是有限的数据存储结构，主要用于记录数据的存储和检索。

它们具有许多相同的特征，可以根据每一个实例的需要而定制遍历，并可以使用相同的存储方法。

但是，从数据操作和操作数据的角度来看，它们仍有差异。

首先，栈和队列的数据操作模式不同。

栈是遵循“先进后出”（LIFO）的原则，只有最后一个元素可以被弹出或者取出；而队列则是遵循“先进先出”（FIFO）的原则，第一个元素是最先被取出或弹出的。

此外，栈不允许插入新元素，而队列允许任何位置插入和删除元素。

此外，栈只能被依次访问，而队列允许改变已有元素的位置。

此外，栈和队列可以用相似的实现方式来构建。

一般来说，它们都使用 .链表，数组或者树来存储数据，并使用相同的Pointers来指向数据结构中的元素。

栈和队列也可以使用交换的方式来改变其存储方式，从而提高其效率。

对于实际应用来说，栈和队列都有自己的优势，具体取决于应用中的需求。

比如，栈通常被用于数据的深度优先遍历，而队列则可以用于数据的广度优先遍历。

此外，栈也可以用于处理函数调用，而队列可以用于处理操作系统任务或者打印池中的任务等。

数据结构(C语言版)3 栈和队列

数据结构(C语言版)3 栈和队列

typedef struct node { StackElementType data; struct node *next; }LinkStackNode; typedef LinkStackNode *LinkStack;
25
链栈基本操作的实现
int Push(LinkStack top, StackElementType x) /*将数据元素 压入栈 中*/ 将数据元素x压入栈 将数据元素 压入栈top中 {LinkStackNode * temp; temp=(LinkStackNode * )malloc(sizeof(LinkStackNode)); if(temp==NULL) return(FALSE); /*申 申 请空间失败*/ 请空间失败 temp->data=x; temp->next=top->next; top->next=temp; /*修改当前栈顶指针 */ 修改当前栈顶指针 return(TRUE);}
32
InitStack Push Pop
两栈共享基本操作的实现
int Pop(DqStack *S, StackElementType *x, int i) {switch(i) {case 0:if(S->top[0]==-1) return(FALSE); *x=S->Stack[S->top[0]]; S->top[0]--; break; case 1:if(S->top[1]==M) return(FALSE); *x=S->Stack[S->top[1]]; S->top[1]++;break; default: return(FALSE); } return(TRUE); }
数据结构栈和队列

数据结构栈和队列

数据结构03栈与队列通常称,栈与队列是限定插入与删除只能在表地"端点"进行地线性表。

线性表栈（表尾）队列（队尾）Insert(L,i,x)Insert(S,n+1,x)Insert(Q,n+1,x)1≤i≤n+1Delete(L,i)Delete(S,n)Delete(Q,1)1≤i≤n栈与队列是两种常用地数据类型3.1 栈地基本概念3.2 栈地顺序存储结构与实现3.3 栈地链式存储结构与实现3.4 队列地基本概念3.5 队列地顺序存储3.6 队列地链式存储先入后出同点？后入先出栈（Stack）是限定仅在表尾进行插入或删除地线性表。

允许插入与删除地一端叫做栈顶（Top）,另一端叫做栈底（Base）。

当栈没有任何元素时则称为空栈。

假设栈S=(a1,a2,a3,…an),则a1称为栈底元素,an为栈顶元素。

栈元素按a1,a2,a3,…an地次序进栈,弹栈地第一个元素应为栈顶元素。

因此,栈地修改是按后进先出地原则进行地,所以,栈称为后进先出LIFO。

栈地抽象数据类型定义为:ADT Stack{数据对象:D={ai|ai∈ElemSet,i=1,2,…,n,n≥0}数据关系:R={<ai-1,ai>|ai-1,ai∈D,i=2,…,n}约定an端为栈顶,a1端为栈底基本操作:}ADT StackInitStack(&S)初始条件:无操作结果:构造一个空栈S DestoryStack(&S)初始条件:栈S已存在操作结果:栈S被销毁CleanStack(&S)初始条件:栈S已存在操作结果:栈S清为空栈StackEmpty(S)初始条件:栈S已存在操作结果:若栈S为空栈,则返回TRUE,否则FALSE StackLength(S)初始条件:栈S已存在操作结果:返回S地元素个数,即栈地长度GetTop(S,&e)初始条件:栈S已存在且非空操作结果:用e返回S地栈顶元素… …a1a2anPush(&S,e)初始条件:栈S已存在操作结果:插入元素e为新地栈顶元素… …a1a2an ean Pop(&S,&e)初始条件:栈S 已存在且非空操作结果:删除S 地栈顶元素,并用e 返回其值a1a2an-1… …e=anStackTraverse(S,visit())初始条件:栈S已存在且非空操作结果:从栈顶到栈底依次对S地每个元素调用函数visit()。

数据结构栈和队列的特点

数据结构栈和队列的特点

数据结构栈和队列的特点
嘿，你知道吗，数据结构里的栈和队列，那可真是相当有意思的存
在呢！
先来说说栈吧，它就像是一个只能从一端进出的神奇箱子。

你可以
想象一下，就好像你有一堆盘子，你每次只能把新盘子放在最上面，
要拿盘子也只能从最上面拿，这就是栈的特点呀！比如说，你在玩一
个游戏，你不断地获得新道具，就把它们依次放入栈中，当你需要使
用道具时，就从栈顶拿出来，是不是很形象呢？“那这栈的作用到底有
多大呀？”
而队列呢，则像是排队买东西的队伍。

排在前面的人先得到服务，
先进入队列的元素也先出去。

这多像我们在银行排队办业务呀！大家
依次排队，先来的先办，后来的就等着，秩序井然。

“这队列不就保证
了公平性嘛！”
栈和队列在计算机科学中可有着广泛的应用呢！比如在程序运行时，函数的调用就可以用栈来管理，函数一层一层地调用，最后又按照相
反的顺序返回。

而在网络通信中，队列可以用来缓存数据，确保数据
按照顺序进行传输。

“这多重要啊，要是乱了套可不行！”
在实际编程中，我们经常需要根据具体的需求来选择使用栈还是队列。

栈的后进先出特性适合处理一些需要回溯的情况，而队列的先进
先出特性则适合保证顺序的操作。

“你说要是没有它们，那得多混乱呀！”
总之，数据结构中的栈和队列就像是两个非常得力的助手，它们各
自有着独特的特点和用途，为我们的编程世界增添了许多精彩和便利。

它们虽然看似简单，但其背后蕴含的智慧和力量却是不可小觑的呀！。

数据结构实用教程(C语言版) 第3章 栈和队列

数据结构实用教程(C语言版) 第3章 栈和队列

返回到本节目录
3.1.1 栈的概念
假设有一个栈S=（a1，a2，…，an），栈 中元素按a1，a2，…，an的次序进栈后， 进栈的第一个元素a1为栈底元素，出栈的第 一个元素an为栈顶元素，也就是出栈的操作 是按后进先出的原则进行的，其结构如图31所示。
图3-1栈结构示意图
返回到本节目录
3.1.2栈的基本操作
3.1.3顺序栈
由于栈是操作受限制的线性表，因此与线性表类似，栈也 有两种存储结构，即顺序存储结构和链式存储结构。 1. 顺序栈的定义 栈的顺序存储结构称为顺序栈。类似于顺序表的类型定义，顺 序栈是用一个预设的足够长度的一维数组和一个记录栈顶元素 位置的变量来实现。顺序栈中栈顶指针与栈中数据元素的关1.3顺序栈
3. 顺序栈的基本操作实现
（3）进栈操作 进栈操作的过程如图3-3所示。先判断栈S如图3-3（a） 是否为满，若不满再将记录栈顶的下标变量top加1如 图3-3（b），最后将进栈元素放进栈顶位置上如图33（c）所示，算法描述见算法3.3。
图3-3 进栈操作过程图
返回到本节目录
栈除了在栈顶进行进栈与出栈外，还有初始化、判空 等操作，常用的基本操作有： （1）初始化栈InitStack(S)。其作用是构造一个空 栈 S。 （2）判断栈空EmptyStack(S)。其作用是判断是 否是空栈，若栈S为空，则返回1；否则返回0。 （3）进栈Push(S,x)。其作用是当栈不为满时，将 数据元素x插入栈S中，使其为栈S的栈顶元素。 （4）出栈Pop(S,x)。其作用是当栈S不为空时，将 栈顶元素赋给x，并从栈S中删除当前栈顶元素。 （5）取栈顶元素GetTop(S,x)。其作用是当栈S不 为空时，将栈顶元素赋给x并返回，操作结果只是 读取栈顶元素，栈S不发生变化。 返回到本节目录
数据结构第3章栈和队列

数据结构第3章栈和队列


• 出栈 算法步骤： ①判断当前栈空间是否为空，为空则返回值0， 不空则转第2步； ②将top所指位置元素值取出； ③栈顶指针top--，指向新的栈顶元素，成功返 回值1； int Pop_SStack(SeqStack *s, datatype *e) { if (Empty_SStack ( s ) ) return 0; else { *e=s->data[s->top]; s->top--; return 1; 取栈顶元素 } datatype GetTop_SStack(SeqStack *s) { if ( Empty_SStack ( s ) ) return 0; }
• 设队头指针指向队头元素前一个位置，即队头 指针位置+1才是真正队头元素，队尾指针指 向队尾元素。 • 置空队指rear=-1; • 入队指令：sq->rear++; sq->data[sq->rear]=a; • 出队指令：sq->front++; a=sq->data[sq->front]; • 队中元素的个数计算方法： n=(sq->rear)-(sq->front); • 队满时：n= MAXQSIZE； 队空时：n=0
栈的顺序存储
1. 顺序栈的定义 • 利用顺序存储方式实现的栈称为顺序 栈。 栈中的数据元素可用一维数组来 实现：datatype data[MAXSSIZE]， 栈底一般设在数组的低端，在整个进 栈和出栈的过程中不改变，栈顶位置 将随着数据元素进栈和出栈而变化， 一般用一个top 来作为栈顶指针。
• 入队
int In_SeqQue ( c_SeqQue *q , datatype e) { if ((q->rear+1) % MAXQSIZE==q->front) { printf(＂队满＂); return –1; /*队满不能入队*/ } else { q->rear=(q->rear+1) % MAXQSIZE; q->data[q->rear]=e; return 1; /*入队完成*/ } }
数据结构3栈和队列

数据结构3栈和队列

队列的顺序存储结构
使用循环队列来实现。循环队列是将一维数组看作一个首尾相接的圆环，通过两个指针（头指针和尾 指针）来标识队列的头和尾。入队时，将元素添加到队尾；出队时，删除队头元素。
链式存储结构实现
栈的链式存储结构
使用链表来实现。链表的头结点作为栈顶， 链表的尾结点作为栈底。入栈时，在链表头 部插入元素；出栈时，删除链表头部的元素 。
输入 标题
树
树是一种分层的数据结构，由节点和边组成。树常用 于实现层次化数据结构，如文件系统、XML文档解析 等。
链表
图
哈希表是一种通过哈希函数将键映射到值的数据结构， 可以实现快速的查找、插入和删除操作。哈希表常用
于实现字典、缓存等数据结构。
哈希表
图是一种由节点和边组成的数据结构，可以表示任意 复杂的关系网络。图常用于实现网络分析、路径规划 等算法。
数据结构3栈和队列
contents
目录
• 栈与队列基本概念 • 栈操作及应用 • 队列操作及应用 • 栈和队列实现方式 • 经典问题解析与算法设计 • 总结回顾与拓展延伸
01 栈与队列基本概念
栈定义及特点
栈（Stack）是一种特殊的线性数据结 构，其操作只能在一端进行，遵循后 进先出（LIFO, Last In First Out）的 原则。
栈在函数调用中应用
函数调用栈
在程序执行过程中，每当调用一个函数时，系统会将该函数的信息（如参数、局部变量、返回地址等）压入一个 专门的栈中，称为函数调用栈。当函数执行完毕返回时，系统会从函数调用栈中弹出相应的信息，以恢复调用函 数的状态。
递归调用实现
递归函数在调用自身时，系统会将递归调用的信息压入函数调用栈中，包括递归参数、局部变量、返回地址等。 当递归到最底层时开始逐层返回，系统会从函数调用栈中弹出相应的信息进行处理，直到所有递归调用都处理完 毕为止。

第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）：检查栈中 是否还有元素。
回溯到上一个状态。
广度优先搜索中的队列应用
搜索队列
广度优先搜索使用队列来保存待 搜索的节点，按照先进先出的原
则进行搜索。
状态转移
在广度优先搜索中，队列用于保存 状态转移的信息，以便在搜索过程 中根据状态转移规则进行状态的扩 展和搜索。
最短路径问题
广度优先搜索可用于解决最短路径 问题，通过队列保存待访问的节点 ，并按照距离起始节点的远近进行 排序和访问。
其他算法中的栈和队列应用
深度优先搜索
在深度优先搜索中，栈用于保存当前路径的状态信息，以便在需要时 回溯到上一个状态。
括号匹配问题
栈可用于解决括号匹配问题，遇到左括号时将其压入栈中，遇到右括 号时从栈中弹出左括号并判断是否匹配。
表达式求值
栈可用于表达式求值中，保存操作数和运算符，并按照运算优先级进 行求值。
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
stacksize
栈空 5 4 3 2 1 0
top top top
top
base
F E
5
4 3 2 1
base
top top top top top top top
F
E
D C B A 出栈
D
C B
base
栈S空
栈顶指针top, 约定指向实际 栈顶前的空位置，初值为0
A 0 进栈
设数组大小为stacksize top= 0 ,栈空,此时出栈,则下溢（underflow) top=Stacksize,栈满,此时入栈,则上溢（overflow) stacksize-1 B栈底
2013年10月10日4时48分
2013年10月10日4时48分
例二、 括号匹配的检验
假设在表达式中，只有［］（）两种 括号，如：（［］（） （［ ］））、 ［（［ ］［ ］）］等为正确的格式， ［（ ］）或（［（ ））或 （（） ］ ） 均为不正确的格式。
检验括号是否匹配的方法可用: “期待的急迫程度”这个概念来描述。
Status Pop (SqStack &S, SElemType &e) { // 若栈不空，则删除S的栈顶元素， // 用 e 返回其值，并返回OK；
// 否则返回ERROR if (S.top = = S.base) return ERROR; e = * -- S.top;
return OK;
Status matching(string& exp) { state = 1; i=0； while (i<Length(exp) && state) { switch (exp[i]) { case ”(” ,”[”:{Push(S,exp[i]); i++; break;} case”)”: { if(NOT StackEmpty(S)&&GetTop(S)=“(“ {Pop(S,e); i++;} else {state = 0;} break; } …… 。。。。。。。 }
在用户输入一行的过程中，允 许用户输入出差错，并在发现有误时 可以及时更正。
合理的作法是：
设立一个输入缓冲区，用以接 受用户输入的一行字符，然后逐行 存入用户数据区; 并假设“#”为退 格符，“@”为退终端接受了这样两行字符： whli##ilr#e（s#*s) outcha@putchar(*s=#++); 则实际有效的是下列两行：
*sizeof(SElemType));
if (!S.base) exit( OVERFLOW); S.top= S.base +S.stacksize; S.stacksize+=STACKINCREMENT; } *S.top++ = e; return OK; }
2013年10月10日4时48分
x
–出栈
q
top top …... 栈底 ^
2013年10月10日4时48分
3.3
栈的应用举例
例一、 数制转换 例二、 括号匹配的检验
例三、 行编辑程序问题
例四、 迷宫求解 例五、 表达式求值
例六、 实现递归
2013年10月10日4时48分
例一、 数制转换
算法基于原理： (N)d1 = (N div d2)×d2 + N mod d2
2013年10月10日4时48分
top的初值指向栈底：top=base，此条件也可作为判栈空的条件； 在实际使用中，top 始终指向栈顶元素的下一个位臵上； 入栈（插入新的栈顶元素）：top增1； 出栈（删除栈顶元素）： top减1。
2013年10月10日4时48分
栈满 5 4 3 2 1 top=0 0 top top
while (*s)
putchar(*s++);
2013年10月10日4时48分 Void LineEdit ( ) { InitState(S); ch=getchar( ); while (ch != EOF) { //EOF为全文结束符 while (ch != EOF && ch != '\n') { switch (ch) { case '#' : Pop(S, c); break; case '@': ClearStack(S); break;// 重臵S为空栈 default : Push(S, ch); break; } ch = getchar( ); // 从终端接收下一个字符 }
2013年10月10日4时48分
例如：（1348)10 = (2504)8 ，其 运算过程如下：
计 算 顺 序
N N div 8 1348 168 168 21 21 2 2 0
N mod 8 4 0 5 2
输 出 顺 序
void conversion () { InitStack(S); 以（1348)10为例： N N/8 N%8 scanf ("%d",N); 1348 168 4 while (N) { 168 21 0 21 2 5 Push(S, N % 8); 2 0 2 N = N / 8; } while (!StackEmpty(S)) { 2 2504 5 Pop(S,e); 0 printf ( "%d", e ); 4 } } // conversion
2013年10月10日4时48分
InitStack(&S)
DestroyStack(&S) StackLength(S) StackEmpty(s) GetTop(S, &e) ClearStack(&S) Push(&S, e) Pop(&S, &e)
StackTravers(S, visit())
由此看出,栈和队列是限定插入和删除 只能在“端点”进行的线性表。
2013年10月10日4时48分
3.1 栈的类型定义
3.2 栈类型的实现 3.3 栈的应用举例 3.4 队列的类型定义
3.5 队列类型的实现
练习
2013年10月10日4时48分
• 栈的定义和特点
3.1 栈的类型定义
• 定义：限定仅在表尾进行插入或删除操作的线 性表，表尾—栈顶，表头—栈底，不含 元素的空表称空栈。 • 特点：先进后出（FILO）或后进先出（LIFO）
a1 a2 … … an-1 an
e = an
2013年10月10日4时48分
3.2 栈类型的实现
3.2.1 顺序栈
3.2.1 链
栈
2013年10月10日4时48分
3.2.1 顺序栈
类似于线性表的顺序映象实现，利 用一组地址连续的存储单元依次存放 自栈底到栈顶的数据元素，同时附设
指向表尾的指针top，指示栈顶元素在
将从栈底到栈顶的字符传送至调用过程的数据区；
ClearStack(S); // 重臵S为空栈 if (ch != EOF) ch = getchar(); } DestroyStake(S); }// LineEdit
2013年10月10日4时48分
例四、 迷宫求解
通常用的是“穷举求解”的方法
2013年10月10日4时48分
2013年10月10日4时48分
例三、行编辑程序问题
常用的文本编辑器如：word、记事 本，最简单的文本编辑器实现的功能是： 接受用户从终端输入的程序或数据，并 存入用户的数据区。
思考：如何实现？ “每接受一个字符即存入存储器”
?
并不恰当！
2013年10月10日4时48分
2013年10月10日4时48分
2013年10月10日4时48分
栈和队列是两种特殊的线性表，是操作 受限的线性表，称限定性DS。
线性表
栈
队列
Insert(L, i, x) Insert(S, n+1, x) Insert(Q, n+1, x) 1≤i≤n+1 Delete(L, i) Delete(S, n) Delete(Q, 1) 1≤i≤n
2013年10月10日4时48分
StackLength(S) 初始条件：栈 S 已存在。 操作结果：返回 S 的元素个 数，即栈的长度。
2013年10月10日4时48分
GetTop(S, &e) 初始条件：栈 S 已存在且非空。 操作结果：用 e 返回 S 的栈顶元素。
a1 a2 …… an
2013年10月10日4时48分
基本操作实现
为减少溢出的概率，可以在同一段内存中同时使用两个栈. 0
A栈底
A栈顶
B栈顶
2013年10月10日4时48分
Status InitStack (SqStack &S) { // 构造一个最大空间为 STACK_INIT_SIZE 的空顺序栈 S S.base=(SElemType*)malloc( ↓ ); STACK_INIT_SIZE*sizeof(SElemType) if (!S.base) exit (OVERFLOW); //存储分配失败 S.top = S.base; S.stacksize = STACK_INIT_SIZE; return OK;
}
2013年10月10日4时48分
Status Push (SqStack &S, SElemType e) { if (S.top - S.base >= S.stacksize) {//栈满 S.base=(SElemType*)realloc(S.base，
(STACK_INIT_SIZE+STACKINCREMENT)