Data Structure | Stack

Stack 是一种线性的数据结构，它的最大特点是后进先出 (Last In First Out) (LIFO)

每次压入 (push) 元素，元素都储存在 Stack 的最上方，每次取出 (pop || peek) 元素，同样也只能先取出最上端的。
(可以将这些元素想象成一摞叠在一起的盘子)

Stack 的常用方法有 push(), pop(), isEmpty(), peek(), 这些操作都只花费常数时间 O(1)

Stack 有两种实现方法：通过Array，通过LinkedList。下面来逐一分析

Implementing Stack using Arrays

Stack 最顶端的元素即数组的最后一个元素
push 即向数组末尾添加一个元素；pop 即取出最后一个元素
isEmpty 即判断数组是否为空；size 即获取元素个数

public class StackImplement<E>{
    private E[] a;    // stack entries
    private int N;    // size

    public StackImplement(){       // default constructor
        a = (E[]) new Object[100]; // with capacity 100
    }

    public StackImplement(int cap){ 
        a = (E[]) new Object[cap];
    }

    public boolean isEmpty(){ 
        return N == 0;
    }

    public int size(){
        return N;
    }

    public void push(E e){
        a[N++] = e; 
    }

    public E pop(){
        return a[--N];
    }
}

需要注意的是第6行和第10行，按照范型的概念，我们本应该写成这样
a = new E[cap]
但由于历史和技术原因，Java 虚拟机并不允许这样做。我们要将其写成这样
a = (E[]) new Object[cap]
这样写在编译期间会有 warning，不用在意，尽管放心安全的使用

同样需要注意的是pop() 方法，在该方法中，我们仅用了一行代码：return a[--N]}
这样写结果是对的，a[N] 元素我们不在使用，但仍存有值
这样会导致 Loitering
Loitering: Holding a reference to an object when it is no longer needed
所以更规范的写法是：

public E pop(){
    E item = a[--N];
    a[N] = null;
    return iteml;
}

但是这种用 Array 来实现 Stack 有一个缺点：数组的 size 是固定的
我们得提供一个用户自定义 size 的constructor ，一个 default constructor 和一个特定的 size 比如1000
如果用户只存储了很少的元素，那么更多的内存空间会被浪费
如果用户存储了超过1000个元素，此时程序会 throw IllegalStateException

所以我们应该提供一个 resizing-array implementation
First try:
   push(): increase size of array a[] by 1.
   pop(): decrease siez of array a[] by 1.

Too exxpensive:
   Need to copy all item to a new array
   Inserting first N items taks time proportinal to 1 + 2 + … + N ~ N^2/2

Effective solution:
   push(): double size of array a[] when array is full.
   pop(): halve size of array a[] when array is one-quarter full

private void resize(int capacity){
    E[] copy = (E[]) new Object[capacity];
    for (int i = 0; i < N; i++){
	copy[i] = a[i];
    }
    a = copy;
}

相应的，当 array 中没有空间时，resize 成两倍
当 elements 个数只占四分之一时，resize 成一半

public void push(E item){
    if (N == a.length){
        resize(2 * a.length);
    }
    a[N++] = item;
}

public E pop(){
    E item = a[--N];
    a[N] = null;   // avoid loitering
    if (N > 0 && N == a.length / 4) resize(a.length / 2);
    return item;
}

使用这种方法构造 Stack 时
size(), isEmpty(), peek(), push(), pop() 时间复杂度都是 O(1)

使用示例：

public static void main(String[] args){
    ArrayStack<Integer> stack = new ArrayStack<Integer>();
    stack.push(1);
    stack.push(2);
    stack.push(3);
    System.out.println(stack.size());    // 3
    System.out.println(stack.pop());     // 3
    System.out.println(stack.peek());    // 2
    System.out.println(stack.isEmpty()); // false
}

Implementing Stack using Singly LinkedList

在使用链表构造 Stack 时，我们要考虑的是，把链表的那一端作为 Stack 的 top？头还是尾？
很显然，我们应该将头作为 top，因为头部的元素可以通过常数时间获取，而获取尾部元素还要遍历整个 List

import java.util.LinkedList;

public class LinkedStack<E>{
    private LinkedList<E> list = new LinkedList<>();

    public LinkedStack(){};
    public int size(){
	return list.size();
    }
    public boolean isEmpty(){
	return list.isEmpty();
    }
    public void push(E element){
	list.addFirst(element);
    }
    public E peek(){
	return list.get(0);
    }
    public E pop(){
 	return list.removeFirst();
    }

    public static void main(String[] args){
	LinkedStack<String> list = new LinkedStack<String>();
	list.push("Future");
	list.push("Googler");
	list.push("live linke Jim Morrison");
	System.out.println(list.size());      // 3
	System.out.println(list.peek());      // live linke Jim Morrison
	System.out.println(list.pop());       // live linke Jim Morrison
	System.out.println(list.isEmpty());  // false
    }
}

由于 Stack 的这种 LIFO 特点，可以用来 reverse array element

public static <E> void reverse(E[] a){
    Stack<E> stack = new ArrayStack<>(a.length);
    for (int i = 0; i < a.length; i++){
	stack.push(a[i]);
    }
    for (int i = 0; i < a.length; i++){
	a[i] = stack.pop();
    }
}

resizing array vs linked list

Linked-list implementation:
   Every operation takes constant time in the worst case.
   Uses extra time and space to deal with the links.

Resizing-array implementation:
   Every operation takes constant amortized tiem.
   Less wasted space.

---

Reference:
Data Strucuture and Algorithms in Java (7th edition) (Page 230 – Page 234)