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

[[199073]]

小妖·Android開發

棧和隊列介紹

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

鏈式存儲棧分析

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

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

代碼實現

接下來看看如何用Java代碼實現：

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

/** 
     * 數據出棧操作 
     * @return 
     */ 
    public T pop() { 
        T result = top.data; 
        if (top.hasNext()) { 
            top = top.next; 
        } 
        return result; 
    } 
    //使用內部類構建結點 
    private class Node<T> { 
        T data; //使用泛型來定義數據域 
        Node<T> next; //定義下一個結點 
 
        /** 
         * 無參構造方法中初始化棧底部，為棧添加末端哨兵 
         */ 
        Node() { 
            data = null; 
            next = null; 
        } 
 
        /** 
         * 通過帶參構造方法來構造每一個添加的結點對象 
         * @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 + 
                    '}'; 
        } 
    } 
 
} 

從代碼中可以看到，在這里使用了泛型來保證入棧數據類型的通用，結點采用了內部類的方式來構造，因為其私有性，所以是可以保證數據安全的。基礎不太好的同學可能會比較懵逼，不太明白這個鏈式是鏈到哪里的，所以小妖在入棧操作時將棧內信息打印了出來，相信各位一看就明白了。如下圖：

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

【寫在***】

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

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

【51CTO原創稿件，合作站點轉載請注明原文作者和出處為51CTO.com】