"数据结构第3章：限定性线性表—栈和队列"

栈)：构造一个空栈。判空 StackEmpty(S)：若栈为空返回真，否则返回假。进栈 Push(S, e)：若栈不满，则将元素 e 压入栈顶。出栈 Pop(S, e)：若栈不空，则删除栈顶元素，并用 e 返回其值。取栈顶元素 GetTop(S, e)：若栈不空，则用 e 返回栈顶元素的值，栈顶指针不变。4. 栈的存储结构顺序栈：利用一维数组存储栈中元素，用栈顶指针 top 指示栈顶元素在数组中的位置。链栈：用链表表示的栈称为链栈。链栈入栈和出栈等操作均在单链表的表头进行。3.2 队列1. 队列的定义线性表中仅表头进行删除操作，表尾进行插入操作的线性表。Q = (a1, a2, …, an)队头(front)：删除元素的一端称为队头。队尾(rear)：插入元素的一端称为队尾。入队(enqueue)：插入操作。出队(dequeue)：删除操作。空队列：不含元素的空表。对头元素：a1；队尾元素：andequeue enqueue a1 a2 … an 队头 队尾2. 队列的特点“鱼和池塘”(First In First Out) ，简称FIFO结构。队列又称为先进先出线性表。3. 队列基本运算初始化 InitQueue(Q)：构造一个空队列。判空 QueueEmpty(Q)：若队列为空返回真，否则返回假。入队 EnQueue(Q, e)：若队列未满，则将元素 e 插入队列 Q 的队尾。出队 DeQueue(Q, e)：若队列不空，则删除队列 Q 的队头元素，并用 e 返回其值。4. 队列的存储结构顺序队列：利用一维数组存储队列中元素，用队头指针 front 和队尾指针 rear 分别指示队列的队头和队尾位置，以便实现入队和出队操作。循环队列：在顺序队列的基础上做了一定的改进，克服了普通顺序队列做 EnQueue 和 DeQueue 操作时需要移动大量元素的问题。链队列：用链表表示的队列称为链队列，入队和出队等操作均在链表的两端进行。5. 栈和队列的应用栈和队列是常用的数据结构，它们在编程中有着广泛的应用。栈适合处理逆波兰表达式、括号匹配、计算机内存管理等问题；队列适合处理操作系统的进程管理、调度算法等问题。结语本章介绍了栈和队列的基本概念、存储结构和基本运算的实现，同时讨论了它们的应用。通过学习本章内容，可以更好地理解和应用栈和队列这两种重要的数据结构。".