03 第03章 栈和队列.pptx

第1页：第三章栈和队列封面

本页为第三章栈和队列封面。本章讲解栈与队列这两种操作受限的线性表：栈后进先出，队列先进先出。

第2页：操作受限的线性表

栈和队列是软件设计中常用的两种数据结构，它们的逻辑结构和线性表相同。不同之处在于，栈和队列的相关操作具有特殊性，它们只是线性表相关操作的一个子集。

更准确地说，一般线性表上的插入、删除操作不受限制，而栈和队列上的插入、删除操作均受某种特殊限制。因此，栈和队列也称作操作受限的线性表。

第3页：栈的概念及操作特征

栈是线性表的一个特例，具有如下特征：

• 栈是线性表的一个特例
• 栈只能对线性表的固定一端进行插入和删除操作
• 栈数据的主要特点是“后进先出”（Last In First Out，LIFO）或“先进后出”（First In Last Out，FILO）

第4页：栈顶、栈底与溢出

栈顶（Top）

栈中允许进行数据插入和删除的那一端

栈底（Bottom）

栈中无法进行数据操作的那一端

栈上溢（Full）

栈内空间已存满数据时仍希望做压栈动作，产生“上溢出”

栈下溢（Empty）

栈内空间已无数据时仍希望做出栈动作，产生“下溢出”

第5页：进栈或入栈（Push）

进栈或入栈（Push）是把元素放入栈顶的操作。依次执行 Push(A)、Push(B)、Push(C) 后，C 位于栈顶，A 位于栈底，最先出栈的将是最后入栈的 C。

第6页：弹出或出栈（Pop）

弹出或出栈（Pop）是从栈顶取出元素的操作。对栈内 ABC 依次执行 Pop()，弹出顺序为 C、B、A，与入栈顺序完全相反，体现后进先出的特点。

第7页：System.Collections.Stack

本页讲解 C# 中实现了栈结构的集合类 System.Collections.Stack，并通过例 3-1 Stack.cs 演示 Push、Pop、Peek 等常用方法的调用方式。

第8页：栈的应用：进制转换

栈可广泛用于解决表达式求值、进制转换、括号匹配、迷宫、递归调用等满足“先进后出”原则的问题，这里仅介绍如何用栈解决进制转换问题。

例 3-1 Demo3-1.cs 给出了进制转换的实现：把除基取余得到的各位余数依次入栈，再依次出栈即可得到目标进制的表示。

第9页：队列的定义

队列（Queue）是只允许在一端进行插入，在另一端进行删除的线性表。它所有的插入均限定在表的一端进行，该端称为队尾，所有的删除则限定在表的另一端进行，该端称为队头。

第10页：队头、队尾与溢出

队头（Head）

队列中允许数据删除的那一端

队尾（Tail）

队列中允许数据插入的那一端

队上溢（Full）

队内空间存满数据时仍希望做入队动作，产生“上溢出”，是空间不足的出错状态

队下溢（Empty）

队内空间已无数据时仍希望做出队动作，产生“下溢出”，是数据不足的出错状态

第11页：入队（Enqueue）

入队（Enqueue）是把元素放到队尾的操作。依次执行 Enqueue(A)、Enqueue(B)、Enqueue(C) 后，A 位于队头，C 位于队尾。

第12页：出队（Dequeue）

出队（Dequeue）是从队头取出元素的操作。对队列 ABC 执行 Dequeue()，最先取得的是最早入队的 A，体现先进先出的特点。

第13页：循环队列

由于数组在删除元素时需要花费大量时间移动大量元素，因此基于数组的队列在队头数据执行出队操作时速度较慢，很少有实际应用，所以多采用循环队列方式。

为了避免大量的数据移动，通常将一维数组中的各个元素看成是一个首尾相接的封闭的圆环，即第一个元素是最后一个元素的下一个元素，这种形式的顺序队列称为循环队列。

第14页：System.Collections.Queue

本页讲解 C# 中实现了队列结构的集合类 System.Collections.Queue，其 Enqueue、Dequeue、Peek 等方法与队列的入队、出队操作一一对应。

第15页：栈和队列小结

栈和队列的基本操作都是单个元素的“进”、“出”操作，栈的操作是进栈和出栈，队列的操作是进队和出队。所不同的是栈是一种“先进后出”的数据结构，而队列是一种“先进先出”的数据结构。

C# 中实现了栈的集合类是 Stack 和 Stack<T> 两种，实现了队列的集合类是 Queue 和 Queue<T> 两种。