狠狠撸

第 4 章栈和队列
? 4.1 栈
? 4.2 队列
? 4.3 优先队列
? 4.4 递归算法

目的和要求
? 目的：使用栈或队列作为求解复杂应用问题的
有效手段和措施。
? 内容：栈和队列抽象数据类型及它们的实现和
应用；优先队列；递归算法设计。
? 要求：掌握栈和队列抽象数据类型，以及顺序
和链式存储结构实现；理解对于怎样的应用问
题，需要使用栈或队列，以及怎样使用。
? 重点：栈和队列的设计和实现；理解递归定义
，设计递归算法。
? 难点：使用栈或队列求解复杂应用问题；递归
算法设计。
? 实验：栈和队列及其应用；递归算法。

《数据结构（ Java 版）（第 3 版）》
4.1 栈
4.1.1 栈抽象数据类型
4.1.2 顺序栈
4.1.3 链式栈
4.1.4 栈的应用

4.1.1 栈抽象数据类
型
栈（ stack ）是一种特殊的线性表，其插入和删
除操作只允许在线性表的一端进行。
public interface SStack<T>
{ // 栈接口，栈抽象数据类
型
boolean isEmpty(); // 判断是否空栈
void push(T x); // 元素 x 入栈
T pop(); // 出栈，返回当前栈
顶元素
T get(); // 取栈顶元素，未出
栈
}

4.1.2 顺序栈
public class SeqStack<T> implements
SStack<T> // 顺序栈类，实现栈
接口
{
Object element[]; // 存储栈数据元素的数
组

4.1.3 链式
栈
public class LinkedStack<T> implements SStack<T>
{
private Node<T> top;
}

4.1.4 栈的应用
1. 栈是嵌套调用机制的实现基础
2. 使用栈以非递归方式实现递归算法

例 4.1 判断表达式中圆括号是否
匹配

例 4.2 使用栈计算表达式的
值。
中缀表达式 1+2*(3-4)+5

（ 1 ）将中缀表达式转换为后缀表
达式

（ 2 ）后缀表达式求值

4.2 队列
4.2.1 队列抽象数据类型
4.2.2 顺序队列
4.2.3 链式队列
4.2.4 队列的应用

4.2.1 队列抽象数据类型
队列（ queue ）是一种特殊的线性表，其插入和
删除操作分别在线性表的两端进行。
public interface QQueue<T> // 队列接口
{
boolean isEmpty(); // 判断队列是否为
空
void enqueue(T x); // 入队
T dequeue(); // 出队

4.2.2 顺序队
列
1. 顺序队列，假溢出

2. 顺序循环队列
front=(front+1) % length;
rear=(rear+1) % length;

3. 顺序循环队列类
public class SeqQueue<T> implements
QQueue<T>
{
private Object value[];
private int front,rear; // 队
列头尾下标
}

4.2.3 链式队列
public class LinkedQueue<T> implements
QQueue<T> // 链式队列类
{ private Node<T> front, rear;
}

4.2.4 队列的应用
例 4.3 求解素数环问题。

4.3 优先队列
1. 优先队列及其存储结构
2. 优先队列类
public class PriorityQueue<T extends
Comparable<T>>
implements QQueue<T>
例 4.4 进程按优先级调度管理。

1. 递归定义
2. 递归算法
f(n)=n×f(n-1)
【例 4.5 】求 n ！。
4.4 递归算法
1 0,1
!
( 1)! ??2
n
n
n n n
=?
= ?
× ??

【例 4.6 】求 Fibonacci 序列
。
0,1
( )
( 1) ( 2) ??2
n n
f n
f n f n n
=?
= ?
? + ??

例 4.7 打印数字塔
public static void line(int i)
{
if (i<10)
line(i+1);
System.out.print(String.format("%3d",
i));
}

3. 单链表的递归算法
public String toString()
{ return "(" + this.toString(this.head) + ")";
}
public String toString(Node<T> p) // 递归算法
{ if (p==null)
return "";
return p.data.toString() + ", "
+ this.toString(p.next);
}

实验 4 栈和队列以及递归
算法
1. 走迷宫
2. 骑士游历

狠狠撸

第04章栈和队列(java版)

Recommended

More Related Content

Similar to 第04章栈和队列(java版) (20)

More from Yan Li (6)

第04章栈和队列(java版)

狠狠撸

第04章 栈和队列(java版)

Recommended

More Related Content

Similar to 第04章 栈和队列(java版) (20)

More from Yan Li (6)

第04章 栈和队列(java版)

第04章栈和队列(java版)

Similar to 第04章栈和队列(java版) (20)

第04章栈和队列(java版)