棧

基本概念

棧（stack）在計(jì)算機(jī)科學(xué)中是限定僅在表尾進(jìn)行插入或刪除操作的線性表。棧是一種數(shù)據(jù)結(jié)構(gòu)，它按照后進(jìn)先出的原則存儲(chǔ)數(shù)據(jù)，先進(jìn)入的數(shù)據(jù)被壓入棧底，最后的數(shù)據(jù)在棧頂，需要讀數(shù)據(jù)的時(shí)候從棧頂開始彈出數(shù)據(jù)。棧是只能在某一端插入和刪除的特殊線性表。用桶堆積物品，先堆進(jìn)來的壓在底下，隨后一件一件往上堆。取走時(shí)，只能從上面一件一件取。讀和取都在頂部進(jìn)行，底部一般是不動(dòng)的。棧就是一種類似桶堆積物品的數(shù)據(jù)結(jié)構(gòu)，進(jìn)行刪除和插入的一端稱棧頂，另一端稱棧底。插入一般稱為進(jìn)棧，刪除則稱為退棧。 棧也稱為后進(jìn)先出表。

代碼

public class MyStack {
    //底層實(shí)現(xiàn)是一個(gè)數(shù)組
    private long[] arr;
    // 數(shù)組下標(biāo)
    private int top;

    /**
     * 默認(rèn)構(gòu)造方法
     */
    public MyStack() {
        arr = new long[10];
        top = -1;
    }

    /**
     * 帶參數(shù)的構(gòu)造方法
     *
     * @param maxSize 數(shù)組的初始化長度
     */
    public MyStack(int maxSize) {
        arr = new long[maxSize];
        top = -1;
    }

    /**
     * 添加數(shù)據(jù)（壓棧）
     *
     * @param value 添加的數(shù)值
     */
    public void push(int value) {
        // ++top后top由-1變?yōu)榱?，即第一個(gè)值添加到arr[0]的位置
        arr[++top] = value;
    }

    /**
     * 移除數(shù)據(jù)
     *
     * @return
     */
    public long pop() {
        return arr[top--];
    }

    /**
     * 查看棧頂數(shù)據(jù)
     *
     * @return
     */
    public long peek() {
        return arr[top];
    }

    /**
     * 判斷是否為空
     *
     * @return
     */
    public boolean isEmpty() {
        return top == -1;
    }

    /**
     * 判斷是否滿了
     *
     * @return
     */
    public boolean isFull() {
        return top == arr.length - 1;
    }
}

測試

public class TestMyStack {
    public static void main(String[] args) {
        MyStack ms = new MyStack(4);
        ms.push(0);
        ms.push(1);
        ms.push(2);
        ms.push(3);
        System.out.println(ms.isEmpty());
        System.out.println(ms.isFull());
        System.out.println(ms.peek());
        while (!ms.isEmpty()){
            System.out.print(ms.pop()+" ");
        }
        System.out.println();
        System.out.println(ms.isEmpty());
        System.out.println(ms.isFull());
    }
}

結(jié)果

false
true
3
3 2 1 0 
true
false

從結(jié)果中可以看到，往棧中壓入數(shù)據(jù)的順序(0,1,2,3)和彈出數(shù)據(jù)的順序(3,2,1,0)剛好相反。

隊(duì)列

基本概念

隊(duì)列的操作是在兩端進(jìn)行的，其中一端只能進(jìn)行插入，該端稱為隊(duì)列的隊(duì)尾，而另一端只能進(jìn)行刪除，該端稱為隊(duì)列的隊(duì)首。
隊(duì)列在我們?nèi)粘Ｉ钪薪?jīng)常碰到，例如，排隊(duì)買東西，誰先來，誰先買，買完就走，誰后來，誰在隊(duì)的最后面排隊(duì)。隊(duì)列的運(yùn)算規(guī)則是FIFO（first in first out），或者叫做先進(jìn)先出。

代碼

public class MyQueue {
    //底層實(shí)現(xiàn)是一個(gè)數(shù)組
    private long[] arr;
    //有效數(shù)據(jù)大小
    private int elements;
    //隊(duì)頭
    private int front;
    //隊(duì)尾
    private int end;

    /**
     * 默認(rèn)的無參構(gòu)造
     */
    public MyQueue() {
        arr = new long[10];
        elements = 0;
        front = 0;
        end = -1;
    }

    /**
     * 帶參數(shù)的構(gòu)造方法
     *
     * @param maxSize
     */
    public MyQueue(int maxSize) {
        arr = new long[maxSize];
        elements = 0;
        front = 0;
        end = -1;
    }

    /**
     * 從隊(duì)尾插入數(shù)據(jù)
     *
     * @param value
     */
    public void insert(long value) {
        if (end == arr.length - 1) {
            end = -1;
        }
        //每次都從隊(duì)尾插入數(shù)據(jù)
        arr[++end] = value;
        elements++;
    }

    /**
     * 從隊(duì)頭刪除數(shù)據(jù)
     *
     * @return
     */
    public long remove() {
        long value = arr[front++];
        if (front == arr.length) {
            front = 0;
        }
        elements--;
        return value;
    }

    /**
     * 從隊(duì)頭查看數(shù)據(jù)
     *
     * @return
     */
    public long peek() {
        return arr[front];
    }

    /**
     * 判斷隊(duì)列是否為空
     *
     * @return
     */
    public boolean isEmpty() {
        return elements == 0;
    }

    /**
     * 判斷隊(duì)列是否滿了
     *
     * @return
     */
    public boolean isFull() {
        return elements == arr.length;
    }
}

測試

public class TestMyqueue {
    public static void main(String[] args) {
        MyQueue mq = new MyQueue(4);
        mq.insert(0);
        mq.insert(1);
        mq.insert(2);
        mq.insert(3);
        System.out.println(mq.isEmpty());
        System.out.println(mq.isFull());
        System.out.println(mq.peek());
        while (!mq.isEmpty()){
            System.out.print(mq.remove()+" ");
        }
        System.out.println();
        System.out.println(mq.isEmpty());
        System.out.println(mq.isFull());
    }
}

結(jié)果

false
true
0
0 1 2 3 
true
false

從結(jié)果中可以看到，往隊(duì)列中添加數(shù)據(jù)的順序(0,1,2,3)和移除數(shù)據(jù)的順序(0,1,2,3)相同。