数据结构-栈和队列

堆栈与队列，信息学院暑期培训，堆栈与队列，学习目标掌握两种抽象数据类型堆栈与队列的特点，并能在相应的应用问题中正确选择它们。熟悉循环队列和链式队列的基本操作和实现算法。了解递归算法执行期间堆栈状态变化的过程。焦点和难点堆栈和队列是编程中广泛使用的两种线性数据结构。本章的重点是掌握这两种结构的特点，以便在应用问题中正确使用。知识点序列堆栈、链堆栈、循环队列、链队列、堆栈和队列、堆栈和队列是程序设计中广泛使用的两种线性数据结构。与线性表相比，它们的插入和删除操作受到更多的约束和约束，因此它们也被称为限制性线性表结构。线性表格允许在表格中的任何位置插入和删除。堆栈只允许在表的末尾插入和删除。队列只能在表的末尾插入，在头的末尾删除。嘿。3堆栈和队列，堆栈可以在计算机中以多种方式实现：硬堆栈：它是通过使用CPU或类似硬件中的一些寄存器组或使用内存的特殊区域来实现的。这种堆栈容量有限，但速度非常快。软堆栈：这种类型的堆栈主要在内存中实现。堆栈容量可能非常大。在实现方面，也有两种方式：动态和静态。本章将讨论堆栈和队列的基本概念、存储结构、基本操作以及这些操作的具体实现。嘿。3.1堆栈，1堆栈概念堆栈：一个线性表，它限制表一端的插入和删除操作。也称为后进先出后进先出(last in first out)或先进先出(LastInFirstOut)线性表。顶端：允许插入和删除的堆栈末端，也称为表的末端。栈顶指针(top)用于指示栈顶元素。底部：它是一个固定的末端，也称为头部。空堆栈：当表中没有元素时，称为空堆栈。3.1.1堆栈的基本概念，3.1.1堆栈的基本概念，设置堆栈S=(a1，a2、an)，a1称为堆栈的底部元素，an是堆栈的顶部元素，如图3-1所示。堆栈中的元素按a1、a2，要从堆栈中推出的第一个元素应该是堆栈的顶部元素。也就是说，根据后进先出的原则修改堆栈。堆栈图，先进先出(FILO)，后进先出(LIFO)的特征，a1，a2，a3，进入堆栈，退出堆栈，插入：进入堆栈，进入堆栈，推入堆栈删除：退出堆栈，弹出堆栈，堆栈的逻辑结构，例如：有三个元素以A，B，C的顺序进入堆栈，每个元素只允许进入堆栈一次，那么可能有多少种堆栈序列？a，b，c，案例1: a，b，c，堆栈的逻辑结构，a，b，c，堆栈序列：c，b，堆栈序列：c，b，a，示例：有三个元素按a，b，c的顺序排列，每个元素只允许进入堆栈一次，有多少个可能的堆栈序列？案例1:堆栈的逻辑结构，案例2:示例：如果三个元素按a、b和c的顺序堆叠，并且每个元素只允许堆叠一次，那么有多少种可能的堆叠顺序？堆栈的逻辑结构如下：A .堆栈顺序：B，堆栈顺序：B，C，堆栈顺序：B，C，A，C。注意：堆栈只限制表插入和删除操作的位置，不限制插入和删除操作的时间。例如，如果三个元素以A、B和C的顺序堆叠，并且每个元素只允许堆叠一次，那么有多少种可能的堆叠顺序？情景2:还有别的吗？3.1.1堆栈的基本概念，由堆栈2的抽象数据类型定义的ADT堆栈数据对象：d=AI | AI elemset，I=1，2，n，n0数据关系：R=|ai-1，AI d，I=2，3，n基本操作：初始化、堆栈条目、堆栈移除、堆栈顶部元素提取等。ADTStack，Adttack 数据对象：d=AI | AI elemset，I=1，2，n，n 0数据关系：R1=| AI-1，AI d，I=2，n基本操作：InitStack(，3.1.2.1堆栈动态顺序存储表示，堆栈外节点：首先执行top减1以使top指向堆栈顶部元素的存储位置，然后取出堆栈顶部元素。，图3-2(动态)堆栈变化示意图，3.1.2.1堆栈动态顺序存储表示，基本操作1堆栈类型定义的实现# #defineSTACK_SIZE100/*/*堆栈初始矢量大小*/# DefinedStackment 10/*存储空间分配增量*/# TypeDefinedTeleType；typedefstructsqstack ElemType *底部；/*堆栈不存在。该值为空*/元素类型*顶部；/*堆栈顶部指针*/intstacksize。/*当前分配的空间，单位为元素*/ SqStack；3.1.2.1堆栈的动态顺序存储表明初始化状态为init _ stack(void) sqstacks；s . bottom=(ElEMTYPe *)malloc(STACK _ SIZE * sizeof(ElEMTYPe)；如果(！返回错误；顶部=底部；/*堆栈为空时，堆栈顶部和底部指针相同*/s . stack size=stack size；返回确定；堆栈的动态顺序存储表示3堆栈(元素推送)状态推送(sqstacks，elem type) if(s . top-s . bottom=s . stack size-1) s . bottom=(elem type *)real loc(s . stackincrementstack _ size)* size of(elem type)；/*堆栈已满，额外存储空间*/if(！返回错误；顶部=底部堆叠大小；S.stacksize=STACKINCREMENT。*顶部=东；S.top。/*栈顶指针加1，e成为新的栈顶*/returnOK；堆栈的动态顺序存储表示四次堆栈(元素弹出)状态p (sqstacks，elemtype * e)/*弹出堆栈顶部元素*/if (s.top=s.bottom)返回错误；/*堆栈为空，返回失败标志*/s . top-；e=*S顶部；返回确定；，3.1.2.2堆栈静态顺序存储表示，使用静态一维数组来存储堆栈。栈的底部是固定的，而栈的顶部随着栈的进入和退出操作而改变；堆叠的底部是固定的；栈顶随着栈的推和拉操作而变化。整数变量TOP(称为顶部指针)用于指示堆栈的当前顶部位置。 top=0用于指示堆栈清空的初始状态，每次top都指向数组中堆栈顶部的存储位置。节点堆叠：首先执行top+1，将top指向堆栈的新顶部位置，然后将数据元素保存到堆栈的顶部(TOP指向的当前位置)。堆栈的3.1.2.2静态顺序存储表示，堆栈外节点：首先，移除顶部指向的顶部元素，然后执行top减1以使top指向堆栈的新顶部位置。如果堆栈数组有Maxsize元素，当top=Maxsize-1时，堆栈已满。图3-3是尺寸为5的堆叠的示意图。嘿。3.1.2.2栈静态顺序存储意味着基本操作的实现1栈类型定义#defineMAX_STACK_SIZE100/*栈向量大小*/# typedelemtype；typedefstructsqstack ElemTypeStack _ array最大堆栈大小；inttop SqStack3.1.2.2堆栈的静态顺序存储表示2堆栈sqstackinit _ stack(void) sqstacks；底部=顶部=0；返回；，3.1.2.2堆栈静态顺序存储意味着3推送(元素推送)状态推送(sqstacks，elemtype)/*使数据元素e推送至新的堆栈顶部*/if (s.top=max _ stack _ size-1)返回错误；/*堆栈已满，返回错误标志*/s . top；/*栈顶指针加1 */栈顶数组=e；/*e成为新的堆栈顶部*/returnOK；/*堆栈按成功*/，3.1.2.2堆栈的静态顺序存储表示，4堆栈(元素弹出)状态弹出(SQStacks，元素类型* E)/*弹出堆栈顶部元素*/如果(S.top=0)返回错误；/*堆栈为空，返回错误标志*/* e=堆栈_数组顶部；s . top-；返回确定；，3.1.2.2堆栈静态顺序存储是指堆栈顶部指针指向实际堆栈顶部之后的空位置，初始值为0，堆栈条目，A，堆栈退出，堆栈已满，B，C，D，E，F，将数组大小设置为Mtop=0，堆栈为空，当堆栈退出时，在流top=M下，堆栈已满，当堆栈条目溢出、堆栈为空，堆栈条目：top加1，堆栈外：TOP减1，3.1.2.2堆栈的静态顺序存储意味着当堆栈已满时，当堆栈被推入时，必然会发生空间溢出，这称为“溢出”。溢出是一种错误情况，应该避免。当堆栈为空时，当堆栈被移除时也会发生溢出，这被简单地称为“下溢”。下溢可能是一种正常现象，因为当堆栈在使用时，其初始状态或最终状态是空堆栈，所以下溢经常被用作控制转移的条件。1堆栈的链存储结构称为链堆栈，它是一个具有有限操作的链表。插入和删除操作只能在标题位置执行。因此，没有必要附加，链堆栈的节点类型描述如下：typedefructstack _ node elemtypedata；下一步；堆栈_节点；3.1.3堆栈的链存储表示2链堆栈的基本操作的实现(1)堆栈的初始化_节点*初始化_链接_堆栈(void)堆栈_节点*顶部；top=(堆栈节点*)malloc(大小为(堆栈节点)；上-下=空；返回(顶部)；堆栈的链存储表示，(2)推送(元素推送)状态推送(堆栈_节点*顶部，元素类型)堆栈_节点* p；p=(堆栈节点*)malloc(大小为(堆栈节点)；如果(！p)返回错误；/*申请新节点失败，返回错误标志*/p-数据=e；p-next=top-next；top-next=p；/*钩环*/返回正常；堆栈的链存储表示弹出(元素弹出)状态弹出(堆栈_节点*顶部，元素类型* e)/*将顶部元素推出堆栈*/堆栈_节点* p；电子类型；如果(上一个=空)返回错误；/*堆栈为空，返回错误标志*/p=上一个；e=p-数据；/*取栈顶元素*/top-next=p-next；/*修改堆栈顶部指针*/free(p)；返回确定；对于栈的应用来说，栈因其“后进先出”的固有特性，已经成为编程中常用的工具和数据结构。下面是一些堆栈应用程序的例子。嘿。3.2.1数字转换，对于任何输入的非负十进制整数，打印并输出其等效的八进制数。例如，十进制数159被转换成八进制数。十进制整数n到其它十进制数d (2，8，16)的转换是计算机实现计算的基本问题。转换规则：这个转换规则对应一个简单的算法原理：n=(ndivd)*d nmodd，其中：div是可分运算(/)，mod是余数运算(%)，voidconversion(intn，intd)/*通过静态顺序堆栈方法实现，将十进制整数N转换为d(2或8)十进制数*/ SqStacks；intk，* e；S=初始化_堆栈()；而(n0) k=n % d；推动(S，k)；n=n/d。/*找到所有的剩余部分，并将它们放在堆栈中*/while(顶部！=0)/*堆栈不为空时被推出，并输出*/pop(S，e)；printf(,*e)；，3.2.1数字转换，3.2.2、括号匹配问题，在文字处理软件或编译器设计中，经常需要检查括号中的字符串或表达式是否匹配？匹配思想：如果从左到右扫描一个字符串(或表达式)，那么每个右括号将匹配遇到的最后一个左括号。从左到右扫描期间遇到的左括号可以存储在堆栈中。每当遇到闭合支架时，它与堆栈顶部的开口支架(如果有)匹配，并且开口支架从堆栈顶部移除。该算法的思想是建立一个堆栈。读取左括号时，左括号被推入堆栈。读取右括号时，堆栈中会弹出一个元素，与读取的左括号匹配。如果匹配成功，请继续阅读。否则，匹配失败，并返回FLASE。3.2.2括号匹配问题，算法描述# definet rue 0 # defineflag-1qstacks；S=初始化_堆栈()；/*堆栈初始化*/，intmatch _括号()char，x；Scanf (%c ，3.2.3回文游戏(向前读和向后读字符串(不带空格)，算法思想：读入字符串；删除空格(原始字符串)；压入堆栈；将原始字符串字符依次与堆栈字符进行比较；如果不是，不是回文；如果直到堆栈为空时都是相等的，请回复。嘿。3.2.2堆栈和递归调用的实现。堆栈的另一个重要应用是在编程语言中实现递归调用。递归调用：一个函数(或过程)直接或间接调用自己，这被简单地称为递归。递归是编程中一个强大的工具。因为递归函数结构清晰，程序易读，而且它们的正确性很容易证明。为了防止递归调用无终止地进行，实际上，有效的递归调用函数(或过程)应该包括两部分：递归规则(方法)和终止条件。例如：n！为了保证递归调用的正确执行，系统建立了一个“递归工作栈”，作为整个递归调用过程中使用的数据存储区。每一层递归地包含参数、局部变量和前一层的返回地址等信息，以形成一个“工作记录”。每次进入递归层，都会生成一个新的工作记录，并将其推到堆栈的顶部。每当您退出递归层时，一个工作记录就会从堆栈顶部弹出。，3.2.2堆栈和递归调用