问题的提出： 例1 把十进制整数转换为二至十六之间的任一进制数输出。 例1 把十进制整数转换为二至十六之间的任一进制数输出。 例2 括号匹配问题。试编写一个算法，用来检查一个C++语言程序中的花括号、方括号和圆括号是否配对，若能够全部配对则返回1，否则返回0。 例3 判回文 例4 表达式求值

第3章 栈和队列 本章的基本内容是： 栈的基本概念 栈的存储及实现 栈的应用 队列的基本概念 队列的存储及实现 队列的应用 第3章 栈和队列 本章的基本内容是： 栈的基本概念 栈的存储及实现 栈的应用 队列的基本概念 队列的存储及实现 队列的应用 2017/3/15

3.1 特殊线性表——栈 3.1.1 栈的基本概念 栈的逻辑结构 （a1, a2, ……, an） 3.1 特殊线性表——栈 3.1.1 栈的基本概念 栈的逻辑结构 栈：限定仅在表尾进行插入和删除操作的线性表。 空栈：不含任何数据元素的栈。 允许插入和删除的一端称为栈顶，另一端称为栈底。 （a1, a2, ……, an） 栈底 栈顶

3.1.1 栈的基本概念 栈的示意图 入栈 出栈 栈顶 c 插入：入栈、进栈、压栈 删除：出栈、弹栈 栈顶 b 栈顶 a 栈底

c b a 3.1.1 栈的基本概念 栈的示意图 栈的操作特性：后进先出 插入：入栈、进栈、压栈 删除：出栈、弹栈 入栈 出栈 栈顶 栈顶 栈底 栈的操作特性：后进先出

3.1.1 栈的基本概念 c b a 例：有三个元素按a、b、c的次序依次进栈，且每个元素只允许进一次栈，则可能的出栈序列有多少种？ 情况1： 栈顶 c 栈顶 b 栈顶 a 栈底

3.1.1 栈的基本概念 b a 例：有三个元素按a、b、c的次序依次进栈，且每个元素只允许进一次栈，则可能的出栈序列有多少种？ 情况2： 栈顶 b 栈顶 a 栈底

3.1.1 栈的基本概念 c a 例：有三个元素按a、b、c的次序依次进栈，且每个元素只允许进一次栈，则可能的出栈序列有多少种？ 情况2： 栈顶 出栈序列：b、c c 栈顶 出栈序列： b、 c、a a 栈底 注意：栈只是对表插入和删除操作的位置进行了限制，并没有限定插入和删除操作进行的时间。

2009年考研试题 单选第2题 2. 设栈S 和队列Q 的初始状态均为空，元素abcdefg 依次进入栈S。若每个元素出栈后立即进入队列Q，且7 个元素出队的顺序是bdcfeag，则栈S 的容量至少是 A．1 B.2 C.3 D.4

2010年考研试题 单选第1题 若元素a、b、c、d、e、f依次进栈，允许进栈、退栈操作交替进行，但不允许连续三次进行退栈工作，则不可能得到的出栈序列是： A. dcebfa B. cbdaef C. bcaefd D. afedcb 【正确选项】 D 【解析】本题考查栈的基本概念。 快速解题：选项所给序列中出现长度大于等于3的连续逆序子序列，即为不符合要求的出栈序列。

2011年考研试题 单选第2题 元素a，b，c，d，e依次进入初始为空的栈中，若元素进栈后可停留、可出栈，直到所有元素都出栈，则在所有可能的出栈序列中，以元素d开头的序列个数是： A. 3 B. 4 C. 5 D. 6

3.1.2 栈的顺序存储与实现 a1 如何改造数组实现栈的顺序存储？ top 确定用数组的哪一端表示栈底。 3.1.2 栈的顺序存储与实现 如何改造数组实现栈的顺序存储？ 0 1 2 3 4 5 6 7 8 a1 top 确定用数组的哪一端表示栈底。 附设指针top指示栈顶元素在数组中的位置。

3.1.2 栈的顺序存储与实现 a1 a2 a3 top top top 进栈：top加1 栈空：top= -1 出栈：top减1 3.1.2 栈的顺序存储与实现 0 1 2 3 4 5 6 7 8 a1 a2 a3 top top top 进栈：top加1 栈空：top= -1 出栈：top减1 栈满：top= MaxSize-1

顺序栈的类模板 template <class T,int MaxSize > class SeqStack { T data[MaxSize]; //存放栈元素的数组 int top; //栈顶指针，指示栈顶元素在数组中的下标 public: SeqStack( ) ; //构造函数 void Push(T x); //入栈 T Pop( ); //出栈 T Top( ); //取栈顶元素（元素并不出栈） bool Empty( ); //判断栈是否为空 };

顺序栈的实现——入栈 操作接口： void Push( T x ); 时间复杂度？ template <class T,int MaxSize> void SeqStack<T,MaxSize>::Push(T x) { if (top== MaxSize-1) {cerr<<"上溢"; exit(1);} top++; data[top]=x; } 时间复杂度？

顺序栈的实现——出栈 操作接口： T Pop( ); 时间复杂度？ template <class T,int MaxSize> T SeqStack<T, MaxSize>::Pop( ) { if (top==-1) {cerr<<"下溢"; exit(1);} x=data[top]; top--; return x; } 时间复杂度？

顺序栈的特殊形式——两栈共享空间 在一个程序中需要同时使用具有相同数据类型的两个栈，如何顺序存储这两个栈？ 解决方案1： 直接解决：为每个栈开辟一个数组空间。 会出现什么问题？如何解决？ 解决方案2：习题3.3 顺序栈单向延伸——使用一个数组来存储两个栈

顺序栈的特殊形式——两栈共享空间 两栈共享空间：使用一个数组来存储两个栈，让一个栈的栈底为该数组的始端，另一个栈的栈底为该数组的末端，两个栈从各自的端点向中间延伸。

顺序栈的特殊形式——两栈共享空间 a1 a2 … ai bj … … b2 b1 top1 top2 栈1的底固定在下标为0的一端； 0 1 2 … … S-1 a1 a2 … ai bj … … b2 b1 栈1底 top1 top2 栈2底 栈1的底固定在下标为0的一端； 栈2的底固定在下标为MaxSize-1的一端。 top1和top2分别为栈1和栈2的栈顶指针； MaxSize为整个数组空间的大小（图中用S表示）；

顺序栈的特殊形式——两栈共享空间 a1 a2 … ai bj … … b2 b1 top1 top1 top2 什么时候栈1为空？ 0 1 2 … … S-1 a1 a2 … ai bj … … b2 b1 top1 top1 top2 什么时候栈1为空？ top1= -1

顺序栈的特殊形式——两栈共享空间 a1 a2 … ai bj … … b2 b1 top1 top2 top2 top1= -1 0 1 2 … … S-1 a1 a2 … ai bj … … b2 b1 top1 top2 top2 什么时候栈1为空？ top1= -1 什么时候栈2为空？ top2= MaxSize

顺序栈的特殊形式——两栈共享空间 a1 a2 … … ai bj … … b2 b1 top1 top2 top1= -1 0 1 2 … … S-1 a1 a2 … … ai bj … … b2 b1 top1 top2 什么时候栈1为空？ top1= -1 什么时候栈2为空？ top2= MaxSize 什么时候栈满？ top2= top1+1

两栈共享空间类模板 template <class T, int MaxSize> class BothStack { public: BothStack( ); ~BothStack( ); void Push(int i, T x); T Pop(int i); T GetTop(int i); bool Empty(int i); private: T data[MaxSize]; int top1, top2; };

两栈共享空间的实现——插入 操作接口：void Push(int i, T x) ; 1. 如果栈满，则抛出上溢异常； 2. 判断是插在栈1还是栈2； 2.1 若在栈1插入，则 2.1.1 top1加1; 2.1.2 在top1处填入x； 2.2 若在栈2插入，则 2.2.1 top2减1; 2.2.2 在top2处填入x；

两栈共享空间的实现——删除 操作接口：T Pop(int i) ; 1. 若是在栈1删除，则 1.1 若栈1为空栈，抛出下溢异常； 1.2 删除并返回栈1的栈顶元素； 2. 若是在栈2删除，则 2.1 若栈2为空栈，抛出下溢异常； 2.2 删除并返回栈2的栈顶元素；

3.1.3 栈的链式存储与实现 如何改造链表实现栈的链接存储？ head a1 a2 an ai 将哪一端作为栈顶？ 3.1.3 栈的链式存储与实现 如何改造链表实现栈的链接存储？ head a1 a2 an ∧ ai 将哪一端作为栈顶？ 将链头作为栈顶，方便操作。 链栈需要加头结点吗？ 链栈不需要附设头结点。

3.1.3 栈的链式存储与实现 链栈：栈的链接存储结构 top a1 an-1 an top an an-1 a1 3.1.3 栈的链式存储与实现 链栈：栈的链接存储结构 top a1 an-1 an ∧ top an an-1 a1 ∧ 栈顶 栈顶 栈底 两种示意图在内存中对应同一种状态 栈底

链栈的类模板 template <class T> class LinkStack { Node<T> *top; //栈顶指针 public: LinkStack( ); //构造函数 ~LinkStack( ); //析构函数 void Push(T x); //入栈 T Pop( ); //出栈 T Top( ); //取栈顶元素（元素不出栈） bool Empty( ); //判断链栈是否为空栈 };

链栈的实现——入栈 操作接口： void Push(T x); 算法描述： x top s 为 什 top an 么 没 有 判 断 满 ？ 算法描述： template<class T> void LinkStack<T>::Push(T x) { s=new Node<T>; s->data = x; //申请一个数据域为x的结点s s->next = top; top=s; //将结点s插在栈顶 } top x s top an an-1 a1 ∧

链栈的实现——出栈 操作接口： T Pop( ); 算法描述： top an top an-1 a1 top++可以吗？ p ∧ template <class T> T LinkStack<T>::Pop( ) { if (top==NULL) {cerr<<"下溢"; exit(1);} x=top->data; //暂存栈顶元素 p=top; top=top->next; //删除栈顶结点 delete p; return x; } top an p top an-1 a1 ∧ top++可以吗？

顺序栈和链栈的比较 时间性能：相同，都是常数时间O(1)。 空间性能： 顺序栈：有元素个数的限制和空间浪费的问题。 链栈：没有栈满的问题，只有当内存没有可用空间时才会出现栈满，但是每个元素都需要一个指针域，从而产生了结构性开销。 总之，当栈的使用过程中元素个数变化较大时，用链栈是适宜的，反之，应该采用顺序栈。

3.1.4 栈的应用 栈的应用1——递归

3.1.4 栈的应用 栈的应用1——递归 德罗斯特效应（Droste effect）

3.1.4 栈的应用 栈的应用1——递归 哪些问题可以用递归解决 大问题可以分解为小问题 可以确定递归到何时终止

3.1.4 栈的应用 栈的应用1——递归 补充练习题 1.编写把十进制正整数转换为S进制(S=2，8，16)数输出的递归算法。 3.1.4 栈的应用 栈的应用1——递归 补充练习题 1.编写把十进制正整数转换为S进制(S=2，8，16)数输出的递归算法。 2.编写出计算Fib(n)的递归算法。并分析递归算法和非递归算法它们的时间复杂度和空间复杂度。 3.杨辉三角形的递归实现。 4．一个射击运动员打靶，靶一共有10环，连开10枪打中90环的可能性有多少种？试用递归算法实现。 【《程序员面试宝典》Ch8，电子工业出版社】 分析：本题可以通过10重循环实现，但这样的时间复杂度和空间复杂度无疑很高。比较好的方法是采用递归的方式。程序结果一共有92 378种可能。 5.编写一个递归算法，输出自然数1~n这n个数的全排列 6.编写GRAY码的递归算法。

3.1.4 栈的应用 栈的应用1——递归 递归与栈的关系 递归函数的内部执行过程 3.1.4 栈的应用 栈的应用1——递归 递归与栈的关系 递归函数的内部执行过程 ⑴ 运行开始时，首先为递归调用建立一个工作栈，其结构包括值参、局部变量和返回地址； ⑵ 每次执行递归调用之前，把递归函数的值参和局部变量的当前值以及调用后的返回地址压栈； ⑶ 每次递归调用结束后，将栈顶元素出栈，使相应的值参和局部变量恢复为调用前的值，然后转向返回地址指定的位置继续执行。

3.1.4 栈的应用 栈的应用2——中缀表达式求值 表达式求值是程序设计语言编译中的一个最基本问题。它的实现需要借助栈来完成。这里介绍一种简单直观，广为使用的算法，即“算符优先法”。 为实现算符优先算法，可以使用两个工作栈。 1.运算符OPTR栈, 用以寄存运算符； 2.操作数OPND栈, 用以寄存操作数或运算结果。

算法思想： 1）首先置操作数栈为空栈，表达式起始符“@”为运算符的栈底元素； 2）依次读入表达式中每个字符，若是操作数则进OPND栈，若是运算符，则与OPTR栈的栈顶运算符进行比较，作相应操作，直至整个表达式求值完毕（即OPTR栈的栈顶元素和当前读入的字符均为“@”）。

运算优先级 ＋ － × ／ ( ) @ > < = 当前运算符 栈顶运算符

3.1.4 栈的应用 栈的应用3——后缀表达式求值 中缀转后缀 后缀求值

问题的提出： 如何解决主机与外部设备之间速度不匹配的问题？ 主机输出数据给打印机打印，输出数据的速度比打印数据的速度要快得多，若直接把输出的数据送给打印机打印，由于速度不匹配，显然是不行的。 解决的方法是设置一个打印数据缓冲区，主机把要打印输出的数据依次写入到这个缓冲区中；打印机就从缓冲区中按照先进先出的原则依次取出数据并打印，打印完后再向主机发出请求，主机接到请求后再向缓冲区写入打印数据。 “打印数据缓冲区”——“队列”

09年考研试题 单选第1题 1.为解决计算机与打印机之间速度不匹配的问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是 A.栈 B.队列 C.树 D.图

3.2 特殊线性表——队列 3.2.1 队列的基本概念 队列的逻辑结构 a1 a2 a3 队列的操作特性： 先进先出 3.2 特殊线性表——队列 3.2.1 队列的基本概念 队列的逻辑结构 队列：只允许在一端进行插入操作，而另一端进行删除操作的线性表。 出队 入队 a1 a2 a3 队头 队尾 队列的操作特性： 先进先出

3.2.2 队列的顺序存储结构及实现（顺序队列） a1 a2 a3 a4 如何改造数组实现队列的顺序存储？ 3.2.2 队列的顺序存储结构及实现（顺序队列） 如何改造数组实现队列的顺序存储？ 例：a1a2a3a4依次入队，仿照顺序表n个元素存放在前n个单元中。 0 1 2 3 4 入队 出队 a1 a2 a3 a4 入队操作时间性能为O(1)

3.2.2 队列的顺序存储结构及实现（顺序队列） a1 a2 a3 a4 如何改造数组实现队列的顺序存储？ 例：a1a2依次出队 3.2.2 队列的顺序存储结构及实现（顺序队列） 如何改造数组实现队列的顺序存储？ 例：a1a2依次出队 0 1 2 3 4 入队 出队 a1 a2 a3 a4

3.2.2 队列的顺序存储结构及实现（顺序队列） a2 a3 a4 如何改造数组实现队列的顺序存储？ 例：a1a2依次出队 3.2.2 队列的顺序存储结构及实现（顺序队列） 如何改造数组实现队列的顺序存储？ 例：a1a2依次出队 0 1 2 3 4 入队 出队 a2 a3 a4

3.2.2 队列的顺序存储结构及实现（顺序队列） a3 a4 如何改造数组实现队列的顺序存储？ 例：a1a2依次出队 0 1 2 3 4 3.2.2 队列的顺序存储结构及实现（顺序队列） 如何改造数组实现队列的顺序存储？ 例：a1a2依次出队 0 1 2 3 4 入队 出队 a3 a4 出队操作时间性能为O(n)

3.2.2 队列的顺序存储结构及实现（顺序队列） 如何改进出队的时间性能？ 3.2.2 队列的顺序存储结构及实现（顺序队列） 如何改进出队的时间性能？ 放宽队列的所有元素必须存储在数组的前n个单元这一条件 ，只要求队列的元素存储在数组中连续的位置。 设置队头、队尾两个指示

3.2.2 队列的顺序存储结构及实现（顺序队列） a1 例：a1a2a3a4依次入队 0 1 2 3 4 front rear rear 3.2.2 队列的顺序存储结构及实现（顺序队列） 例：a1a2a3a4依次入队 0 1 2 3 4 入队 出队 a1 front rear rear 入队操作时间性能为O(1)

3.2.2 队列的顺序存储结构及实现（顺序队列） a1 a2 例：a1a2a3a4依次入队 0 1 2 3 4 front rear 3.2.2 队列的顺序存储结构及实现（顺序队列） 例：a1a2a3a4依次入队 0 1 2 3 4 入队 出队 a1 a2 front rear 入队操作时间性能仍为O(1)

3.2.2 队列的顺序存储结构及实现（顺序队列） a1 a2 a3 例：a1a2a3a4依次入队 0 1 2 3 4 front rear 3.2.2 队列的顺序存储结构及实现（顺序队列） 例：a1a2a3a4依次入队 0 1 2 3 4 入队 出队 a1 a2 a3 front rear 入队操作时间性能仍为O(1)

3.2.2 队列的顺序存储结构及实现（顺序队列） a1 a2 a3 a4 例：a1a2a3a4依次入队 0 1 2 3 4 front 3.2.2 队列的顺序存储结构及实现（顺序队列） 例：a1a2a3a4依次入队 0 1 2 3 4 入队 出队 a1 a2 a3 a4 front rear 入队操作时间性能仍为O(1)

3.2.2 队列的顺序存储结构及实现（顺序队列） a1 a2 a3 a4 例：a1a2依次出队 0 1 2 3 4 front rear 3.2.2 队列的顺序存储结构及实现（顺序队列） 例：a1a2依次出队 0 1 2 3 4 入队 出队 a1 a2 a3 a4 front rear

3.2.2 队列的顺序存储结构及实现（顺序队列） a1 a2 a3 a4 例：a1a2依次出队 0 1 2 3 4 front rear 3.2.2 队列的顺序存储结构及实现（顺序队列） 例：a1a2依次出队 0 1 2 3 4 入队 出队 a1 a2 a3 a4 front rear 出队操作时间性能提高为O(1)

3.2.2 队列的顺序存储结构及实现（顺序队列） a1 a2 a3 a4 例：a1a2依次出队 0 1 2 3 4 front rear 3.2.2 队列的顺序存储结构及实现（顺序队列） 例：a1a2依次出队 0 1 2 3 4 入队 出队 a1 a2 a3 a4 front rear 出队操作时间性能提高为O(1)

3.2.2 队列的顺序存储结构及实现（顺序队列） 例：a1a2依次出队 0 1 2 3 4 入队 出队 a3 a4 front rear

3.2.2 队列的顺序存储结构及实现（顺序队列） a3 a4 a5 继续入队会出现什么情况？ 0 1 2 3 4 front rear 3.2.2 队列的顺序存储结构及实现（顺序队列） 继续入队会出现什么情况？ 0 1 2 3 4 入队 出队 a3 a4 a5 front rear rear 假溢出：当元素被插入到数组中下标最大的位置上之后，队列的空间就用尽了，尽管此时数组的低端还有空闲空间，这种现象叫做假溢出。

3.2.2 队列的顺序存储结构及实现（顺序队列） a6 a3 a4 a5 如何解决假溢出？ 0 1 2 3 4 rear front 3.2.2 队列的顺序存储结构及实现（顺序队列） 如何解决假溢出？ 0 1 2 3 4 出队 入队 a6 a3 a4 a5 rear front rear 循环队列：将存储队列的数组头尾相接。

3.2.2 队列的顺序存储结构及实现（顺序队列） a6 a3 a4 a5 如何实现循环队列？ 0 1 2 3 4 rear front 3.2.2 队列的顺序存储结构及实现（顺序队列） 如何实现循环队列？ 0 1 2 3 4 出队 入队 a6 a3 a4 a5 rear front 不存在物理的循环结构，但可用软件方法实现。 求模：（4＋1）mod 5＝0

3.2.2 队列的顺序存储结构及实现（顺序队列） a3 如何判断循环队列队空？ 队空的临界状态 0 1 2 3 4 front rear 3.2.2 队列的顺序存储结构及实现（顺序队列） 如何判断循环队列队空？ 队空的临界状态 0 1 2 3 4 出队 入队 a3 front rear

3.2.2 队列的顺序存储结构及实现（顺序队列） a3 如何判断循环队列队空？ 执行出队操作 0 1 2 3 4 front rear 出队 3.2.2 队列的顺序存储结构及实现（顺序队列） 如何判断循环队列队空？ 执行出队操作 0 1 2 3 4 出队 入队 a3 front rear

3.2.2 队列的顺序存储结构及实现（顺序队列） a3 如何判断循环队列队空？ 执行出队操作 0 1 2 3 4 front rear 3.2.2 队列的顺序存储结构及实现（顺序队列） 如何判断循环队列队空？ 执行出队操作 0 1 2 3 4 出队 入队 a3 front rear 队空：front=rear

3.2.2 队列的顺序存储结构及实现（顺序队列） a6 a3 a4 a5 如何判断循环队列队满？ 队满的临界状态 0 1 2 3 4 3.2.2 队列的顺序存储结构及实现（顺序队列） 如何判断循环队列队满？ 队满的临界状态 0 1 2 3 4 出队 入队 a6 a3 a4 a5 rear front

3.2.2 队列的顺序存储结构及实现（顺序队列） a6 a3 a4 a5 如何判断循环队列队满？ 执行入队操作 0 1 2 3 4 rear 3.2.2 队列的顺序存储结构及实现（顺序队列） 如何判断循环队列队满？ 执行入队操作 0 1 2 3 4 出队 入队 a6 a3 a4 a5 rear front

3.2.2 队列的顺序存储结构及实现（顺序队列） a6 a7 a3 a4 a5 如何判断循环队列队满？ 执行入队操作 0 1 2 3 4 3.2.2 队列的顺序存储结构及实现（顺序队列） 如何判断循环队列队满？ 执行入队操作 0 1 2 3 4 出队 入队 a6 a7 a3 a4 a5 rear front 队满：front=rear

3.2.2 队列的顺序存储结构及实现（顺序队列） a3 a4 a5 a6 队空、队满的判定条件出现二义性。 如何将队空和队满的判定条件分开？ 3.2.2 队列的顺序存储结构及实现（顺序队列） 队空、队满的判定条件出现二义性。 如何将队空和队满的判定条件分开？ 方法一：修改队满条件，浪费一个元素空间，队满时数组中还有一个空闲单元； 0 1 2 3 4 入队 出队 a3 a4 front a5 rear a6

3.2.2 队列的顺序存储结构及实现（顺序队列） 队空、队满的判定条件出现二义性。 如何将队空和队满的判定条件分开？ 3.2.2 队列的顺序存储结构及实现（顺序队列） 队空、队满的判定条件出现二义性。 如何将队空和队满的判定条件分开？ 方法一：浪费一个元素空间。将图3-8（c）所示的情况视为队满，此时的状态是，队尾指针加1就会从后面赶上队头指针，此时队满的条件是(rear+1) % MaxSize==front，这样就能与空队区别开。 方法二：设置一个布尔变量flag。当flag==flase时为空，当flag==true时为满。 方法三：使用一个计数器记录队列中元素的个数。附设一个存储队列中元素个数的变量如num，当num==0时队空，当num==MaxSize时队满。

循环队列(顺序)的类模板 template <class T, int MaxSize > //定义类模板SeqQueue class SeqQueue { T data[MaxSize]; //存放队列元素的数组 int front, rear; //队头和队尾指针 public: SeqQueue( ); //构造函数，置空队 void EnQueue(T x); //将元素x入队 T DeQueue( ); //将队头元素出队 T GetQueue( ); //取队头元素（并不删除） bool Empty( ); //判断队列是否为空 };

3.2.3 队列的链式存储结构及实现 （链队列） 链队列：队列的链接存储结构 如何改造单链表实现队列的链接存储？ head a1 a2 an ∧ front rear 队头指针即为链表的头指针

3.2.3 队列的链式存储结构及实现 （链队列） 非空链队列 front a1 a2 an ∧ rear 空链队列 front ∧ rear

链队列的类模板 template <class T> class LinkQueue { public: void EnQueue(T x); //将元素x入队 T DeQueue( ); //将队头元素出队 T GetQueue( ); //取链队列的队头元素 bool Empty( ); //判断链队列是否为空 private: Node<T> *front, *rear; //队头和队尾指针，分别指向头结点和终端结点 };

队列的链式实现 构造函数： LinkQueue( ); 算法描述： template <class T> front LinkQueue::LinkQueue( ) { s=new Node<T>; s->next=NULL; front=rear=s; } front ∧ rear

队列的链式实现 入队： void EnQueue(T x); front a1 an x s rear rear 算法描述： ∧ x s ∧ rear rear 有了头结点两种情况下的处理是一致的。 算法描述： s->next=NULL; rear->next=s; rear=s; front ∧ x s ∧ rear rear

队列的链式实现——入队 template <class T> void LinkQueue::EnQueue(T x) { s=new Node<T>; s->data=x; s->next=NULL; rear->next=s; rear=s; }

队列的链式实现——出队 p front a1 a2 an rear 算法描述： p=front->next; ∧ rear 算法描述： p=front->next; front->next=p->next;

队列的链式实现——出队 p front a1 a2 an rear 考虑边界情况：队列中只有一个元素？ 如何判断边界情况？ p ∧ rear 考虑边界情况：队列中只有一个元素？ 如何判断边界情况？ p 仅1个元素的队列判断： if (p->next==NULL) rear=front; front ∧ a1 ∧ rear rear

队列的链式实现——出队 template <class T> T LinkQueue::DeQueue( ) { if (rear==front) {cerr<<"下溢"; exit(1);} p=front->next; x=p->data; front->next=p->next; if (p->next==NULL) rear=front; //修改队尾指针 delete p; return x; }

循环队列和链队列的比较 时间性能: 空间性能: 循环队列和链队列的基本操作都需要常数时间O(1)。 循环队列：必须预先确定一个固定的长度，所以有存储元素个数的限制和空间浪费的问题。 链队列：没有队列满的问题，只有当内存没有可用空间时才会出现队列满，但是每个元素都需要一个指针域，从而产生了结构性开销。

课后练习 3.6、3.7、3.8题。