了解完算法的基本數據結構鍊表和數組後，我們就可以開始了解基于這些基本數據衍生出來的其它數據結構，如堆、棧、隊列等，今天詳細聊聊棧，其它文章參考

數組簡介

鍊表簡介

棧是一種線性結構，最常見的生活中的例子就是羽毛球筒

羽毛球筒隻開放一端入口，那麼先放入的球一定是在底部，最後放入的球在最頂部，拿球時先獲取的就是靠近頂部的球，隻有不停的獲取才能将底部的球拿到。

棧也就是這樣，隻能從一端入棧和出棧，這種順序我們稱為FILO（First In Last Out）先進後出，最早進入的元素稱為棧底，最後進入的元素我們稱為棧頂，如下

棧是鍊表和數組的基本數據的衍生結構，所以可以采用鍊表或者數據實現，具體思路如下

用數組來實現棧太簡單，我們可以參考之前數組的相關文章

數組簡介

入棧就是在數組的尾部插入元素不涉及到數組元素移動，出棧就是将數組尾部的元素清除，示意圖如下

入棧

出棧

實現代碼

/** *用數組實現棧 */ classMyStack1{ //數組的實際大小 privateintsize; privateObject[]arr; publicMyStack1(intcapacity){ arr=newObject[capacity]; size=0; } //入棧 publicvoidpush(Objectdata){ if(size==arr.length){ thrownewRuntimeException("超過棧的最大容量"); } arr[size]=data; size ; } //出棧 publicObjectpull(){ if(size==0){ thrownewRuntimeException("棧為空！"); } Objectdata=arr[size-1]; //恢複數組指定位置默認值 arr[size-1]=null; size--; returndata; } publicvoidshow(){ System.out.println("打印棧存放數據：" Arrays.toString(arr)); } }

鍊表實現棧同樣是尾部指針的移動，如下是鍊表實現的示意圖

入棧就是将原隊尾的next指針指向新節點即可，而出棧就是将原隊尾節點的上一個節點的next指針指向null。

入棧

出棧

實現代碼如下

/** *用鍊表實現棧 */ classMyStack2{ //鍊表元素個數 privateintsize; //頭節點 privateNodehead; //尾節點 privateNodelast; //入棧 publicvoidpush(Objectdata){ Nodenode=newNode(data); if(size==0){ head=node; last=node; }else{ last.next=node; last=node; } size ; } //出棧 publicObjectpull(){ if(size==0){ thrownewRuntimeException("棧數據為空"); } Objectdata=last.data; if(size==1){ head=null; last=null; }else{ //獲取倒數第二個節點 Nodeindex=getIndex(size-2); index.next=null; last=index; } size--; returndata; } //獲取指定下标的元素從0開始 publicNodegetIndex(intindex){ if(index<0||index>=size){ thrownewRuntimeException("數組下标異常"); } Nodetemp=head; for(inti=0;i<index;i ){ temp=temp.next; } returntemp; } publicvoidshow(){ Nodetemp=head; while(temp!=null){ System.out.println(temp); temp=temp.next; } } } classNode{ //數據 Objectdata; //下一個節點指針 Nodenext; publicNode(Objectdata){ this.data=data; next=null; } @Override publicStringtoString(){ return"Node{" "data=" data ",next=" next '}'; } }

從操作代碼可以看出，無論棧的實現方式是采用數組還是鍊表，入棧出棧都非常簡單僅僅是一個元素的移動，所以入棧和出棧操作時間複雜度都為O(1)。