"山东大学《数据结构》讲义03栈和队列.docx；栈和队列的特性与运用"

栈和队列是数据结构中的两种特殊线性表，它们的特殊性表现在它们的基本操作是线性表操作的子集，因此可以说它们是限定性的数据结构。从抽象数据类型的角度来看，栈和队列是与线性表不同的两类重要的抽象数据类型。 栈具有后进先出（LIFO）的特性，即最后压入的元素最先弹出，而最先压入的元素最后弹出。栈的基本操作包括压栈（Push）、弹栈（Pop）、取栈顶元素（Top）等，因此栈可以用于实现一些需要按照后进先出顺序进行操作的场景，比如递归函数的调用过程中就需要使用栈来保存每次函数调用后的返回地址和参数。 队列具有先进先出（FIFO）的特性，即最先进入队列的元素最先被取出，而最后进入队列的元素最后被取出。队列的基本操作包括入队（Enqueue）和出队（Dequeue），其中入队操作在队列的末尾插入新元素，出队操作则删除队列的前端元素并返回其值。队列适用于需要按照先进先出顺序进行操作的场景，比如进程调度等。 栈和递归之间存在密切的关系。在递归函数的执行过程中，每个函数调用都会创建一个新的局部变量和一些执行上下文信息，并将这些信息存储在栈中。当函数调用完成后，栈会弹出该函数的执行上下文，以便继续执行前一个函数的操作。因此，可以说递归是一个栈的应用，栈的特殊性质使得递归能够正常工作。 假设一个栈的入栈序列为1, 2, 3,...,n，输出序列为pl, p2, p3,...,pn。已知pl=n，则pi的值为n-1。由于栈的特性，每个元素出栈后，下一个出栈的元素是栈顶的元素，因此pi的值就是顺序栈中弹出顺序的下一个元素。 假设顺序栈中6个元素的出栈顺序为s2, s3, s4, s6, s5, s1，那么顺序栈的容量至少应为6。这是因为在出栈过程中，要保证每个元素都能顺利弹出，需要为每个元素分配一个空间。 循环队列是一种特殊的队列，它可以在固定大小的空间中循环使用，解决了普通队列随着元素入队和出队的不断变化而造成的空间浪费问题。循环队列中，队列空和队列满的评定标准是： - 当队列头指针与队列尾指针相等时，队列为空 - 当队列尾指针指向队列的最后一个位置，而队列头指针指向队列的第一个位置的前一个位置时，队列为满。 利用两个栈可以模拟一个队列的入队、出队和判断队空等运算。其中一个栈用于入队操作，另一个栈用于出队操作。当进行入队操作时，直接将元素压入入队栈中；进行出队操作时，如果出队栈为空，则将入队栈中的元素倒入出队栈中，然后进行出栈操作。通过这样的设计，可以实现队列的先进先出特性。 在本章中，重点讨论了栈和队列的抽象数据类型定义、顺序表示与实现、链式表示与实现、以及它们的一些应用。栈和队列由于其广泛的实际应用和操作的特殊性，对于理解数据结构和算法的设计思想具有重要的意义。