Java實現(xiàn)鏈棧的示例代碼
前言
線性表和棧都是我們常用的數(shù)據(jù)結(jié)構(gòu)，?？梢钥闯梢环N特殊狀態(tài)的線性表，棧的實現(xiàn)，一般都是使用線性表來實現(xiàn)，線性表分為順序表和鏈表，使用線性表中的順序表來實現(xiàn)棧時這種棧被稱為順序棧，相應的使用線性表中的鏈表來實現(xiàn)棧時這種棧被稱為鏈棧，但是需要說明的是，雖然棧是一種特殊的線性表，但是棧和線性表并不是一種數(shù)據(jù)結(jié)構(gòu)。這篇文章總結(jié)如何使用鏈式存儲結(jié)構(gòu)來實現(xiàn)棧，也就是鏈棧的實現(xiàn)。如果想要了解另一種棧（順序棧）的實現(xiàn)請看這里：順序棧的實現(xiàn)
一、實現(xiàn)過程
這部分總結(jié)鏈棧的實現(xiàn)過程，以及對應方法實現(xiàn)思路，這里提供一個棧的頂層接口IStack,用以聲明棧中所應實現(xiàn)的方法，提供該接口不僅可供鏈棧使用，順序棧也是可以使用的。下面鏈棧的實現(xiàn)通過實現(xiàn)ISstack接口來完成，詳細步驟如下。
1.提供棧接口：IStack
該接口定義了棧必須實現(xiàn)的接口，有如下方法：
/**
* 該接口是：棧的頂層接口
* 他的實現(xiàn)類會有：順序棧、鏈棧
*
* 棧：先入后出
*/
public interface IStack {
void clear();//清空方法
boolean isEmpty();//判空方法
int length();//棧深度方法
Object peek();//取棧頂元素并返回值，若棧為空，返回null
void push(Object object) throws Exception;//入棧操作,元素進入棧頂
Object pop();//將棧頂元素出站
}
2.提供結(jié)點類：Node
鏈棧的實現(xiàn)使用單鏈表來實現(xiàn)，因此我們需要提供一個結(jié)點的信息類，該結(jié)點是鏈表的存儲單元，他包含有兩個屬性，一個是數(shù)據(jù)域用以存儲數(shù)據(jù)，一個是指針域用以指向下一個結(jié)點，這兩個屬性這里都聲明成了public，也可以聲明成private，這樣就需要使用get、set方法來操作這些屬性了，這里為了方便使用public來聲明這兩個屬性。
public class Node {
public Object object;
public Node next;
public Node(){
}
public Node(Object object){
this.object = object;
}
public Node(Node next){
this.next = next;
}
public Node(Object object,Node next){
this.object = object;
this.next = next;
}
@Override
public String toString() {
return "Node{" +
"object=" + object +
", next=" + next +
'}';
}
}
3.提供鏈棧的實現(xiàn)類：LinkedStack
使用鏈式存儲結(jié)構(gòu)實現(xiàn)的棧被稱為鏈棧，這里使用單鏈表的數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)，該單鏈表的實現(xiàn)可以使用帶頭結(jié)點和不帶頭結(jié)點兩種方式。兩種實現(xiàn)沒有太大區(qū)別，這里使用不帶頭結(jié)點的方式來實現(xiàn)。不帶頭結(jié)點那我們需要提供一個首結(jié)點，首結(jié)點需要在棧創(chuàng)建時被初始化，代碼如下：
/**
*
* @author pcc
* @version 1.0.0
* @className LinkedStack:該棧類，使用鏈式存儲結(jié)構(gòu)實現(xiàn)，是鏈棧，這里使用單鏈表的方式實現(xiàn)
* @date 2021-04-20 16:32
*
* 棧的特點是先進后出：
* 因此我們可以使用頭插法，每次在頭部插入，出棧時只需獲取鏈表的頭結(jié)點即可。
*
* 鏈棧與順序棧的區(qū)別：
* 順序棧底層是數(shù)組，因此必須初始化一個數(shù)組的容量，也就是棧的容量，鏈棧則無需此操作
* 對比鏈棧和順序棧的實現(xiàn)，可以發(fā)現(xiàn)入棧和出戰(zhàn)方法的時間復雜度都是O（1），效率上沒有區(qū)別，但是順序棧占用的空間會相對更多
* 一些，順序棧是通過指針指向假設的棧頂，其他元素其實依然存在，但鏈棧的棧頂之前的元素會被垃圾回收，因此鏈棧的實現(xiàn)綜合時間和
* 空間來看，更優(yōu)秀一些。
*/
public class LinkedStack implements IStack {
//這是首結(jié)點
Node node;
public LinkedStack(){
node = new Node();
}
}
4.提供清空(clear)、判空(isEmpty)、棧深度(length)等方法
這些方法的實現(xiàn)都比較簡單，都一起寫了，鏈表的起始就是首結(jié)點，因此我們只需要將首結(jié)點的數(shù)據(jù)域與指針域置空即可實現(xiàn)鏈棧的清空。判空也只需要判斷首結(jié)點的數(shù)據(jù)域是否有值即可。棧深度則需要遍歷鏈表的長度了（也可以設置一個整型，每次入棧操作時整型加1，這里通過遍歷實現(xiàn)）。
下面是三個方法的實現(xiàn)：
@Override
public void clear() {
node.next = null;
node.object = null;
}
@Override
public boolean isEmpty() {
return node.object==null?true:false;
}
@Override
public int length() {
if(node.object==null)
return 0;
int j= 1;
Node nodeNew = node;
while(nodeNew.next!=null){
j++;
nodeNew = nodeNew.next;
}
return j;
}
5.提供入棧的方法：push(Object object)
入棧方法當然就是將數(shù)據(jù)元素放入棧頂?shù)牟僮髁?。首先我們應該知道對于鏈表每次獲取鏈表首結(jié)點的時間復雜度是O(1),獲取尾結(jié)點的時間復雜度是O(n)，因此很明顯我們使用鏈表作為棧的數(shù)據(jù)結(jié)構(gòu)時，應該使用頭插法來將數(shù)據(jù)存入鏈棧，這樣我們每次插入的棧頂元素都在鏈表的開始位置，獲取該結(jié)點的時間復雜度是O(1)。所以我們使用頭插法實現(xiàn)數(shù)據(jù)的存儲，代碼如下：
@Override
public void push(Object object) throws Exception {
if(node.object==null){
node.object = object;
return;
}
//頭插法
node = new Node(object,node);
}
6.提供獲取棧頂元素方法：peek()
該方法只是獲取棧頂元素的信息，并不會將該元素出棧，因為棧頂元素就是鏈表的首結(jié)點，因此我們只需要返回首結(jié)點的數(shù)據(jù)域即可，代碼實現(xiàn)如下：
@Override
public Object peek() {
return node.object;
}
7.提供出棧方法：pop()
棧是一種先入后出的數(shù)據(jù)結(jié)構(gòu)，每次出棧的只能是最后進入的數(shù)據(jù)元素，因此我們每次只需要將鏈棧的首結(jié)點出棧即可，代碼實現(xiàn)如下：
@Override
public Object pop() {
if(node.object==null)
return null;
Node tem = node;
node = node.next==null?new Node():node.next;
return tem.object;
}
8.提供鏈棧的完整實現(xiàn)代碼
/**
*
* @author pcc
* @version 1.0.0
* @className LinkedStack:該棧類，使用鏈式存儲結(jié)構(gòu)實現(xiàn)，是鏈棧，這里使用單鏈表的方式實現(xiàn)
* @date 2021-04-20 16:32
*
* 棧的特點是先進后出：
* 因此我們可以使用頭插法，每次在頭部插入，出棧時只需獲取鏈表的頭結(jié)點即可。
*
* 鏈棧與順序棧的區(qū)別：
* 順序棧底層是數(shù)組，因此必須初始化一個數(shù)組的容量，也就是棧的容量，鏈棧則無需此操作
* 對比鏈棧和順序棧的實現(xiàn)，可以發(fā)現(xiàn)入棧和出戰(zhàn)方法的時間復雜度都是O（1），效率上沒有區(qū)別，但是順序棧占用的空間會相對更多
* 一些，順序棧是通過指針指向假設的棧頂，其他元素其實依然存在，但鏈棧的棧頂之前的元素會被垃圾回收，因此鏈棧的實現(xiàn)綜合時間和
* 空間來看，更優(yōu)秀一些。
*/
public class LinkedStack implements IStack {
//這是首結(jié)點
Node node;
public LinkedStack(){
node = new Node();
}
@Override
public void clear() {
node.next = null;
node.object = null;
}
@Override
public boolean isEmpty() {
return node.object==null?true:false;
}
@Override
public int length() {
if(node.object==null)
return 0;
int j= 1;
Node nodeNew = node;
while(nodeNew.next!=null){
j++;
nodeNew = nodeNew.next;
}
return j;
}
@Override
public Object peek() {
return node.object;
}
@Override
public void push(Object object) throws Exception {
if(node.object==null){
node.object = object;
return;
}
//頭插法
node = new Node(object,node);
}
@Override
public Object pop() {
if(node.object==null)
return null;
Node tem = node;
node = node.next==null?new Node():node.next;
return tem.object;
}
}
二、測試鏈棧的相應方法
第一部分已經(jīng)詳細描述了鏈棧的實現(xiàn)過程，下面就來測試下這些方法是否可以正常使用吧。
1.測試入棧和出棧
創(chuàng)建一個測試類，然后往棧中插入五個數(shù)據(jù)元素，并依次出棧，若是出棧順序和入棧順序相反則說明是正確的了，測試結(jié)果如下圖：
可以看見輸出和輸入順序是相反的，結(jié)果滿足先入后出的預期。說明入棧與出棧的操作沒有問題。
2.驗證獲取棧頂元素方法peek、棧深度方法length、清空方法clear
還是往棧里面放入原先的五個元素，然后棧頂元素應該是“李四5”，長度應該是5，第二次長度應該是0，如果輸出內(nèi)容是這些說明棧的實現(xiàn)就沒有問題了，結(jié)果見下圖：
從輸出結(jié)果可以看到，這些方法實現(xiàn)并沒有問題，到這里棧常用的所有方法就已經(jīng)都實現(xiàn)了，方法的實現(xiàn)都很簡單，并沒有有難度的地方。
三、總結(jié)
鏈棧即使用鏈式存儲結(jié)構(gòu)實現(xiàn)的棧，其實這里的鏈棧就是一個特殊的單鏈表，一種限制了只能在首結(jié)點插入和刪除的單鏈表。這也是鏈表的本質(zhì)，無論是在何種語言中棧的實現(xiàn)要么是使用順序表要么是使用鏈表。無論使用哪種方法實現(xiàn)其實都很簡單。
1.順序棧與鏈棧的區(qū)別
順序棧與鏈棧作為兩種不同的棧的實現(xiàn)，他們肯定是有區(qū)別的，我們首先對比下入棧的操作，順序棧的入棧操作是直接根據(jù)頭指針將數(shù)據(jù)加入到數(shù)組指定的下標位置，鏈棧的入棧則是直接在首結(jié)點插入，他們的時間復雜度都是O(1),那么再對比下出棧的操作，順序棧是通過頭指針直接拿到下標為頭指針的數(shù)組元素，鏈棧則是直接將鏈表的頭部刪除返回，他們的時間復雜度也都是O(1),因此在入棧和出棧的操作上他們的性能并沒有什么區(qū)別，其他的區(qū)別還是要看不同的實現(xiàn)，若是實現(xiàn)的順序棧每次出棧后不刪除棧頂以后的元素，則順序棧會占用更多的空間，因為鏈棧每次出棧后他的數(shù)據(jù)元素與GC ROOTS就失去了連接，下次觸發(fā)GC時就會回收相應內(nèi)存。這種情況順序棧會占用更多的空間，鏈棧則更少，但是若是每次出棧時將順序棧頭指針以后的數(shù)據(jù)元素刪除，就不會有這種區(qū)別了，所以綜合來說順序棧與鏈棧在入棧和出棧的操作上性能沒有區(qū)別，但是其他場景的性能消耗，比如空間復雜度上則需要看順序棧與鏈棧的具體實現(xiàn)來定。
到此這篇關(guān)于Java實現(xiàn)鏈棧的示例代碼的文章就介紹到這了,更多相關(guān)Java鏈棧內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
SpringBoot2.0整合jackson配置日期格式化和反序列化的實現(xiàn)
這篇文章主要介紹了SpringBoot2.0整合jackson配置日期格式化和反序列化的實現(xiàn)，小編覺得挺不錯的，現(xiàn)在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2018-11-11
本文主要介紹了springboot使用注解獲取yml配置的兩種方法,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧2023-09-09
這篇文章主要介紹了解決JPA添加Pageable實現(xiàn)翻頁時報錯的問題，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2021-09-09
這篇文章主要給大家介紹了關(guān)于java語言基礎之標識符和命名規(guī)則的相關(guān)資料，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2021-03-03
詳解spring cloud使用Hystrix實現(xiàn)單個方法的fallback
本篇文章主要介紹了詳解spring cloud-使用Hystrix實現(xiàn)單個方法的fallback，小編覺得挺不錯的，現(xiàn)在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2018-01-01
Java Socket 編程是指使用 Java 語言進行網(wǎng)絡通信的過程，包括建立連接、傳輸數(shù)據(jù)和關(guān)閉連接等操作，本文將詳細介紹Java Socket編程，需要的朋友可以參考下2023-05-05
這篇文章主要介紹了Java Integer.ValueOf()的一些了解，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2020-05-05
這篇文章主要為大家詳細介紹了java實現(xiàn)上傳文件到FTP，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-06-06
詳解Java編程中protected修飾符與static修飾符的作用
這篇文章主要介紹了Java編程中protected關(guān)鍵字與static關(guān)鍵字的作用,是Java入門學習中的基礎知識,需要的朋友可以參考下2016-01-01
這篇文章主要介紹了SpringBoot項目整合Redis教程詳解，Redis?是完全開源的，遵守?BSD?協(xié)議，是一個高性能的?key-value?數(shù)據(jù)庫。感興趣的小伙伴可以參考閱讀本文2023-03-03