棧（Stack）

? 棧是具有一定操作約束的線性表，它只在一端（棧頂）做插入和刪除操作，它是典型的后進(jìn)先出的一種數(shù)據(jù)結(jié)構(gòu)，特別的，插入數(shù)據(jù)稱為入棧（Push），刪除數(shù)據(jù)稱為出棧（Pop）。

抽象數(shù)據(jù)類型描述

? 數(shù)據(jù)對(duì)象集：一個(gè)有0個(gè)或多個(gè)元素的線性表。

? 操作集：Item 代表數(shù)據(jù)元素類型

• int length() 返回棧的長(zhǎng)度（所包含的元素的個(gè)數(shù)）。
• boolean isEmpty() 棧是否為空。
• void push(Item item) 入棧。
• Item pop() 出棧

棧的順序存儲(chǔ)

? 在類的內(nèi)部使用數(shù)組來存儲(chǔ)元素，數(shù)組的大小會(huì)根據(jù)需要?jiǎng)討B(tài)的變化，因?yàn)橛幸粋€(gè)resize()方法，使用N來表示棧頂?shù)纳厦嬉粋€(gè)位置，入棧時(shí)，先將元素放入data[N]，N再進(jìn)行加一的操作；反之，出棧時(shí)，先將N減一，取出元素，再置此時(shí)data[N]的值為null，避免對(duì)象游離。為了能夠使?？梢员闅v，實(shí)現(xiàn)了Iterable接口，完整代碼如下：

public class ArrayStack<Item> implements Iterable<Item> {

    private Item[] data = (Item[]) new Object[1]; // 棧里的數(shù)據(jù)
    private int N = 0; // 棧的元素個(gè)數(shù)

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

    public int length(){
        return N;
    }

    public void resize(int len){
        Item[] temp = (Item[]) new Object[len];
        for (int i=0; i<N; i++){
            temp[i] = data[i];
        }
        data = temp;
    }

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

    public Item pop(){
        Item item = data[--N];
        data[N] = null; // 避免對(duì)象游離
        if (N>0 && N==data.length/4){
            this.resize(data.length/2);
        }
        return item;
    }

    @Override
    public Iterator<Item> iterator() {
        return new ReverseArrayIterator();
    }

    // 內(nèi)部類
    public class ReverseArrayIterator implements Iterator<Item>{
        private int i = N;

        public boolean hasNext(){
            return i>0;
        }

        public Item next(){
            return data[--i];
        }

        public void remove(){

        }
    }

    public static void main(String[] args) {
        ArrayStack<Integer> testStack = new ArrayStack<>();
        testStack.push(1);
        testStack.push(2);
        testStack.push(3);
        testStack.push(4);
        for (Integer i:testStack){
            System.out.println(i);
        }
        testStack.pop();
        for (Integer i:testStack){
            System.out.println(i);
        }
    }
}

棧的鏈?zhǔn)酱鎯?chǔ)

? 設(shè)定一個(gè)top指針表示棧頂，所以顯然當(dāng)top為null時(shí)，表示?？?。入棧：新建一個(gè)oldTop變量指向此時(shí)的top指向，再讓top指向新插入的元素結(jié)點(diǎn)，再設(shè)其next指針指向oldTop；出棧：只需在取出元素之后讓棧頂指針指向下一個(gè)元素即可，完整代碼如下：

public class Stack<Item> implements Iterable<Item> {
    private Node top;
    private int N;

    private class Node{
        Item item;
        Node next;

        public Node(Item item, Node next) {
            this.item = item;
            this.next = next;
        }
    }

    public boolean isEmpty(){
        return top==null;
    }

    public int length(){
        return N;
    }

    public void push(Item item){
        Node oldTop = top;
        top = new Node(item,oldTop);
        N = N + 1;
    }

    public Item pop(){
        Item item = top.item;
        top = top.next;
        return item;
    }

    @Override
    public Iterator<Item> iterator() {
        return new StackIterator();
    }

    private class StackIterator implements Iterator<Item>{

        private Node current = top;

        @Override
        public boolean hasNext() {
            return current != null;
        }

        @Override
        public Item next() {
            Item item = current.item;
            current = current.next;
            return item;
        }
    }
}