下压栈（LIFO）详解

写在前面的话：

一枚自学Java和算法的工科妹子。

• 算法学习书目：算法（第四版） Robert Sedgewick
• 算法视频教程：Coursera  Algorithms Part1&2

本文是根据《算法（第四版）》的个人总结，如有错误，请批评指正。

一、下压栈的定义

下压栈（简称栈）是一种基于后进先出（LIFO）策略的集合类型。栈只有一个出口，允许新增元素（只能在栈顶上增加）、移出元素（只能移出栈顶元素）等操作。

当用例使用foreach语句迭代遍历栈中的元素时，元素的处理顺序和它们被压人栈中的顺序正好相反。

二、下压栈的实现

1.定容栈（数组实现）

import java.util.Iterator;
import java.util.NoSuchElementException;public class FixedCapacityStack implements Iterable {private Item[] a;    // holds the itemsprivate int N;       // number of items in stack// create an empty stack with given capacitypublic FixedCapacityStack(int capacity) {a = (Item[]) new Object[capacity];   // no generic array creationN = 0;}public boolean isEmpty()          {  return N == 0;                    }public void push(Item item)       {  a[N++] = item;                    }public Item pop()                 {  return a[--N];                    }
    public Iterator iterator()  { return new ReverseArrayIterator(); }public class ReverseArrayIterator implements Iterator {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 stack = new FixedCapacityStack(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 stackStdOut.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 implements Iterable {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/2if (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 iterator() {return new ReverseArrayIterator();}private class ReverseArrayIterator implements Iterator {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 stack = new ResizingArrayStack();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 implements Iterable {private Node first;     // 栈顶（最先添加的元素）private int n;                // 元素数量// 定义链表结点的内部类private static class Node {private Item item;private Node next;}public Stack() {first = null;n = 0;}public boolean isEmpty() {return first == null;}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() {if (isEmpty()) throw new NoSuchElementException("Stack underflow");Item item = first.item;        // save item to returnfirst = first.next;            // delete first noden--;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 iterator() {return new ListIterator(first);}private class ListIterator implements Iterator {private Node current;public ListIterator(Node 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 stack = new Stack();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 ops  = new Stack();Stack vals = new Stack();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）咨询.

转载于:https://www.cnblogs.com/zouzz/p/6090910.html

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！