写在前面的话：
一枚自学Java和算法的工科妹子。
- 算法学习书目：算法（第四版） Robert Sedgewick
- 算法视频教程：Coursera Algorithms Part1&2
本文是根据《算法（第四版）》的个人总结，如有错误，请批评指正。
一、下压栈的定义
下压栈（简称栈）是一种基于后进先出（LIFO）策略的集合类型。栈只有一个出口，允许新增元素（只能在栈顶上增加）、移出元素（只能移出栈顶元素）等操作。
当用例使用foreach语句迭代遍历栈中的元素时，元素的处理顺序和它们被压人栈中的顺序正好相反。
二、下压栈的实现
1.定容栈（数组实现）
import java.util.Iterator;
import java.util.NoSuchElementException; public class FixedCapacityStack<Item> implements Iterable<Item> {
private Item[] a; // holds the items
private int N; // number of items in stack // create an empty stack with given capacity
public FixedCapacityStack(int capacity) {
a = (Item[]) new Object[capacity]; // no generic array creation
N = 0;
} public boolean isEmpty() { return N == 0; }
public void push(Item item) { a[N++] = item; }
public Item pop() { return a[--N]; }
public Iterator<Item> iterator() { return new ReverseArrayIterator(); } public class ReverseArrayIterator implements Iterator<Item> {
private int i = N-1; public boolean hasNext() {
return i >= 0;
} public Item next() {
if (!hasNext()) throw new NoSuchElementException();
return a[i--];
} public void remove() {
throw new UnsupportedOperationException();
}
} public static void main(String[] args) {
int max = Integer.parseInt(args[0]);
FixedCapacityStack<String> stack = new FixedCapacityStack<String>(max);
while (!StdIn.isEmpty()) {
String item = StdIn.readString();
if (!item.equals("-")) stack.push(item);
else if (stack.isEmpty()) StdOut.println("BAD INPUT");
else StdOut.print(stack.pop() + " ");
}
StdOut.println(); // print what's left on the stack
StdOut.print("Left on stack: ");
for (String s : stack) {
StdOut.print(s + " ");
}
StdOut.println();
}
}
2.动态调整大小的栈（数组实现）
import java.util.Iterator;
import java.util.NoSuchElementException; public class ResizingArrayStack<Item> implements Iterable<Item> {
private Item[] a; // 声明数组
private int n; // 栈中元素数量 public ResizingArrayStack() {
a = (Item[]) new Object[2];
n = 0;
} public boolean isEmpty() {
return n == 0;
} public int size() {
return n;
} // 将栈移动到一个大小为max的新数组
private void resize(int capacity) {
assert capacity >= n; Item[] temp = (Item[]) new Object[capacity];
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() {
if (isEmpty()) throw new NoSuchElementException("Stack underflow");
Item item = a[n-1];
a[n-1] = null; // 避免对象游离
n--;
// 若栈的元素个数只有数组大小的1/4，则调整数组大小为原先的1/2
if (n > 0 && n == a.length/4) resize(a.length/2);
return item;
} public Item peek() {
if (isEmpty()) throw new NoSuchElementException("Stack underflow");
return a[n-1];
} public Iterator<Item> iterator() {
return new ReverseArrayIterator();
} private class ReverseArrayIterator implements Iterator<Item> {
private int i; public ReverseArrayIterator() {
i = n-1;
} public boolean hasNext() {
return i >= 0;
} public void remove() {
throw new UnsupportedOperationException();
} public Item next() {
if (!hasNext()) throw new NoSuchElementException();
return a[i--];
}
} public static void main(String[] args) {
ResizingArrayStack<String> stack = new ResizingArrayStack<String>();
while (!StdIn.isEmpty()) {
String item = StdIn.readString();
if (!item.equals("-")) stack.push(item);
else if (!stack.isEmpty()) StdOut.print(stack.pop() + " ");
}
StdOut.println("(" + stack.size() + " left on stack)");
}
}
解释对象游离：
- 对象游离概念：保存了一个不需要的对象的引用。
- 如何避免对象游离：Java的垃圾回收机制是回收所有无法被访问的对象的内存。在我们对pop()的实现中，被弹出的元素的引用依然存在与数组中，使得即使该元素被使用完后也无法将其回收。所以需要将数组中的这个引用覆盖来避免对象游离，只要将被弹出的数组位置的元素值设置为null，就可以覆盖无用的引用，并使系统使用完被弹出的元素后回收它的内存。
3.链表实现
import java.util.Iterator;
import java.util.NoSuchElementException; public class Stack<Item> implements Iterable<Item> {
private Node<Item> first; // 栈顶（最先添加的元素）
private int n; // 元素数量 // 定义链表结点的内部类
private static class Node<Item> {
private Item item;
private Node<Item> next;
} public Stack() {
first = null;
n = 0;
} public boolean isEmpty() {
return first == null;
} public int size() {
return n;
} // 在表头插入节点
public void push(Item item) {
Node<Item> oldfirst = first;
first = new Node<Item>();
first.item = item;
first.next = oldfirst;
n++;
} // 在表头删除节点
public Item pop() {
if (isEmpty()) throw new NoSuchElementException("Stack underflow");
Item item = first.item; // save item to return
first = first.next; // delete first node
n--;
return item; // return the saved item
} public Item peek() {
if (isEmpty()) throw new NoSuchElementException("Stack underflow");
return first.item;
} public String toString() {
StringBuilder s = new StringBuilder();
for (Item item : this) {
s.append(item);
s.append(' ');
}
return s.toString();
} public Iterator<Item> iterator() {
return new ListIterator<Item>(first);
} private class ListIterator<Item> implements Iterator<Item> {
private Node<Item> current; public ListIterator(Node<Item> first) {
current = first;
} public boolean hasNext() {
return current != null;
} public void remove() {
throw new UnsupportedOperationException();
} public Item next() {
if (!hasNext()) throw new NoSuchElementException();
Item item = current.item;
current = current.next;
return item;
}
} public static void main(String[] args) {
Stack<String> stack = new Stack<String>();
while (!StdIn.isEmpty()) {
String item = StdIn.readString();
if (!item.equals("-"))
stack.push(item);
else if (!stack.isEmpty())
StdOut.print(stack.pop() + " ");
}
StdOut.println("(" + stack.size() + " left on stack)");
}
}
三、下压栈不同实现方式的比较--Resizing Array （可调整大小的数组） VS. Linked List（链表）
1.Resizing Array （可调整大小的数组）
- 构造含有N（N是2的幂）个元素的栈，数据结构初识为空，N次连续的push()调用需要访问数组元素的次数：N+（4+8+......+2N）=5N-4，前面的N表示添加N个元素时push()中a[n++] = item访问数组N次，后面（4+8+......+2N）是push()中每次数组长度加倍时，resize()方法初始化数据结构需要访问数组次数的总和。因此，每次操作访问数组的平均次数为常数，但最后一次操作所需的时间是线性的。这是一种均摊分析，将少量昂贵操作的成本通过各种大量廉价操作平摊。但是这种方式在许多场景下不适用，当遇到需要增加（或减少）数组大小时，导致push()压栈（或出栈）的耗时很长；
- 占用总的时间和内存相对较少，数组内存24+xN（x根据Item类型而定，整数4个字节）。
2.Linked List（链表）
- 每次操作（出栈和压栈）都是常数时间，操作的速度平稳；
- 占用总的时间和内存比较大，为了维持连接，每个Stack Node需要40个字节的内存。
四、下压栈的应用
实例：Dijkstra的双栈算数表达式求值算法
- 将操作数压入操作数栈；
- 将运算符压入运算符栈；
- 忽略左括号；
- 在遇到右括号时，弹出一个运算符，弹出所需数量的操作数，并将运算符和操作数的运算结果压入操作数栈。
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("(")) ;
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);
}
else vals.push(Double.parseDouble(s));
}
StdOut.println(vals.pop());
}
}
作者： 邹珍珍（Pearl_zhen）
出处： http://www.cnblogs.com/zouzz/
声明：本文版权归作者和博客园共有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出 原文链接 如有问题， 可邮件（zouzhenzhen@seu.edu.cn）咨询.