Java的棧與隊列實現(xiàn)代碼解析
棧的概念（Stack）
棧是常見的線性數(shù)據(jù)結(jié)構(gòu)，棧的特點是以先進后出的形式，后進先出，先進后出，分為棧底和棧頂
棧應(yīng)用于內(nèi)存的分配，表達式求值，存儲臨時的數(shù)據(jù)和方法的調(diào)用等。
例如這把槍，第一發(fā)子彈是最后發(fā)射的，第一發(fā)子彈在棧底，而最新安裝上去的子彈在棧的頂部，只有將上面的子彈打完（棧頂?shù)臄?shù)據(jù)走完），最后一發(fā)子彈才會射出
棧的實現(xiàn)
棧的實現(xiàn)是基于簡單的數(shù)組形成的，我們可以將它想象成連續(xù)的數(shù)組，而棧的順序是由后放到前放
模擬實現(xiàn)棧的方法:push（放入一個元素到棧中)
pop(提取棧頂?shù)囊粋€元素，并將在其棧中消除)
peek(查看棧頂?shù)脑?
size(查看棧中的大小)
empty(棧中是否為空)
full(棧是否滿了)
代碼
import java.util.Arrays;
public class MyStack implements IStack {
private int[] elem;
private int top;//數(shù)組的棧頂,以及數(shù)組棧中存放元素的數(shù)量
private static final int DEFAULT_CAPACITY = 10;//這里是初始容量
public MyStack() {
elem = new int[DEFAULT_CAPACITY];
top = -1;//數(shù)組下標從0開始
}
@Override
public void push(int item) {
if (full()) {
//如果滿了就擴容
elem = Arrays.copyOf(elem, 2 * elem.length);
}
elem[++top] = item;
}
@Override
public int pop() throws RuntimeException {
try {
if (empty()) {
throw new RuntimeException("棧為空");
}
} catch (RuntimeException e) {
e.printStackTrace();
}
return elem[top--];//return返回后刪除棧頂?shù)脑?
}
@Override
public int peek() {
if (empty()) {
throw new RuntimeException("棧為空");
}
return elem[top];//返回棧頂元素
}
@Override
public int size() {
return top+1;//去除數(shù)組0
}
@Override
public boolean empty() {
return top == -1;
}
@Override
public boolean full() {
return top == elem.length;//count==當前的elem的總長度為true
}
}隊列（Queue）
隊列是由先進先出的線性數(shù)據(jù)結(jié)構(gòu)，采用的是先進先出，后進后出，如果要插入元素的話就是從入隊尾巴方向插入，而刪除作為出隊要在頭尾刪除。
隊列的方法
模擬實現(xiàn)隊列(雙鏈表實現(xiàn))
public class MyQueue implements IQueue{
static class Queue{
public int elem;
public Queue next;
public Queue prev;
public Queue(int elem) {
this.elem = elem;
}
}
public Queue head;
public Queue last;
public int size=0;
@Override
public void offer(int val) {
Queue queue = new Queue(val);
if (this.head == null) {
this.head = queue;
this.last = queue;
++size;
return;
}
this.last.next=queue;
this.last.prev=this.head;
this.last=last.next;
++size;
}
@Override
public int poll() {
if(this.head==null){
throw new RuntimeException("沒有要丟掉的隊列");
}
Queue cur =this.head;
if(this.head.next==null){
return -1;
}
this.head=this.head.next;
this.head.prev=null;
size--;
return cur.elem;
}
@Override
public int peek() {
if(this.head!=null){
return this.head.elem;
}
return 0;
}
@Override
public int size() {
return size;
}
}循環(huán)隊列（循環(huán)數(shù)組實現(xiàn)）
數(shù)組實現(xiàn)隊列的循環(huán)需要引入一個公式（目前的下標值+1）%當前數(shù)組的長度
(index+1)%array.length,下標值從0開始少一個數(shù)，當index+1就是當前的總長度時，公式后的值一定為下標0。
private int[] array;
private int front;
private int rear;
public MyCircularQueue(int k) {
array=new int[k+1];
front=0;//初始位置
rear=0;
}
public boolean enQueue(int value) {
//入列
if(isFull()){
//這里如果容量已經(jīng)滿了，需要先刪除后在進行插入
return false;
}
array[rear]=value;//rear下標獲取元素
rear=(rear+1)%array.length;//rear最終循環(huán)為0下標
return true;
}
public boolean deQueue() {
//出列
if(isEmpty()){
//為空返回false
return false;
}
front=(front+1)%array.length;//front只需要往后走
return true;
}
public int Front() {
if(isEmpty()){
return -1;
}
return array[front];
}
public int Rear() {
if(isEmpty()){
return -1;
}
//這里三木操作符判斷是否為0如果為0，將rear回退到最后一個位置，不為0則-1
int temp = (rear==0)?array.length-1:rear-1;
return array[temp];
}
public boolean isEmpty() {
return front==rear;
}
public boolean isFull() {
return (rear+1)%array.length==front;
}
}用隊列實現(xiàn)棧
因為隊列是先進先出的，而我們的棧是先進后出的，兩種線性結(jié)構(gòu)的關(guān)系是顛倒的，一個隊列是不能完成的，我們需要兩個隊列互相工作來完成
輔助隊列先獲取數(shù)值，保證輔助隊列是最后一個拿到值的，然后將主隊列的值給到輔助隊列，在交換兩個隊列的數(shù)值，因為隊列關(guān)系先進先出，每一次最后一個值就是隊列先出的數(shù)值
主隊列不為空，將主隊列的元素都poll出放到輔助棧中，使用一個tmp來將主隊列（這里主隊列已經(jīng)遍歷完）和輔助隊列交換
Queue<Integer> q1;//主隊列
Queue<Integer> q2;//輔助隊列
public MyStack() {
q1=new LinkedList<>();//構(gòu)造方法
q2=new LinkedList<>();
}
public void push(int x) {
q2.offer(x);
while(!q1.isEmpty()){//主隊列不為空，則將主隊列出列給到輔助隊列
q2.offer(q1.poll());
}
//走到這里主隊列是為空
Queue tmp=q1;
q1=q2;
q2=tmp;
//將兩個隊列交換
}
public int pop() {
return q1.poll();
}
public int top() {
return q1.peek();
}
public boolean empty() {
return q1.isEmpty();
}
}用棧來實現(xiàn)隊列
棧來實現(xiàn)隊列，棧是先進后出的順序，而隊列是先進先出的順序
將push都放到a棧中當我們peek或者是要刪除的時候，我們都將a棧的元素pop給b棧，這樣b棧已經(jīng)有了我們的元素
但是我們還需要考慮的是丟掉元素后如果在一起添加元素到a棧呢，這里我們給一個條件，如果b的棧不為空時，我們?nèi)匀挥胋棧的隊列
如果a為空，這兩個棧都是空的說明沒有元素直接返回-1，如果a不為空的話且b沒有新的元素b繼續(xù)捕獲新的a棧中所有的元素
class MyQueue {
Stack<Integer> A;
Stack<Integer> B;
public MyQueue() {
A=new Stack<>();
B=new Stack<>();
}
public void push(int x) {
A.push(x);
}
public int pop() {
int check=peek();
B.pop();
return check;
}
public int peek() {
//先判斷b是否是空的，如果不是空的直接返回，是空才可以往下走
if(!B.isEmpty())return B.peek();
//因為b還不是空的，所以不需要將a棧放到b中
if(A.isEmpty())return -1;
while(!A.isEmpty()){
B.push(A.pop());//將所有的a放到b中
}
return B.peek();
}
public boolean empty() {
return A.isEmpty()&&B.isEmpty();
//a和b都為空才為空
}
}總結(jié)
棧分為棧頂和棧底，最先進的為棧底，最后進的為棧頂。
隊列分為隊頭和隊尾，最先進的為隊頭，最后進的為隊尾。
到此這篇關(guān)于Java的棧與隊列實現(xiàn)代碼解析的文章就介紹到這了,更多相關(guān)java棧和隊列內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
本文主要介紹了SpringBoot實現(xiàn)反向代理的示例代碼，文中通過示例代碼介紹的非常詳細，對大家的學(xué)習或者工作具有一定的參考學(xué)習價值，需要的朋友們下面隨著小編來一起學(xué)習學(xué)習吧2023-06-06
本篇文章主要介紹了spring @profile注解的使用方法，小編覺得挺不錯的，現(xiàn)在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2017-10-10
在項目開發(fā)地過程中經(jīng)常會用到字典存儲某些可配置的值，但相應(yīng)的也會給開發(fā)帶來復(fù)雜度，比如數(shù)據(jù)庫存儲的值為字典值：0，1,2,3這種類型的值，但是前端頁面卻需要展示為 啟動、禁用、刪除 等中文狀態(tài)，下面我們來看兩種解決方案2022-06-06
Spring?Boot?中實現(xiàn)?WebSocket?集群思路詳解
本文介紹了如何在SpringBoot中實現(xiàn)WebSocket集群處理,解決了會話共享和消息同步問題,通過分布式存儲（Redis）和消息隊列（RedisPub/Sub）實現(xiàn)跨節(jié)點通信,感興趣的朋友跟隨小編一起看看吧2025-12-12
在本篇文章里小編給大家整理的是一篇關(guān)于java迭代器和for循環(huán)優(yōu)劣詳解內(nèi)容，對此有興趣的朋友們可以學(xué)習參考下。2021-01-01
HashMap實現(xiàn)保存兩個key相同的數(shù)據(jù)
這篇文章主要介紹了HashMap實現(xiàn)保存兩個key相同的數(shù)據(jù)操作，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2021-06-06
這篇文章主要介紹了Mysql存儲java對象實例詳解的相關(guān)資料,需要的朋友可以參考下2016-11-11
Springboot下RedisTemplate的兩種序列化方式實例詳解
這篇文章主要介紹了Springboot下RedisTemplate的兩種序列化方式,通過定義一個配置類，自定義RedisTemplate的序列化方式，結(jié)合實例代碼給大家介紹的非常詳細，對大家的學(xué)習或工作具有一定的參考借鑒價值，需要的朋友可以參考下2022-09-09
這篇文章主要介紹了Java的Map中computeIfAbsent方法詳解,在jdk1.8中Map接口新增了一個computeIfAbsent方法,這是Map接口中的默認實現(xiàn)該方法是首先判斷緩存Map中是否存在指定的key的值,如果不存在,會調(diào)用mappingFunction(key)計算key的value,需要的朋友可以參考下2023-11-11
基于SpringBoot+Redis實現(xiàn)分布式鎖
本文主要介紹了基于SpringBoot+Redis實現(xiàn)分布式鎖，文中通過示例代碼介紹的非常詳細，對大家的學(xué)習或者工作具有一定的參考學(xué)習價值，需要的朋友們下面隨著小編來一起學(xué)習學(xué)習吧2023-05-05