【51CTO.com原創(chuàng)稿件】小妖畢業(yè)于重慶郵電大學(xué)計算機系，目前是一枚小小Android移動應(yīng)用開發(fā)程序員，愛生活，愛女朋友，沒事的時候還愛玩兒游戲，愛死磕。目前人生目標：賺錢買房買車娶媳婦兒。

[[199073]]

小妖·Android開發(fā)

棧和隊列介紹

學(xué)過計算機編程基礎(chǔ)的朋友都知道計算機中最常見的數(shù)據(jù)結(jié)構(gòu)棧和隊列，這種線性表結(jié)構(gòu)之所以很常見，正是因為它們簡單卻強大的功能特性是很多算法的基礎(chǔ)構(gòu)成。大三時小妖在北京一次實習(xí)面試中，面試官問過他一個問題，“怎么樣用棧來實現(xiàn)一個隊列？”當時他陷入了一個誤區(qū)，認為面試官說的棧是指一個棧，由于棧的先入后出的特性，所以一個棧來完成隊列的功能在概念上是不可能的。俗話說，一個棧不行，那就兩個棧。OK，答對了，確實是至少需要兩個棧。言歸正傳，既然棧和隊列的應(yīng)用如此廣泛，那么怎么通過代碼來實現(xiàn)他們呢？很多童鞋可能會說，這還不簡單么？用集合或者數(shù)組，so easy！那么，如果為了提高執(zhí)行效率，不允許使用集合或者數(shù)組呢？下面，就由小妖來為大家小小的剖析一下吧！

鏈式存儲棧分析

棧的概念，這里就不再多說了，不清楚的童鞋請自行百度。其先入后出的特性確實有很多的實現(xiàn)方式。如題，我們這里將實現(xiàn)鏈式存儲，何為鏈式存儲呢？如下圖：

鏈式存儲的基本單位是Node（結(jié)點），在一個結(jié)點中，分為數(shù)據(jù)區(qū)和指針域，通過指針域指向下一個結(jié)點來將各個結(jié)點相連接。由于鏈式的特性，插入和刪除鏈中的某一個結(jié)點（除鏈頭和尾之外的其他結(jié)點）相對而言是消耗比較大的，但是用來實現(xiàn)棧或者隊列是極好的。對于棧結(jié)構(gòu)來說，數(shù)據(jù)的入棧和出棧以及判斷是否到達棧底等方法是必不可少的。

代碼實現(xiàn)

接下來看看如何用Java代碼實現(xiàn)：

/** 
 * Created by lxh on 2017/8/1. 
 * QQ-632671653 
 * 自定義鏈式存儲棧 
 */ 
public class LinkStack<T> { 
 
 
    private Node<T> top = new Node<>();//初始化棧頂結(jié)點 
 
    /** 
     * 數(shù)據(jù)入棧操作 
     * @param data 
     */ 
    public void push(T data) { 
        top = new Node<>(data, top); 
        System.out.println(top.toString()); 
    } 

/** 
     * 數(shù)據(jù)出棧操作 
     * @return 
     */ 
    public T pop() { 
        T result = top.data; 
        if (top.hasNext()) { 
            top = top.next; 
        } 
        return result; 
    } 
    //使用內(nèi)部類構(gòu)建結(jié)點 
    private class Node<T> { 
        T data; //使用泛型來定義數(shù)據(jù)域 
        Node<T> next; //定義下一個結(jié)點 
 
        /** 
         * 無參構(gòu)造方法中初始化棧底部，為棧添加末端哨兵 
         */ 
        Node() { 
            data = null; 
            next = null; 
        } 
 
        /** 
         * 通過帶參構(gòu)造方法來構(gòu)造每一個添加的結(jié)點對象 
         * @param data 
         * @param next 
         */ 
        public Node(T data, Node<T> next) { 
            this.data = data; 
            this.next = next; 
        } 
 
        /** 
         * 判斷是否到達棧底 
         * @return 
         */ 
        boolean hasNext() { 
            return data != null && next != null; 
        } 
 
        @Override 
        public String toString() { 
            return "Node{" + 
                    "data=" + data + 
                    ", next=" + next + 
                    '}'; 
        } 
    } 
 
} 

從代碼中可以看到，在這里使用了泛型來保證入棧數(shù)據(jù)類型的通用，結(jié)點采用了內(nèi)部類的方式來構(gòu)造，因為其私有性，所以是可以保證數(shù)據(jù)安全的?；A(chǔ)不太好的同學(xué)可能會比較懵逼，不太明白這個鏈式是鏈到哪里的，所以小妖在入棧操作時將棧內(nèi)信息打印了出來，相信各位一看就明白了。如下圖：

相信通過信息圖大家明白了，這個鏈式存儲棧是通過在結(jié)點對象中遞歸添加結(jié)點對象來構(gòu)成了一個一個結(jié)點的鏈接，體現(xiàn)在字符集上則是一層一層的對象嵌套（由于采用了Java語言來編寫，沒有C中的指針，所以采用此方法來代替指針）。通過末端結(jié)點的哨兵，當出棧時數(shù)據(jù)集為null 則可以判斷出棧中數(shù)據(jù)出棧完畢了。

【寫在***】

同行中流傳著這樣一句話：不要重復(fù)的造輪子。但是小妖覺得，即便不需要你去造輪子，但是你也得明白輪子到底是怎樣造出來。如果你只會調(diào)用API，那么你將失去競爭力。

如果你也愿意分享你的故事，請加51CTO開發(fā)者QQ交流群 542270018聯(lián)系群主小官，期待你精彩的故事！

【51CTO原創(chuàng)稿件，合作站點轉(zhuǎn)載請注明原文作者和出處為51CTO.com】