背包、队列和栈的实现（基于链表）

下面介绍背包、队列和栈（基于链表）的实现，是对《算法（第四版）》1.3 节的部分总结。

首先，应该知道链表及链表的基本操作，在 中做了总结，下面主要是给出具体的实现代码。

栈的实现

算法 1 将栈保存为一条链表，栈的顶部即为表头，实例变量 first 指向栈顶。

import java.util.Iterator;
import java.util.Scanner;
public class Stack implements Iterable
{
	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;
	}
	public Iterator iterator() { return new StackIterator(); }
	private class StackIterator implements Iterator {
		private Node current = first;
		public boolean hasNext() { return current != null; }
		public Item next() {
			Item item = current.item;
			current = current.next;
			return item;
		}
	}
	public static void main(String[] args) {
		Stack stack = new Stack();
		Scanner scanner = new Scanner(System.in);
		while (scanner.hasNext()) {
			String item = scanner.next();
			if (!item.equals("-")) stack.push(item);
			else if (!stack.isEmpty()) System.out.print(stack.pop() + " ");
		}
		System.out.println("(" + stack.size() + " left on stack)");
		scanner.close();
	}
}

图 2 显示了图 1 中测试的轨迹。

队列的实现

算法 2 将队列表示为一条从最早插入的元素到最近插入的元素的链表，实例变量 first 指向队列的开头，实例变量 last 指向队列的结尾。

import java.util.Iterator;
import java.util.Scanner;
public class Queue implements Iterable
{
	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;
	}
	public Iterator iterator() { return new QueueIterator(first); }
	private class QueueIterator implements Iterator {
		private Node current;
		public QueueIterator(Node first) { current = first; }
		public boolean hasNext() { return current != null; }
		public Item next() {
			if (!hasNext()) return null;
			Item item = current.item;
			current = current.next;
			return item;
		}
	}
	public static void main(String[] args) {
		Queue queue = new Queue();
		Scanner scanner = new Scanner(System.in);
		while (scanner.hasNext()) {
			String item =scanner.next();
			if (!item.equals("-"))
				queue.enqueue(item);
			else if (!queue.isEmpty())
				System.out.print(queue.dequeue() + " ");
		}
		System.out.println("(" + queue.size() + " left on queue)");
		scanner.close();
	}
}

图 4 显示了图 3 中测试的轨迹。

背包的实现

用链表数据结构实现我们的 Bag API 只需要将 Stack 中的 push() 改名为 add()，并去掉 pop() 的实现即可，如算法 1.4 所示（也可以用相同的方法实现 Queue，但需要的代码更多）。

import java.util.Iterator;
public class Bag implements Iterable
{
	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 add(Item item)
	{	// 和 Stack 的 push() 方法完全相同
		Node oldfirst = first;
		first = new Node();
		first.item = item;
		first.next = oldfirst;
	}
	public Iterator iterator()
	{  return new ListIterator();  }
	private class ListIterator implements Iterator
	{
		private Node current = first;
		public boolean hasNext()
		{  return current ! = null;  }
		public void remove() { }
		public Item next()
		{
			Item item = current.item;
			current = current.next;
			return item;
		}
	}
}