挨踢部落故事匯(25):剖析鏈?zhǔn)酱鎯Ｅc代碼實(shí)現(xiàn)
原創(chuàng)【51CTO.com原創(chuàng)稿件】小妖畢業(yè)于重慶郵電大學(xué)計(jì)算機(jī)系，目前是一枚小小Android移動應(yīng)用開發(fā)程序員，愛生活，愛女朋友，沒事的時候還愛玩兒游戲，愛死磕。目前人生目標(biāo)：賺錢買房買車娶媳婦兒。
小妖·Android開發(fā)
棧和隊(duì)列介紹
學(xué)過計(jì)算機(jī)編程基礎(chǔ)的朋友都知道計(jì)算機(jī)中最常見的數(shù)據(jù)結(jié)構(gòu)棧和隊(duì)列，這種線性表結(jié)構(gòu)之所以很常見，正是因?yàn)樗鼈兒唵螀s強(qiáng)大的功能特性是很多算法的基礎(chǔ)構(gòu)成。大三時小妖在北京一次實(shí)習(xí)面試中，面試官問過他一個問題，“怎么樣用棧來實(shí)現(xiàn)一個隊(duì)列？”當(dāng)時他陷入了一個誤區(qū)，認(rèn)為面試官說的棧是指一個棧，由于棧的先入后出的特性，所以一個棧來完成隊(duì)列的功能在概念上是不可能的。俗話說，一個棧不行，那就兩個棧。OK，答對了，確實(shí)是至少需要兩個棧。言歸正傳，既然棧和隊(duì)列的應(yīng)用如此廣泛，那么怎么通過代碼來實(shí)現(xiàn)他們呢？很多童鞋可能會說，這還不簡單么？用集合或者數(shù)組，so easy！那么，如果為了提高執(zhí)行效率，不允許使用集合或者數(shù)組呢？下面，就由小妖來為大家小小的剖析一下吧！
鏈?zhǔn)酱鎯７治?/strong>
棧的概念，這里就不再多說了，不清楚的童鞋請自行百度。其先入后出的特性確實(shí)有很多的實(shí)現(xiàn)方式。如題，我們這里將實(shí)現(xiàn)鏈?zhǔn)酱鎯Γ螢殒準(zhǔn)酱鎯δ兀咳缦聢D：
鏈?zhǔn)酱鎯Φ幕締挝皇荖ode（結(jié)點(diǎn)），在一個結(jié)點(diǎn)中，分為數(shù)據(jù)區(qū)和指針域，通過指針域指向下一個結(jié)點(diǎn)來將各個結(jié)點(diǎn)相連接。由于鏈?zhǔn)降奶匦裕迦牒蛣h除鏈中的某一個結(jié)點(diǎn)（除鏈頭和尾之外的其他結(jié)點(diǎn)）相對而言是消耗比較大的，但是用來實(shí)現(xiàn)棧或者隊(duì)列是極好的。對于棧結(jié)構(gòu)來說，數(shù)據(jù)的入棧和出棧以及判斷是否到達(dá)棧底等方法是必不可少的。
代碼實(shí)現(xiàn)
接下來看看如何用Java代碼實(shí)現(xiàn)：
- /**
- * Created by lxh on 2017/8/1.
- * QQ-632671653
- * 自定義鏈?zhǔn)酱鎯?nbsp;
- */
- public class LinkStack<T> {
- private Node<T> top = new Node<>();//初始化棧頂結(jié)點(diǎn)
- /**
- * 數(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é)點(diǎn)
- private class Node<T> {
- T data; //使用泛型來定義數(shù)據(jù)域
- Node<T> next; //定義下一個結(jié)點(diǎn)
- /**
- * 無參構(gòu)造方法中初始化棧底部，為棧添加末端哨兵
- */
- Node() {
- data = null;
- next = null;
- }
- /**
- * 通過帶參構(gòu)造方法來構(gòu)造每一個添加的結(jié)點(diǎn)對象
- * @param data
- * @param next
- */
- public Node(T data, Node<T> next) {
- this.data = data;
- this.next = next;
- }
- /**
- * 判斷是否到達(dá)棧底
- * @return
- */
- boolean hasNext() {
- return data != null && next != null;
- }
- @Override
- public String toString() {
- return "Node{" +
- "data=" + data +
- ", next=" + next +
- '}';
- }
- }
- }
從代碼中可以看到，在這里使用了泛型來保證入棧數(shù)據(jù)類型的通用，結(jié)點(diǎn)采用了內(nèi)部類的方式來構(gòu)造，因?yàn)槠渌接行裕允强梢员ＷC數(shù)據(jù)安全的。基礎(chǔ)不太好的同學(xué)可能會比較懵逼，不太明白這個鏈?zhǔn)绞擎湹侥睦锏模孕⊙谌霔２僮鲿r將棧內(nèi)信息打印了出來，相信各位一看就明白了。如下圖：
【寫在***】
同行中流傳著這樣一句話：不要重復(fù)的造輪子。但是小妖覺得，即便不需要你去造輪子，但是你也得明白輪子到底是怎樣造出來。如果你只會調(diào)用API，那么你將失去競爭力。
如果你也愿意分享你的故事，請加51CTO開發(fā)者QQ交流群 542270018聯(lián)系群主小官，期待你精彩的故事！
【51CTO原創(chuàng)稿件，合作站點(diǎn)轉(zhuǎn)載請注明原文作者和出處為51CTO.com】
