Java的棧與隊列實現(xiàn)代碼解析

更新時間：2025年04月23日 14:54:54 作者：freedom　?

棧是常見的線性數(shù)據(jù)結(jié)構(gòu),棧的特點是以先進后出的形式,后進先出,先進后出,分為棧底和棧頂,棧應用于內(nèi)存的分配,表達式求值,存儲臨時的數(shù)據(jù)和方法的調(diào)用等,本文給大家介紹Java的棧與隊列實現(xiàn)代碼,感興趣的朋友一起看看吧

棧的概念（Stack）

棧是常見的線性數(shù)據(jù)結(jié)構(gòu)，棧的特點是以先進后出的形式，后進先出，先進后出，分為棧底和棧頂
棧應用于內(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都為空才為空
    }
}