教你怎么用Java數組和鏈表實現棧
一、何為棧?
棧(stack)又名堆棧,它是一種運算受限的線性表。限定僅在表尾進行插入和刪除操作的線性表。這一端被稱為棧頂,相對地,把另一端稱為棧底。向一個棧插入新元素又稱作進棧、入?;驂簵?,它是把新元素放到棧頂元素的上面,使之成為新的棧頂元素;從一個棧刪除元素又稱作出?;蛲藯?,它是把棧頂元素刪除掉,使其相鄰的元素成為新的棧頂元素。
??梢灶惐瘸涩F實生活中的彈夾或者羽毛球桶
二、用數組實現棧
用數組模擬棧的思路分析如圖:
1.定義一個top變量(指針)表示棧頂初始化為-1.
2.定義一個變量來記錄棧的大小。
3.入棧操作有數據加入到棧中:top++; arr[top]=value;
4.出棧操作: int value=arr[top]; top–; return value;
下面看完整代碼示例:
class Stack{ public int maxsize;//棧的大小 public int top=-1;//棧頂 public int[] arr; public Stack(int maxsize) { this.maxsize = maxsize; arr=new int[maxsize]; } //判斷棧是否為空 public boolean isEmpty(){ return top==-1; } //判斷棧是否滿 public boolean isFull(){ return top==maxsize-1; } //添加一個元素 public void push(int value){ if(isFull()){ throw new RuntimeException("棧滿"); } top++; arr[top]=value; } //彈出一個元素 public int pop(){ if(isEmpty()) throw new RuntimeException("???); int value=arr[top]; top--; return value; } //遍歷棧中的元素 public void traverse(){ if (isEmpty()){ return; } //需要從棧頂開始顯示數據 for(int i = top; i >= 0 ; i--) { System.out.printf("stack[%d]=%d\n", i, arr[i]); } } }
入棧操作 top++;arr[top]=value;其實可以直接改寫為arr[++top]=value;
出棧操作可以將 int value=arr[top]; top–;return value;改為return arr[top–];
三、鏈表實現棧
思路分析:
入棧操作:用一個臨時節(jié)點保存當前棧頂節(jié)點,將入棧的新節(jié)點作為棧頂元素,并將next域指向原來的舊節(jié)點。 Node temp=top; top.setNext(temp);
出棧操作:先判斷棧是否為空,不為空則將top節(jié)點的數據返回,并將top指向top的下一個next域:top=top.getNext();
public class LinkedListStack<V> { static class Node<V>{ private V data; private Node<V> next; public V getData() { return data; } public void setData(V data) { this.data = data; } public Node<V> getNext() { return next; } public void setNext(Node<V> next) { this.next = next; } } public int stackSize;//棧內元素的個數 public Node<V> top;//棧頂元素 public LinkedListStack() { stackSize = 0; top = null; } //入棧 public void push(V element){ Node<V> temp=top; top=new Node<>(); top.setData(element); top.setNext(temp); stackSize++; } //出棧 public V pop(){ if (isEmpty()) throw new RuntimeException("empty stack"); V value=top.getData(); //棧頂指向下一個元素 top=top.getNext(); stackSize--; return value; } //查看棧頂元素 public V peek(){ return top.getData(); } //判斷是否為空 public boolean isEmpty(){ return stackSize==0; } //查看棧內元素個數 public int getStackSize(){ return stackSize; } }
四、測試
public class Test { public static void main(String[] args) { LinkedListStack<String> stack = new LinkedListStack<>(); stack.push("a"); stack.push("b"); stack.push("c"); System.out.println(stack.pop()); System.out.println(stack.peek()); System.out.println(stack.getStackSize()); } } 測試結果: c b 2
到此這篇關于教你怎么用Java數組和鏈表實現棧的文章就介紹到這了,更多相關Java數組和鏈表實現棧內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家!
相關文章
java后臺調用HttpURLConnection類模擬瀏覽器請求實例(可用于接口調用)
這篇文章主要介紹了java后臺調用HttpURLConnection類模擬瀏覽器請求實例,該實例可用于接口調用,具有一定的實用價值,需要的朋友可以參考下2014-10-10SpringBoot+Ajax+redis實現隱藏重要接口地址的方法
這篇文章主要介紹了SpringBoot+Ajax+redis實現隱藏重要接口地址,本篇文章主要講訴使用SpringBoot項目配合Ajax和redis實現隱藏重要接口地址,這里我以隱藏秒殺地址為例,需要的朋友可以參考下2024-03-03使用Springboot封裝好的發(fā)送post請求的工具類
本文介紹了在Springboot中封裝發(fā)送HTTP請求的工具類,并提供了普通的HTTP請求工具類代碼和Response類的使用示例,這些工具類可為開發(fā)者提供便利性和參考價值,幫助提高開發(fā)效率2024-09-09SpringMVC結合模板模式實現MyBatisPlus傳遞嵌套JSON數據
我們經常會遇到需要傳遞對象的場景,有時候,我們需要將一個對象的數據傳遞給另一個對象進行處理,但是又不希望直接暴露對象的內部結構和實現細節(jié),所以本文給大家介紹了SpringMVC結合模板模式實現MyBatisPlus傳遞嵌套JSON數據,需要的朋友可以參考下2024-03-03Spring?Boot集成Milvus快速入門demo示例詳解
Milvus是一種高性能向量數據庫,支持從筆記本到大型分布式系統(tǒng)的多環(huán)境運行,它以開源和云服務形式提供,是LFAI & Data Foundation的項目,采用Apache 2.0許可,Milvus特別支持高并行化和解耦的系統(tǒng)架構,使其能夠隨數據增長而擴展,支持各種復雜搜索功能,滿足企業(yè)級AI應用需求2024-09-09