摘要：一前言上一篇已經講過了鏈表實現單向鏈表了，它跟數組都是線性結構的基礎，本文主要講解線性結構的應用棧和隊列如果寫錯的地方希望大家能夠多多體諒并指正哦，如果有更好的理解的方式也希望能夠在評論下留言，讓大家學習學習二數據結構棧就是這么簡單數據結構

上一篇已經講過了鏈表【Java實現單向鏈表】了，它跟數組都是線性結構的基礎，本文主要講解線性結構的應用：棧和隊列

如果寫錯的地方希望大家能夠多多體諒并指正哦，如果有更好的理解的方式也希望能夠在評論下留言，讓大家學習學習～

數據結構的棧長的是這個樣子：

其實非常好理解，我們將棧可以看成一個箱子

往箱子里面放東西叫做入棧

往箱子里面取東西叫做出棧

箱子的底部叫做棧底

箱子的頂部叫做棧頂

說到棧的特性，肯定會有一句經典的言語來概括：先進后出(LIFO, Last In First Out)

往箱子里邊放蘋果，箱子底部的蘋果想要拿出來，得先把箱子頂部的蘋果取走才行

棧的分類有兩種：

靜態(tài)棧(數組實現)

動態(tài)棧(鏈表實現)

從上一篇寫鏈表我就認知到我的算法是有多渣了，普通的單鏈表操作也能把我繞得暈暈的。

由于我的鏈表還不是很熟，棧又不是很難，那么我就用鏈表來創(chuàng)建動態(tài)棧了！

既然是用鏈表，我們還是把上一篇節(jié)點的代碼拿過來吧：

public class Node {

    //數據域
    public int data;

    //指針域，指向下一個節(jié)點
    public Node next;

    public Node() {
    }

    public Node(int data) {
        this.data = data;
    }

    public Node(int data, Node next) {
        this.data = data;
        this.next = next;
    }
    
}

要鏈表用來表示棧，這次會有兩個指針：

棧頂

棧底

public class Stack {

    public Node stackTop;
    public Node stackBottom;

    public Stack(Node stackTop, Node stackBottom) {
        this.stackTop = stackTop;
        this.stackBottom = stackBottom;
    }

    public Stack() {
    }


}

將原本棧頂指向的節(jié)點交由新節(jié)點來指向，棧頂指向新加入的節(jié)點

    /**
     * 進棧
     *
     * @param stack 棧
     * @param value 要進棧的元素
     */
    public static void pushStack(Stack stack, int value) {

        // 封裝數據成節(jié)點
        Node newNode = new Node(value);


        // 棧頂本來指向的節(jié)點交由新節(jié)點來指向
        newNode.next = stack.stackTop;

        // 棧頂指針指向新節(jié)點
        stack.stackTop = newNode;

    }

只要棧頂元素的指針不指向棧底，那么就一直輸出遍歷結果：

    /**
     * 遍歷棧(只要棧頂指針不指向棧底指針，就一直輸出)
     *
     * @param stack
     */
    public static void traverse(Stack stack) {
        Node stackTop = stack.stackTop;

        while (stackTop != stack.stackBottom) {

            System.out.println("關注公眾號：Java3y：" + stackTop.data);

            stackTop = stackTop.next;
        }


    }

測試：

    public static void main(String[] args) {

        //初始化棧(無元素)
        Stack stack = new Stack(new Node(), new Node());

        //棧頂和棧尾是同一指向
        stack.stackBottom = stack.stackTop;

        //指向null
        stack.stackTop.next = null;


        //進棧
        pushStack(stack, 3);
        pushStack(stack, 4);
        pushStack(stack, 5);

        traverse(stack);

    }

結果：

這就符合了先進后出的特性了～

很簡單，只要棧頂和棧底是同一指向，那么該棧就為空

    /**
     * 判斷該棧是否為空
     *
     * @param stack
     */
    public static void isEmpty(Stack stack) {
        if (stack.stackTop == stack.stackBottom) {

            System.out.println("關注公眾號：Java3y---->該棧為空");
        } else {

            System.out.println("關注公眾號：Java3y---->該棧不為空");

        }

    }

在出棧之前看看該棧是否為空，不為空才出棧...

將棧頂的元素的指針(指向下一個節(jié)點)賦值給棧頂指針(完成出棧)

    /**
     * 出棧(將棧頂的指針指向下一個節(jié)點)
     * @param stack
     */
    public static void popStack(Stack stack) {

        // 棧不為空才能出棧
        if (!isEmpty(stack)) {

            //棧頂元素
            Node top = stack.stackTop;

            // 棧頂指針指向下一個節(jié)點
            stack.stackTop = top.next;

            System.out.println("關注公眾號：Java3y---->出棧的元素是：" + top.data);

        }
    }

測試出棧：

多次出棧：

當時學C的時候需要釋放內存資源，可是Java不用呀，所以棧頂指向棧底，就清空棧了

    /**
     * 清空棧
     * @param stack
     */
    public static void clearStack(Stack stack) {

        stack.stackTop = null;
        stack.stackBottom = stack.stackTop;
    }

數據結構的隊列長的是這個樣子：

其實隊列非常好理解，我們將隊列可以看成小朋友排隊

隊尾的小朋友到指定的地點了-->出隊

有新的小朋友加入了-->入隊

相對于棧而言，隊列的特性是：先進先出

先排隊的小朋友肯定能先打到飯！

隊列也分成兩種：

靜態(tài)隊列(數組實現)

動態(tài)隊列(鏈表實現)

這次我就使用數組來實現靜態(tài)隊列了。值得注意的是：往往實現靜態(tài)隊列，我們都是做成循環(huán)隊列

做成循環(huán)隊列的好處是不浪費內存資源！

這次我們使用的是數組來實現靜態(tài)隊列，因此我們可以這樣設計：

public class Queue {


    //數組
    public int [] arrays;

    //指向第一個有效的元素
    public int front;

    //指向有效數據的下一個元素(即指向無效的數據)
    public int rear;

}

從上面的設計我們可以發(fā)現：rear并不指向最后一個有效的元素，在循環(huán)隊列中這樣設計是非常方便的！因為這樣設計可以讓我們分得清隊頭和隊尾(不然循環(huán)隊列不斷入隊或出隊，位置是變化很快的)

由于我們是循環(huán)隊列，所以front和rear值會經常變動，我們得把front和rear的值限定在一個范圍內，不然會超出隊列的長度的。

有這么一個算法：rear=（rear+1)%數組長度

比如rear的下標是2，數組的長度是6，往后面移一位是3，那么rear = （rear+1) % 6，結果還是3

此時隊列為空，分配了6個長度給數組(只能裝5個實際的數字，rear指向的是無效的位置的)

    public static void main(String[] args) {

        //初始化隊列
        Queue queue = new Queue();

        queue.front = 0;
        queue.rear = 0;
        queue.arrays = new int[6];
        
    }

如果rear指針和front指針緊挨著，那么說明隊列就滿了

    /**
     * 判斷隊列是否滿了，front和rear指針緊挨著，就是滿了
     * @param queue
     * @return
     */
    public static boolean isFull(Queue queue) {
        if ((queue.rear + 1) % queue.arrays.length == queue.front) {

            System.out.println("關注公眾號：Java3y--->此時隊列滿了！");
            return true;
        } else {
            System.out.println("關注公眾號：Java3y--->此時隊列沒滿了！");
            return false;
        }
    }

判斷該隊列是否滿了

入隊的值插入到隊尾中(具體的位置就是rear指針的位置【再次聲明：rear指向的是無效元素的位置】

rear指針移動(再次指向無效的元素位置)

    /**
     * 入隊
     *
     * @param queue
     */
    public static void enQueue(Queue queue,int value) {

        // 不是滿的隊列才能入隊
        if (!isFull(queue)) {

            // 將新的元素插入到隊尾中
            queue.arrays[queue.rear] = value;

            // rear節(jié)點移動到新的無效元素位置上
            queue.rear = (queue.rear + 1) % queue.arrays.length;
        }
    }

只要front節(jié)點不指向rear節(jié)點，那么就可以一直輸出

    /**
     * 遍歷隊列
     * @param queue
     *
     */
    public static void traverseQueue(Queue queue) {

        // front的位置
        int i = queue.front;

        while (i != queue.rear) {

            System.out.println("關注公眾號：Java3y--->" + queue.arrays[i]);

            //移動front
            i = (i + 1) % queue.arrays.length;
        }

    }

隊列沒滿時：

隊列已滿了就插入不了了(驗證上面的方法是否正確)：

只要rear和front指針指向同一個位置，那該隊列就是空的了

    /**
     * 判斷隊列是否空，front和rear指針相等，就是空了
     * @param queue
     * @return
     */
    public static boolean isEmpty(Queue queue) {
        if (queue.rear  == queue.front) {
            System.out.println("關注公眾號：Java3y--->此時隊列空的！");
            return true;
        } else {
            System.out.println("關注公眾號：Java3y--->此時隊列非空！");
            return false;
        }
    }

出隊的邏輯也非常簡單：

判斷該隊列是否為null

如果不為null，則出隊，只要front指針往后面移就是出隊了!

     /**
     * 出隊
     *
     * @param queue
     */
    public static void outQueue(Queue queue) {

        //判斷該隊列是否為null
        if (!isEmpty(queue)) {


            //不為空才出隊
            int value = queue.arrays[queue.front];
            System.out.println("關注公眾號：Java3y--->出隊的元素是：" + value);

            // front指針往后面移
            queue.front = (queue.front + 1) % queue.arrays.length;

        }


    }

結果：

數據結構的棧和隊列的應用非常非常的多，這里也只是最簡單的入門，理解起來也不困難。

棧：先進后出

隊列：先進先出

關于數據結構這方面我就到暫時到這里為止了，都簡單的入個門，以后遇到更加復雜的再繼續(xù)開新的文章來寫～畢竟現在水平不夠，也無法理解更深層次的東西～數據結構這東西是必備的，等到研究集合的時候還會來回顧它，或者遇到新的、復雜的也會繼續(xù)學習....

想要更加深入數據結構的同學就得去翻閱相關的書籍咯～這僅僅是冰山一角

如果文章有錯的地方歡迎指正，大家互相交流。習慣在微信看技術文章，想要獲取更多的Java資源的同學，可以關注微信公眾號:Java3y