1.棧

1.1 簡(jiǎn)介

什么是棧呢？大家可以把它想象成一個(gè)狹窄的盒子，我們往里面放東西，每次取出時(shí)，只能取出最后放進(jìn)去的(最上面一個(gè))，總結(jié)來(lái)講就是 “先進(jìn)后出”，如下圖：

特點(diǎn)：先進(jìn)后出，每次只能取得棧頂元素

1.2 棧的實(shí)現(xiàn)

思想：使用數(shù)組來(lái)實(shí)現(xiàn)棧
進(jìn)棧push時(shí)，依次往數(shù)組后追加元素即可（和前面講過(guò)的數(shù)組操作一樣）
在出棧pop時(shí)，我們每次都取最后一個(gè)元素

相關(guān)操作：進(jìn)棧push 、出棧pop 、獲取棧頂元素peek 、判斷為空isEmpty

代碼：

public class MyStack {//棧底層采用數(shù)組存儲(chǔ)int[] arr;public MyStack(){arr=new int[0];}//進(jìn)棧 (和數(shù)組的add一樣)public void push(int element){//初始化一個(gè)數(shù)組int[] newArr=new int[arr.length+1];for(int i=0;i<arr.length;i++){newArr[i]=arr[i];}newArr[arr.length]=element;arr=newArr;}//出棧-刪除數(shù)組最后一個(gè)元素并返回即可public int pop(){//判斷是否棧空，拋出異常if(arr.length==0){throw new RuntimeException("Stack is Empty!");}int element=arr[arr.length-1];int[] newArr=new int[arr.length-1];//遍歷新數(shù)組，賦值-處理arr最后一個(gè)值for(int i=0;i<newArr.length;i++){newArr[i]=arr[i];}//替換數(shù)組arr=newArr;//返回刪除的元素return element;}//查看棧頂元素public int peek(){//判斷是否棧空，拋出異常if(arr.length==0){throw new RuntimeException("Stack is Empty!");}return arr[arr.length-1];}//判斷棧是否為空public Boolean isEmpty(){return arr.length==0;} }

測(cè)試類(lèi)

public class TestStack {public static void main(String[] args) {MyStack myStack = new MyStack();myStack.push(1);myStack.push(2);myStack.push(3);System.out.println("棧頂元素為:"+myStack.peek());System.out.println("出棧了"+myStack.pop());System.out.println("出棧了"+myStack.pop());System.out.println(myStack.isEmpty());System.out.println("出棧了"+myStack.pop());System.out.println(myStack.isEmpty());} }

結(jié)果

棧頂元素為:3 出棧了3 出棧了2 false 出棧了1 true

2. 隊(duì)列

2.1 簡(jiǎn)介

隊(duì)列，聽(tīng)到這個(gè)詞大家就想到生活中的排隊(duì)吧，沒(méi)錯(cuò)，其實(shí)隊(duì)列就是排隊(duì)
排隊(duì)時(shí)，我們必須遵守先來(lái)排前面，后來(lái)排后面，并且前面的人優(yōu)先通過(guò)
(當(dāng)然vip除外哈，這里不錯(cuò)考慮)
隊(duì)列也一樣，正好和棧相反：“先進(jìn)先出”

特點(diǎn)：先進(jìn)先出 （和我們平時(shí)排隊(duì)一樣，排在前面就優(yōu)先）

2.2 隊(duì)列的實(shí)現(xiàn)

實(shí)現(xiàn)思想：

底層還是使用數(shù)組實(shí)現(xiàn)，和棧唯一不同是出棧每次取出數(shù)組第一個(gè)元素

主要操作：進(jìn)隊(duì)add 出隊(duì)pill 判斷是否為空isEmpty

代碼：

public class MyQueue {//隊(duì)列底層采用數(shù)組存儲(chǔ)int[] arr;public MyQueue(){arr=new int[0];}//進(jìn)棧 (和數(shù)組的add一樣)public void add(int element){//初始化一個(gè)數(shù)組int[] newArr=new int[arr.length+1];for(int i=0;i<arr.length;i++){newArr[i]=arr[i];}newArr[arr.length]=element;arr=newArr;}//出棧-刪除數(shù)組第一個(gè)元素并返回即可public int pill(){//判斷是否棧空，拋出異常if(arr.length==0){throw new RuntimeException("Queue is Empty!");}int element=arr[0];int[] newArr=new int[arr.length-1];//遍歷新數(shù)組，賦值-處理arr最后一個(gè)值for(int i=0;i<newArr.length;i++){newArr[i]=arr[i+1];}//替換數(shù)組arr=newArr;//返回刪除的元素return element;}//判斷棧是否為空public Boolean isEmpty(){return arr.length==0;} }

測(cè)試：

public class TestQueue {public static void main(String[] args) {MyQueue myQueue = new MyQueue();myQueue.add(1);myQueue.add(2);myQueue.add(3);System.out.println("出隊(duì)了："+myQueue.pill());System.out.println("出隊(duì)了："+myQueue.pill());System.out.println("出隊(duì)了："+myQueue.pill());System.out.println(myQueue.isEmpty());} }

結(jié)果：

出隊(duì)了：1 出隊(duì)了：2 出隊(duì)了：3 true 《新程序員》：云原生和全面數(shù)字化實(shí)踐50位技術(shù)專(zhuān)家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結(jié)

以上是生活随笔為你收集整理的【栈和队列】数据结构02-(java实现)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。