棧的定義：

棧是一種特殊的線性表。其特殊性在于限定插入和刪除數(shù)據(jù)元素的操作只能在線性表的一端進行

從影響數(shù)據(jù)結(jié)構(gòu)的3個要素來分析棧：邏輯結(jié)構(gòu)弥姻、存儲結(jié)構(gòu)记劝、數(shù)據(jù)操作慢叨。

• 邏輯結(jié)構(gòu)：線性結(jié)構(gòu)
• 存儲結(jié)構(gòu)：底層可以是順序存儲，比如基于數(shù)組丽惭；底層可以是鏈式存儲击奶，比如基于鏈表。
• 數(shù)據(jù)操作：棧中對數(shù)據(jù)的增加刪除需要滿足先進先出的規(guī)則责掏。

底層為數(shù)組的棧實現(xiàn)：

本文使用Java語言實現(xiàn)柜砾，該實現(xiàn)的棧底層數(shù)據(jù)結(jié)構(gòu)為數(shù)組，支持數(shù)組的動態(tài)變?nèi)荨?/p>

接口定義

import java.util.Iterator;

/**
 *
 * @Created on 2017-02-15 8:40
 * 棧結(jié)構(gòu)定義换衬，定義了基本的6種操作
 */
public interface FlowerStack<T> {

    /**
     * 壓棧
     * @param item
     */
    void push(T item);

    /**
     * 出棧
     * @return
     */
    T pop();

    /**
     * 棧的大小
     * @return
     */
    int size();

    /**
     * 棧是否為空
     * @return
     */
    boolean isEmpty();

    /**
     * 生成迭代器
     */
    Iterator<T> iterator();


}

實現(xiàn)類代碼：

import java.util.Iterator;

/**
 * @Created on 2017-02-15 8:23
 * 自定義棧 該類采用順序棧的方式
 * 要求可以自動擴容痰驱、縮小
 */
public class FlowerArrayStack<T> implements FlowerStack<T> {

    // 持有一個數(shù)組
    private T[] arr = (T[]) new Object[1];
    private int length = 0;


    public FlowerArrayStack() {
        // 初始化
    }

    public void push(T item) {

        // length 指針上移

        if (length == arr.length) {
            resize(arr.length * 2);
        }

        arr[length++] = item;
    }

    @Override
    public T pop() {
        // 返回最頂部的
        if (length == 0) {
            return null;
        }
        T result = arr[--length];
        arr[length] = null;
        // 注意縮小容量
        if (length > 0 && length == arr.length / 4) {
            resize(arr.length / 2);
        }
        return result;
    }

    private void resize(int max) {
        T[] temp = (T[]) new Object[max];
        for(int i=0; i<length; i++) {
            temp[i] = arr[i];
        }
        this.arr = temp;
    }

    @Override
    public int size() {
        return this.length;
    }

    @Override
    public boolean isEmpty() {
        return this.length == 0;
    }

    @Override
    public Iterator<T> iterator() {
        return new FlowerArrayStackIterator();
    }

    public int getCapacity() {
        return arr.length;
    }

    public int getLength() {
        return length;
    }

    public void setLength(int length) {
        this.length = length;
    }

   class FlowerArrayStackIterator implements Iterator<T> {

       int i = length;

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

       @Override
       public T next() {
           return arr[--i];
       }

       @Override
       public void remove() {

       }
   }

}

測試用例代碼：

import org.junit.Test;

import java.util.Iterator;

/**
 * 
 * @Created on 2017-02-15 14:33
 * FlowerArrayStack 測試類
 */
public class FlowerArrayStackTest {

    @Test
    public void test() {
        FlowerArrayStack<Integer> stack = new FlowerArrayStack<Integer>();
        for(int i=0; i<500; i++) {
            stack.push(i);
        }

        Iterator<Integer> it = stack.iterator();
        while (it.hasNext()) {
            System.out.println(it.next());
        }

        for(int i=0; i<1000; i++) {
            stack.pop();
        }

    }

}