算法(第四版) 1.3 背包、队列和栈

1.3 背包、队列和栈

背包（Bag）、队列（Queue）和栈（Stack），它们的不同之处在于删除和访问的顺序不同。

• 我们对集合对象的表示形式将直接影响各种操作的效率。
• 泛型和迭代
• 链式数据结构的重要性，特别是经典数据结构链表，可以高效地实现背包、队列和栈。

1.3.1 API

集合型的抽象数据类型的讨论将从定义它们的API开始。

每份API都含有一个无参构造函数、一个向集合中添加单个元素的方法、一个测试集合是否为空的方法和一个返回集合大小的方法。

泛型可迭代的基础集合数据类型的API

背包

public class Bag implements Iterable
	Bag()	创建一个空背包
void	add(Item item)	添加一个元素
boolean	isEmpty()	背包是否为空
int	size()	背包中的元素数量

先进先出（FIFO）队列

public class Queue implements Iterable
	Queue()	创建一个空队列
void	enqueue(Item item)	添加一个元素
Item	dequeue()	删除最早添加的元素
int	size()	背包中元素的数量

下压（后进先出，LIFO）栈

public class Stack implements Iterable
	Stack()	创建一个空栈
void	push(Item item)	添加一个元素
Item	pop()	删除最近添加的元素
boolean	isEmpty()	栈是否为空
int	size()	栈中元素数量

泛型

在每份API中，类名后的<Item>记号将Item定义为一个类型参数，它是一个象征性的占位符，表示的是用例将会使用的某种具体数据类型。可以将Stack<Item>理解为某种元素的栈。

自动装箱

类型参数必须被实例化为引用类型。在处理赋值语句、方法的参数和算术或逻辑表达式时，Java会自动在引用类型和对应的原始数据类型之间进行转换。这种转换有助于我们同时使用泛型和原始数据类型。

可迭代的集合类型

对于许多应用场景，用力的要求只是用某种方式处理集合中的每个元素，或者叫做迭代访问集合中的所有元素。这种模式非常重要，在Java中和其他许多语言中它都是一级语言特性（不只是库，编程语言本身就含有特殊的机制来支持它）。

背包

背包是一种不支持从中删除元素的集合数据类型——它的目的就是帮助用例收集元素并迭代遍历所有的元素（用例也可以检查背包是否为空或者获取背包中元素的数量）。迭代的顺序不确定且与用例无关。

先进先出队列

在应用程序中使用队列的主要原因是在用集合保存元素的同时保存他们的相对顺序：使它们入列顺序和出列顺序相同。

下压栈

下压栈（或简称栈）是一种基于后进先出（LIFO）策略的集合类型。

生活中的用例：收邮件的邮箱、浏览器中的“后退”按钮

在应用程序中使用栈迭代器的一个典型原因是在用集合保存元素的同时颠倒他们的相对顺序。

算术表达式求值

如何才能得到一个（由字符串表示的）算术表达式的值呢？E.W.Dijkstra在20世纪60年代发明了一个非常简单的算法，用两个栈（一个用于保存运算符，一个用于保存操作数）完成了这个任务。

表达式由括号、运算符和操作数（数字）组成。我们根据以下4种情况从左到右逐个将这些实体送入栈中处理。

• 将操作数压入操作数栈；
• 将运算符压入运算符栈；
• 忽略左括号；
• 在遇到右括号时，弹出一个运算符，弹出所需数量的操作数，并将运算符和操作数的运算结果压入操作数栈中。

/**
 * Dijkstra的双栈算术表达式求值算法
 * @author Dell
 *
 */
public class Evaluate {

	public static void main(String[] args) {
		Stack<String> ops = new Stack<String>();
		Stack<Double> vals = new Stack<Double>();
		
		while (!StdIn.isEmpty()) {
			// 读取字符，如果是运算符则压入栈
			String s = StdIn.readString();
			if (s.equals("(")) {
				// do nothing
			}else if (s.equals("+")) {
				ops.push(s);
			}else if (s.equals("-")) {
				ops.push(s);
			}else if (s.equals("*")) {
				ops.push(s);
			}else if (s.equals("/")) {
				ops.push(s);
			}else if (s.equals("sqrt")) {
				ops.push(s);
			}else if (s.equals(")")) {
				// 如果字符串为")"，弹出运算符和操作数，计算结果并压入栈
				String op = ops.pop();
				Double v = vals.pop();
				if (op.equals("+")) {
					v = vals.pop() + v;
				}else if (op.equals("-")) {
					v = vals.pop() - v;
				}else if (op.equals("*")) {
					v = vals.pop() * v;
				}else if (op.equals("/")) {
					v = vals.pop() / v;
				}else if (op.equals("sqrt")) {
					v = Math.sqrt(v);
				}
				vals.push(v);
			}// 如果字符既非运算符也不是括号，将它作为double值压入栈
			else {
				vals.push(Double.parseDouble(s));
			}
		}
		StdOut.println(vals.pop());
	}
}

D:Softeclipse_rcp_workplacealgorithms4src>java chapter01.Evaluate
( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) )
^Z
101.0

D:Softeclipse_rcp_workplacealgorithms4src>java chapter01.Evaluate
( ( 1 + sqrt ( 5.0 ) ) / 2.0 )
^Z
1.618033988749895

这段Stack用例使用了两个栈来计算表达式的值。它展示了一种重要的计算模型：将一个字符串解释为一段程序并执行该程序得到的结果。

简单起见，这段代码假设表达式没有省略任何括号，数字和字符均以空白字符相隔。

1.3.2 集合类数据类型的实现

（热身）定容栈

只能处理String值，它要求用例指定一个容量且不支持迭代。

public class FixedCapacityStackOfStrings
	FixedCapacityStackOfStrings(int cap)	创建一个容量为cap的空栈
void	push(String item)	添加一个字符串
String	pop()	删除最近添加的字符串
boolean	isEmpty()	栈是否为空
int	size()	栈中字符串的数量

数据类型的实现

public class FixedCapacityStackOfStrings {

	private String[] a; // stack entries
	private int N;		// size
	public FixedCapacityStackOfStrings(int cap) {
		a = new String[cap];
	}
	public boolean isEmpty() {
		return N == 0;
	}
	public int size() {
		return N;
	}
	public void push(String item) {
		a[N++] = item;
	}
	public String pop() {
		return a[--N];
	}
}

测试用例

public static void main(String[] args) {
		FixedCapacityStackOfStrings s;
		s = new FixedCapacityStackOfStrings(100);
		while (!StdIn.isEmpty()) {
			String item = StdIn.readString();
			if (!item.equals("-")) {
				s.push(item);
			}else if (!s.isEmpty()) {
				StdOut.print(s.pop() + " ");
			}
		}
		StdOut.println("(" + s.size() + " left on stack)");
	}

使用方法

D:Softeclipse_rcp_workplacealgorithms4src>more tobe.txt
to be or not to - be - - that - - - is

D:Softeclipse_rcp_workplacealgorithms4src>java chapter01.FixedCapacityStackOfStrings < tobe.txt
to be not that or be (2 left on stack)

这种实现的主要特点是push和pop操作所需的时间独立于栈的长度。

泛型

FixedCapacityStackOfStrings只能处理String对象，这是它的第一个缺点。

一种表示泛型定容栈的抽象数据类型

public class FixedCapacityStack
	FixedCapacityStack(int cap)	创建一个容量为cap的空栈
void	push(Item item)	添加一个元素
Item	pop()	删除最近添加的元素
boolean	isEmpty()	栈是否为空
int	size()	栈中元素的数量

测试用例

public static void main(String[] args) {
		FixedCapacityStack s;
		s = new FixedCapacityStack(100);
		while (!StdIn.isEmpty()) {
			String item = StdIn.readString();
			if (!item.equals("-")) {
				s.push(item);
			}else if (!s.isEmpty()) {
				StdOut.print(s.pop() + " ");
			}
		}
		StdOut.println("(" + s.size() + " left on stack)");
	}

使用方法

D:Softeclipse_rcp_workplacealgorithms4src>more tobe.txt
to be or not to - be - - that - - - is
    
D:Softeclipse_rcp_workplacealgorithms4src>java chapter01.FixedCapacityStack < tobe.txt
to be not that or be (2 left on stack)

数据类型的实现

public class FixedCapacityStack<Item> {

	private Item[] a; // stack entries
	private int N;		// size
	public FixedCapacityStack(int cap) {
		a = (Item[])(new Object[cap]);
	}
	public boolean isEmpty() {
		return N == 0;
	}
	public int size() {
		return N;
	}
	public void push(Item item) {
		a[N++] = item;
	}
	public Item pop() {
		return a[--N];
	}
}

调整数组大小

选择用数组表示栈内容意为着用例必须预先估计栈的最大容量。

push()方法需要在代码中检测栈是否已满，我们的API中也应该含有一个isFull()方法来允许用例检测栈是否已满。但我们省略了它的实现代码，因为我们希望用例从处理栈已满的问题中解脱出来。

我们修改了数组的实现，动态调整数组a[]的大小,使得它既足以保存所有元素，有不至于浪费过多的空间。

public void resize(int max) {
    // 将大小为N < = max 的栈移动到一个新的大小为max的数组中
    Item[] temp = (Item[]) new Object[max];
    for (int i = 0; i < N; i++) {
        temp[i] = a[i];
    }
    a = temp;
}

public void push(Item item) {
    // 将元素压入栈顶
    if (N == a.length) {
        resize(2 * a.length);
    }
    a[N++] = item;
}

Tip：数组的length是固定不变的，而栈的大小N是动态变化的。

public Item pop() {
    // 从栈顶删除元素
    Item item = a[--N];
    a[N] = null;	// 避免对象游离
    if (N > 0 && N == a.length / 4) {
        resize(a.length / 2);
    }
    return a[--N];
}

对象游离

Java的垃圾手机策略是回收所有无法被访问的对象的内存。在我们对pop()方法的实现中，被弹出的元素的引用依然存在于数组中。这个元素实际上已经是一个孤儿了——它永远不会再被访问到了，但Java的垃圾收集器没法知道这一点，除非该引用被覆盖掉。即使用例已经不再需要这个元素了，数组中的引用仍然可以让它继续存在。这种情况（保存一个不需要的对象的引用）称为游离。在这里，避免对象游离很容易，只需将被弹出的数组元素的值设为null即可。

迭代

集合类数据类型的基本操作之一就是，能够使用Java的foreach语句用过迭代遍历并处理集合中的每个元素。

在任意可迭代的集合数据类型中我们需要实现的东西：

• 集合数据类型必须实现一个iterator()方法并返回一个Iterator对象。
• Iterator类必须包含两个方法：hasNext()（返回一个布尔值）和next()（返回集合中的一个泛型元素）。

在Java中，要使一个类可迭代，第一步就是在它的声明中加入implements Iterable<Item>接口。然后在类中添加一个方法iterator()返回一个迭代器Iterator<Item>。

而迭代器我们可以在集合类数据类型中建立嵌套类的方式来完成。

private class ReverseArrayIterator implements Iterator<Item>
{
    private int i = N;
    public boolean hasNext(){ return i > 0  }
    public Item next()      { return a[--i] }
    public void remove()    {               }
}

/**
 * 下压（LIFO）栈 （能够动态调整数组大小的实现）
 * @author Dell
 *
 * @param <Item>
 */
public class ResizingArrayStack<Item> implements Iterable<Item>{

	private Item[] a = (Item[])new Object[1]; 	// stack entries  	栈元素
	private int N = 0;							// size				栈数量
	public boolean isEmpty() {
		return N == 0;
	}
	public int size() {
		return N;
	}
	public void resize(int max) {
		// 将大小为N < = max 的栈移动到一个新的大小为max的数组中
		Item[] temp = (Item[]) new Object[max];
		for (int i = 0; i < N; i++) {
			temp[i] = a[i];
		}
		a = temp;
	}
	public void push(Item item) {
		// 将元素压入栈顶
		if (N == a.length) {
			resize(2 * a.length);
		}
		a[N++] = item;
	}
	public Item pop() {
		// 从栈顶删除元素
		Item item = a[--N];
		a[N] = null;	// 避免对象游离
		if (N > 0 && N == a.length / 4) {
			resize(a.length / 2);
		}
		return a[--N];
	}
	
	@Override
	public Iterator<Item> iterator() {
		return new ReverserArrayIterator();
	}
	
	private class ReverserArrayIterator implements Iterator<Item>{

		private int i = N;
		
		@Override
		public boolean hasNext() {
			return i > 0;
		}

		@Override
		public Item next() {
			return a[--i];
		}
	}
}

1.3.3 链表

定义：链表是一种递归的数据结构，它或者为空（null），或者是指向一个节点（node）的引用，该节点含有一个泛型的元素或者一个指向另一个链表的引用。

节点记录

用一个嵌套类来定义一个嵌套类来定义节点的抽象数据类型。

private class Node
{
    Item item;
    Node next;
}

构造链表

// 要构造一条含有元素to、be和or的链表，我们首先为每个元素创造一个结点：
Node first = new Node();
Node second = new Node();
Node third = new Node();

// 并为每个结点的item域设为所需的值
first.item = "to";
second.item = "be";
third.item = "or";

// 让后设置next域来构造链表
first.next = second;
second.next = third;

链表表示的是一列元素。

fisrt表示的序列是to、be、or。

在表头插入结点

// 保存指向链表的连接
Node oldfirst = first;
// 创建新的首节点
first = new Node();
// 设置新结点中的实例变量
first.item = "not";
first.next = oldfirst;

在表头删除结点

first = first.next;

在表尾插入结点

// 保存指向表尾结点的链接
Node oldlast = last;
// 创建新的尾结点
last = new Node();
last.item = "not";
// 将尾链接指向新结点
oldlast.next = last;

在其他位置的插入和删除操作

我们已经可以通过first链接访问链表的首节点并通过last链接访问链表的尾结点：

• 在表头插入结点
• 在表头删除结点
• 在表尾插入结点

其他操作，如下就不容易实现了：

• 删除指定结点
• 在指定结点前插入一个新结点

例如，我们怎么删除链表的尾结点呢？last链接帮不上忙，因为我们需要将链表结点的前一个结点中的链接（它的指向正好是last）值改为null。在缺少其他信息的情况下，唯一的解决方法是遍历整个链表并找出指向last的结点。这种解决方案并不是我们想要的，因为它所需的时间与链表的长度成正比。实现任意插入和删除操作的标准解决方案是使用双向链表，其中每个结点都含有两个链接，分别指向不同的方向。

遍历

链表的遍历：

for (Node x = first; x != null; x = x.next)
{
    // 处理x.item
}

栈的实现

Stack的测试用例

public static void main(String[] args) {
    // 创建一个栈并根据StdIn中的指示压入或弹出字符串
    Stack<String> s = new Stack<String>();

    while (!StdIn.isEmpty()) {
        String item = StdIn.readString();
        if (!item.equals("-")) {
            s.push(item);
        }else if (!s.isEmpty()) {
            StdOut.print(s.pop() + " ");
        }
    }
    StdOut.println("(" + s.size() + " left on stack)");
}

D:Softeclipse_rcp_workplacealgorithms4src>more tobe.txt
to be or not to - be - - that - - - is

D:Softeclipse_rcp_workplacealgorithms4src>java chapter01.Stack < tobe.txt
to be not that or be (2 left on stack)

下压堆栈（链表实现）

/**
 * 下压堆栈 （链表实现）
 * @author Dell
 *
 * @param <Item>
 */
public class Stack<Item> implements Iterable<Item>{
	
	private Node first;		// 栈顶 （最近添加的元素）
	private int N;			// 元素的数量
	private class Node{
		// 定义了节点的嵌套类
		Item item;
		Node next;
	}
	
	public boolean isEmpty() {
		return first == null;	// 或：N == 0
	}
	
	public int size() {
		return N;
	}
	
	public void push(Item item) {
		// 向栈顶添加元素
		Node oldfirst = first;
		first = new Node();
		first.item = item;
		first.next = oldfirst;
		N++;
	}
	
	public Item pop() {
		// 从栈顶删除元素
		Item item = first.item;
		first = first.next;
		N--;
		return item;
	}
	
	@Override
	public Iterator<Item> iterator() {
		// 实现见算法1.4
		return null;
	}
}

队列的实现

Queue的测试用例

public static void main(String[] args) {
    // 创建一个队列并操作字符串入列或出列
    Queue<String> q = new Queue<String>();

    while (!StdIn.isEmpty()) {
        String item = StdIn.readString();
        if (!item.equals("-")) {
            q.enqueue(item);
        }else if (!q.isEmpty()) {
            StdOut.print(q.dequeue() + " ");
        }
    }
    StdOut.println("(" + q.size() + " ledt on queue)");
}

D:Softeclipse_rcp_workplacealgorithms4src>more tobe.txt
to be or not to - be - - that - - - is

D:Softeclipse_rcp_workplacealgorithms4src>java chapter01.Queue < tobe.txt
to be or not to be (2 ledt on queue)

先进先出队列

/**
 * 先进先出队列  （链表实现）
 * @author Dell
 *
 * @param <Item>
 */
public class Queue<Item> implements Iterable<Item> {
	
	private Node first;		// 指向最早添加的结点的链接
	private Node last;		// 指向最近添加的结点的链接
	private int N;			// 队列中的元素数量
	private class Node{
		// 定义了节点的嵌套类
		Item item;
		Node next;
	}
	
	public boolean isEmpty() {
		return first == null;	// 或：N == 0
	}
	
	public int size() {
		return N;
	}

	public void enqueue(Item item) {
		// 向表尾添加元素
		Node oldlast = last;
		last = new Node();
		last.item = item;
		last.next = null;
		if (isEmpty()) {
			first = last;
		}else {
			oldlast.next = last;
		}
		N++;
	}
	
	public Item dequeue() {
		// 从表头删除元素
		Item item = first.item;
		first = first.next;
		if (isEmpty()) {
			last = null;
		}
		N--;
		return item;
	}
	
	
	@Override
	public Iterator<Item> iterator() {
		// 实现见算法1.4
		return null;
	}
}

背包的实现

用链表数据结构实现我们的Bag API只需要将Stack中的push()改名为add()，并去掉pop()的实现即可

/**
 * 背包的实现 （链表实现）
 * @author Dell
 *
 * @param <Item>
 */
public class Bag<Item> implements Iterable<Item>{
	
	private Node first;		// 栈顶 （最近添加的元素）
	private class Node{
		// 定义了节点的嵌套类
		Item item;
		Node next;
	}
	
	public boolean isEmpty() {
		return first == null;	// 或：N == 0
	}
	
	public void add(Item item) {
		// 向栈顶添加元素
		Node oldfirst = first;
		first = new Node();
		first.item = item;
		first.next = oldfirst;
	}
	
	@Override
	public Iterator<Item> iterator() {
		return new ListIterator();
	}
	
	private class ListIterator implements Iterator<Item>{
		
		private Node current = first;

		@Override
		public boolean hasNext() {
			return current != null;
		}
		
		@Override
		public void remove() {
		}

		@Override
		public Item next() {
			Item item = current.item;
			current = current.next;
			return item;
		}
	}
}

1.3.4 综述

在本节中，我们所学习的支持泛型和迭代的背包、队列和栈的实现所提供的抽象使我们能够编写简洁的用例程序来操作对象的集合。深入理解这些抽象数据类型非常重要，这是我们研究算法和数据结构的开始。

原因有三：

• 第一，我们将以这些数据类型为基石构造本书中的其他更高级的数据结构。
• 第二，它们展示了数据结构和算法的关系以及同时满足多个有可能相互冲突的性能目标时所要面对的挑战。
• 第三，我们将要学习若干算法的实现重点就是需要其中的抽象数据类型能够支持对对象集合的强大操作，这些实现是我们的起点。