摘要：一前言上一篇已經(jīng)講過了鏈表實(shí)現(xiàn)單向鏈表了，它跟數(shù)組都是線性結(jié)構(gòu)的基礎(chǔ)，本文主要講解線性結(jié)構(gòu)的應(yīng)用棧和隊(duì)列如果寫錯(cuò)的地方希望大家能夠多多體諒并指正哦，如果有更好的理解的方式也希望能夠在評(píng)論下留言，讓大家學(xué)習(xí)學(xué)習(xí)二數(shù)據(jù)結(jié)構(gòu)棧就是這么簡(jiǎn)單數(shù)據(jù)結(jié)構(gòu)

上一篇已經(jīng)講過了鏈表【Java實(shí)現(xiàn)單向鏈表】了，它跟數(shù)組都是線性結(jié)構(gòu)的基礎(chǔ)，本文主要講解線性結(jié)構(gòu)的應(yīng)用：棧和隊(duì)列

如果寫錯(cuò)的地方希望大家能夠多多體諒并指正哦，如果有更好的理解的方式也希望能夠在評(píng)論下留言，讓大家學(xué)習(xí)學(xué)習(xí)～

數(shù)據(jù)結(jié)構(gòu)的棧長(zhǎng)的是這個(gè)樣子：

其實(shí)非常好理解，我們將?？梢?strong>看成一個(gè)箱子

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

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

箱子的底部叫做棧底

箱子的頂部叫做棧頂

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

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

棧的分類有兩種：

靜態(tài)棧(數(shù)組實(shí)現(xiàn))

動(dòng)態(tài)棧(鏈表實(shí)現(xiàn))

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

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

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

public class Node {

    //數(shù)據(jù)域
    public int data;

    //指針域，指向下一個(gè)節(jié)點(diǎn)
    public Node next;

    public Node() {
    }

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

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

要鏈表用來表示棧，這次會(huì)有兩個(gè)指針：

棧頂

棧底

public class Stack {

    public Node stackTop;
    public Node stackBottom;

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

    public Stack() {
    }


}

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

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

        // 封裝數(shù)據(jù)成節(jié)點(diǎn)
        Node newNode = new Node(value);


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

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

    }

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

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

        while (stackTop != stack.stackBottom) {

            System.out.println("關(guān)注公眾號(hào)：Java3y：" + stackTop.data);

            stackTop = stackTop.next;
        }


    }

測(cè)試：

    public static void main(String[] args) {

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

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

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


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

        traverse(stack);

    }

結(jié)果：

這就符合了先進(jìn)后出的特性了～

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

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

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

            System.out.println("關(guān)注公眾號(hào)：Java3y---->該棧不為空");

        }

    }

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

將棧頂?shù)脑氐闹羔?指向下一個(gè)節(jié)點(diǎn))賦值給棧頂指針(完成出棧)

    /**
     * 出棧(將棧頂?shù)闹羔樦赶蛳乱粋€(gè)節(jié)點(diǎn))
     * @param stack
     */
    public static void popStack(Stack stack) {

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

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

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

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

        }
    }

測(cè)試出棧：

多次出棧：

當(dāng)時(shí)學(xué)C的時(shí)候需要釋放內(nèi)存資源，可是Java不用呀，所以棧頂指向棧底，就清空棧了

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

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

數(shù)據(jù)結(jié)構(gòu)的隊(duì)列長(zhǎng)的是這個(gè)樣子：

其實(shí)隊(duì)列非常好理解，我們將隊(duì)列可以看成小朋友排隊(duì)

隊(duì)尾的小朋友到指定的地點(diǎn)了-->出隊(duì)

有新的小朋友加入了-->入隊(duì)

相對(duì)于棧而言，隊(duì)列的特性是：先進(jìn)先出

先排隊(duì)的小朋友肯定能先打到飯！

隊(duì)列也分成兩種：

靜態(tài)隊(duì)列(數(shù)組實(shí)現(xiàn))

動(dòng)態(tài)隊(duì)列(鏈表實(shí)現(xiàn))

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

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

這次我們使用的是數(shù)組來實(shí)現(xiàn)靜態(tài)隊(duì)列，因此我們可以這樣設(shè)計(jì)：

public class Queue {


    //數(shù)組
    public int [] arrays;

    //指向第一個(gè)有效的元素
    public int front;

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

}

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

由于我們是循環(huán)隊(duì)列，所以front和rear值會(huì)經(jīng)常變動(dòng)，我們得把front和rear的值限定在一個(gè)范圍內(nèi)，不然會(huì)超出隊(duì)列的長(zhǎng)度的。

有這么一個(gè)算法：rear=（rear+1)%數(shù)組長(zhǎng)度

比如rear的下標(biāo)是2，數(shù)組的長(zhǎng)度是6，往后面移一位是3，那么rear = （rear+1) % 6，結(jié)果還是3

此時(shí)隊(duì)列為空，分配了6個(gè)長(zhǎng)度給數(shù)組(只能裝5個(gè)實(shí)際的數(shù)字，rear指向的是無效的位置的)

    public static void main(String[] args) {

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

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

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

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

            System.out.println("關(guān)注公眾號(hào)：Java3y--->此時(shí)隊(duì)列滿了！");
            return true;
        } else {
            System.out.println("關(guān)注公眾號(hào)：Java3y--->此時(shí)隊(duì)列沒滿了！");
            return false;
        }
    }

判斷該隊(duì)列是否滿了

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

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

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

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

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

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

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

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

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

        while (i != queue.rear) {

            System.out.println("關(guān)注公眾號(hào)：Java3y--->" + queue.arrays[i]);

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

    }

隊(duì)列沒滿時(shí)：

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

只要rear和front指針指向同一個(gè)位置，那該隊(duì)列就是空的了

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

出隊(duì)的邏輯也非常簡(jiǎn)單：

判斷該隊(duì)列是否為null

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

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

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


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

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

        }


    }

結(jié)果：

數(shù)據(jù)結(jié)構(gòu)的棧和隊(duì)列的應(yīng)用非常非常的多，這里也只是最簡(jiǎn)單的入門，理解起來也不困難。

棧：先進(jìn)后出

隊(duì)列：先進(jìn)先出

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

想要更加深入數(shù)據(jù)結(jié)構(gòu)的同學(xué)就得去翻閱相關(guān)的書籍咯～這僅僅是冰山一角

如果文章有錯(cuò)的地方歡迎指正，大家互相交流。習(xí)慣在微信看技術(shù)文章，想要獲取更多的Java資源的同學(xué)，可以關(guān)注微信公眾號(hào):Java3y