一、定义
下压栈（简称栈）是一种基于后进先出（LIFO）策略的集合类型。
1-0 栈的示意图
二、API
2-0 栈的API定义
三、实现
3.1 数组实现
- 可动态调整大小的栈实现（数组方式）：
1. 当栈容量满时，采用遍历数组的方式进行扩容，默认调整为原容量的2倍。
2. 当栈容量变成1/4时，默认调整为原容量的1/2。
public class ResizingArrayStack<Item> implements Iterable<Item> {
private Item[] a; // array of items
private int n; // number of elements on stack
/**
* Initializes an empty stack.
*/
public ResizingArrayStack() {
a = (Item[]) new Object[2];
n = 0;
}
/**
* Is this stack empty?
* @return true if this stack is empty; false otherwise
*/
public boolean isEmpty() {
return n == 0;
}
/**
* Returns the number of items in the stack.
* @return the number of items in the stack
*/
public int size() {
return n;
}
// resize the underlying array holding the elements
private void resize(int capacity) {
assert capacity >= n;
// textbook implementation
Item[] temp = (Item[]) new Object[capacity];
for (int i = 0; i < n; i++) {
temp[i] = a[i];
}
a = temp;
// alternative implementation
// a = java.util.Arrays.copyOf(a, capacity);
}
/**
* Adds the item to this stack.
* @param item the item to add
*/
public void push(Item item) {
if (n == a.length) resize(2*a.length); // double size of array if necessary
a[n++] = item; // add item
}
/**
* Removes and returns the item most recently added to this stack.
* @return the item most recently added
* @throws java.util.NoSuchElementException if this stack is empty
*/
public Item pop() {
if (isEmpty()) throw new NoSuchElementException("Stack underflow");
Item item = a[n-1];
a[n-1] = null; // to avoid loitering
n--;
// shrink size of array if necessary
if (n > 0 && n == a.length/4) resize(a.length/2);
return item;
}
/**
* Returns (but does not remove) the item most recently added to this stack.
* @return the item most recently added to this stack
* @throws java.util.NoSuchElementException if this stack is empty
*/
public Item peek() {
if (isEmpty()) throw new NoSuchElementException("Stack underflow");
return a[n-1];
}
/**
* Returns an iterator to this stack that iterates through the items in LIFO order.
* @return an iterator to this stack that iterates through the items in LIFO order.
*/
public Iterator<Item> iterator() {
return new ReverseArrayIterator();
}
// an iterator, doesn't implement remove() since it's optional
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--];
}
}
}
3.2 链表实现
- 栈的链表实现方式：
1. 栈顶即链表的头。
2. 入栈相当于“头插法”插入元素。
public class Stack<Item> implements Iterable<Item> {
private Node<Item> first; // top of stack
private int n; // size of the stack
// helper linked list class
private static class Node<Item> {
private Item item;
private Node<Item> next;
}
/**
* Initializes an empty stack.
*/
public Stack() {
first = null;
n = 0;
}
/**
* Returns true if this stack is empty.
*
* @return true if this stack is empty; false otherwise
*/
public boolean isEmpty() {
return first == null;
}
/**
* Returns the number of items in this stack.
*
* @return the number of items in this stack
*/
public int size() {
return n;
}
/**
* Adds the item to this stack.
*
* @param item the item to add
*/
public void push(Item item) {
Node<Item> oldfirst = first;
first = new Node<Item>();
first.item = item;
first.next = oldfirst;
n++;
}
/**
* Removes and returns the item most recently added to this stack.
*
* @return the item most recently added
* @throws NoSuchElementException if this stack is empty
*/
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
}
/**
* Returns (but does not remove) the item most recently added to this stack.
*
* @return the item most recently added to this stack
* @throws NoSuchElementException if this stack is empty
*/
public Item peek() {
if (isEmpty()) throw new NoSuchElementException("Stack underflow");
return first.item;
}
/**
* Returns a string representation of this stack.
*
* @return the sequence of items in this stack in LIFO order, separated by spaces
*/
public String toString() {
StringBuilder s = new StringBuilder();
for (Item item : this) {
s.append(item);
s.append(' ');
}
return s.toString();
}
/**
* Returns an iterator to this stack that iterates through the items in LIFO order.
*
* @return an iterator to this stack that iterates through the items in LIFO order
*/
public Iterator<Item> iterator() {
return new ListIterator<Item>(first);
}
// an iterator, doesn't implement remove() since it's optional
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;
}
}
}
3-2 操作示意图
四、应用示例
4.1 简单表达式求值
4.1.1 问题
假设一个简单的算术表达式，仅支持+、-、*、/、(、)、sqrt运算符，求该算术表达式的值。
例如：（1+（（2+3）*（4*5）））
4.1.2 思路
Dijkstra双栈算法，用两个栈（一个保存运算符，一个保存操作数）。
- 将操作数压入操作数栈；
- 将运算符压入运算符栈；
- 忽略左括号；
- 遇到右括号时，弹出一个运算符，弹出所需数量的操作数，并将运算符和操作数的计算结果压入操作数栈；
- 处理完最后一个右括号后，操作数栈上只有一个数，它就是表达式的值。
4.1.3 证明
- 每当算法遇到一个被括号包围并由一个运算符和两个操作数组成的子表达式时，它都将运算符和操作数的计算结果压入操作数栈。
- 在计算步骤1的子表达式时，运用相同规律，直到得到一个最终值
4.1.3 源码
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());
}
}
网友评论