Java實現(xiàn)循環(huán)隊列、棧實現(xiàn)隊列、隊列實現(xiàn)棧的方法

更新時間：2026年03月17日 09:38:02 作者：祈安_

本文主要介紹了隊列、循環(huán)隊列、鏈式隊列、使用棧實現(xiàn)隊列以及使用隊列實現(xiàn)棧的數(shù)據(jù)結構及其實現(xiàn)方法,本文結合實例代碼給大家介紹的非常詳細,感興趣的朋友跟隨小編一起看看吧

一、隊列的介紹

隊列是一種常見的線性數(shù)據(jù)結構，遵循先進先出（FIFO，F(xiàn)irst In First Out）原則。也就是說，最先進入隊列的元素會最先被移除。

從結構上看，隊列通常包含兩個重要指針：隊頭（front）和隊尾（rear）。新元素總是從隊尾進入隊列，這個操作稱為入隊（enqueue）；而元素的刪除只發(fā)生在隊頭，這個操作稱為出隊（dequeue）。

根據(jù)實現(xiàn)方式不同，隊列主要有兩種常見形式。第一種是順序隊列，基于數(shù)組實現(xiàn)，優(yōu)點是結構簡單、訪問速度快，但容易出現(xiàn)“假溢出”問題，因此常配合循環(huán)隊列優(yōu)化使用。第二種是鏈式隊列，基于鏈表實現(xiàn)，入隊和出隊都比較靈活，不容易出現(xiàn)容量浪費，但需要額外的指針空間。

二、循環(huán)隊列的實現(xiàn)

public class MyCircularQueue {
    public int[] elem;
    public int front;
    public int rear;
    public MyCircularQueue(int k){
        elem=new int[k+1];
    }
    public boolean enQueue(int val){
        if(isFull()){
            return false;
        }
        elem[rear]=val;
        rear=(rear+1)%elem.length;
        return true;
    }
    public boolean deQueue(){
        if(isEmpty()){
            return false;
        }
        front=(front+1)%elem.length;
        return true;
    }
    public int front(){
        if(isEmpty()){
            return -1;
        }
        return elem[front];
    }
    public int Rear(){
        if(isEmpty()){
            return -1;
        }
        int index=(rear==0)?elem.length-1:rear-1;
        return elem[index];
    }
    public boolean isEmpty(){
        return front==rear;
    }
    public boolean isFull(){
        return (rear+1)%elem.length==front;
    }
}

構造函數(shù) MyCircularQueue(int k) 的作用是初始化循環(huán)隊列。這里創(chuàng)建了一個長度為 k+1 的數(shù)組，而不是 k。多出來的一個空間用于區(qū)分隊列的“空”和“滿”兩種狀態(tài)，否則僅靠 front == rear 無法判斷。此時 front 和 rear 默認都為 0，表示隊列為空。

enQueue(int val) 用于入隊操作。首先判斷隊列是否已滿，如果滿了直接返回 false 表示入隊失敗。如果還有空間，就把新元素放入 rear 所指的位置，然后通過 (rear + 1) % elem.length 讓隊尾指針向后移動一位，并在到達數(shù)組末尾時自動回繞到開頭，實現(xiàn)“循環(huán)”的效果。操作成功返回 true。

deQueue() 方法用于出隊操作。它先調用 isEmpty() 判斷隊列是否為空，如果為空則返回 false。如果隊列中有元素，并不會真正刪除數(shù)組中的值，而是通過移動 front 指針來“跳過”原隊頭元素，即 front = (front + 1) % elem.length。

front() 方法用于獲取隊頭元素但不刪除。函數(shù)先判斷隊列是否為空，如果為空返回 -1；否則直接返回 elem[front]。

Rear() 方法用于獲取隊尾元素。這里有一個容易出錯的細節(jié)：rear 指針并不是指向最后一個元素，而是指向“隊尾的下一個位置”。因此真正的隊尾下標需要往前退一位。如果 rear == 0，說明隊尾元素在數(shù)組最后一個位置；否則就是 rear - 1。計算出正確下標后返回對應元素。

isEmpty() 方法用于判斷隊列是否為空。判斷條件是 front == rear。在這種循環(huán)隊列設計中，只要兩個指針重合，就說明當前沒有有效元素。

isFull() 方法用于判斷隊列是否已滿。判斷條件是 (rear + 1) % elem.length == front，意思是如果隊尾指針再向前移動一步就會追上隊頭，那么隊列就滿了。

三、鏈式隊列的實現(xiàn)

import java.util.*;
public class MyLinkQueue {
    static class ListNode{
        public int val;
        public ListNode next;
        public ListNode prev;
        public ListNode(int val){
            this.val=val;
        }
    }
    public ListNode head;
    public ListNode last;
    public int usedSize;
    public boolean offer(int val){
        ListNode node=new ListNode(val);
        if(head==null){
            head=node;
            last=node;
        }else{
            last.next=node;
            node.prev=last;
            last=last.next;
        }
        usedSize++;
        return true;
    }
    public int poll(){
        if(head==null){
            return -1;
        }
        int retVal=head.val;
        if(head.next==null){
            head=head.next;
            head.prev=null;
            return retVal;
        }
        head=head.next;
        head.prev=null;
        usedSize--;
        return retVal;
    }
    public int peek(){
        if(head==null){
            return -1;
        }
        return head.val;
    }
    public boolean empty(){
        return head==null;
    }
    public int size(){
        return usedSize;
    }
}

構造的內部類 ListNode 是鏈式隊列的節(jié)點結構。每個節(jié)點包含三個部分：val 用來存儲數(shù)據(jù)，next 指向后繼節(jié)點，prev 指向前驅節(jié)點。。

offer(int val) 方法用于入隊操作。函數(shù)首先創(chuàng)建一個新節(jié)點，如果當前隊列為空（即 head == null），說明這是第一個元素，此時需要同時讓 head 和 last 都指向該節(jié)點。如果隊列不為空，就把新節(jié)點接到當前隊尾：先讓原隊尾的 next 指向新節(jié)點，再讓新節(jié)點的 prev 指向原隊尾，最后更新 last 指向新的尾節(jié)點。入隊成功后，usedSize 自增并返回 true。

poll() 方法用于出隊操作。函數(shù)先判斷隊列是否為空，如果為空直接返回 -1。否則先保存當前隊頭的值用于返回。接下來分情況處理：如果隊列只有一個節(jié)點（head.next == null），把 head 和 last 都置為 null 表示隊列清空；如果不止一個節(jié)點，則把 head 向后移動一位，并把新隊頭的 prev 置為 null，同時 usedSize--。最后返回原隊頭元素。

peek() 方法用于查看隊頭元素但不出隊。函數(shù)先判斷隊列是否為空，如果為空返回 -1；否則直接返回 head.val。

empty() 方法用于判斷隊列是否為空。實現(xiàn)方式很直接，只要判斷 head == null 即可。如果頭節(jié)點不存在，說明隊列中沒有任何元素。

size() 方法用于返回當前隊列中的有效元素個數(shù)。這里直接返回成員變量 usedSize。

四、使用棧實現(xiàn)隊列

import java.util.*;
public class MyQueue {
    private Stack<Integer> s1;
    private Stack<Integer> s2;
    public MyQueue(){
        s1=new Stack<>();
        s2=new Stack<>();
    }
    public void push(int x){
        s1.push(x);
    }
    public int pop(){
        if(empty()){
            return -1;
        }
        if(s2.empty()){
            while(!s1.empty()){
                s2.push(s1.pop());
            }
        }
        return s2.pop();
    }
    public int peek() {
        if(empty()) {
            return -1;
        }
        if(s2.empty()) {
            while (!s1.empty()) {
                s2.push(s1.pop());
            }
        }
        return s2.peek();
    }
    public boolean empty(){
        return s1.empty()&&s2.empty();
    }
}

構造函數(shù) MyQueue() 的作用是初始化兩個棧：s1 和 s2。其中，s1 作為輸入棧，負責接收所有新入隊的元素；s2 作為輸出棧，負責出隊和讀取隊頭元素。通過兩個棧之間的元素搬運，可以把棧的后進先出（LIFO）特性轉換成隊列的先進先出（FIFO）行為，這是本實現(xiàn)的核心思想。

push(int x) 方法用于入隊操作。只需把元素壓入輸入棧 s1。這里沒有立即調整順序，而是把順序反轉的工作留到出隊或取隊頭時再做。這樣可以保證入隊操作始終是 O(1) 時間復雜度，提高整體效率。

pop() 方法用于出隊操作。函數(shù)首先調用 empty() 判斷隊列是否為空，如果為空返回 -1。否則檢查輸出棧 s2 是否為空：如果為空，就把輸入棧 s1 中的所有元素依次彈出并壓入 s2。這一過程會把元素順序完全反轉，使得最早進入隊列的元素來到 s2 的棧頂。完成搬運后，直接從 s2 彈出并返回棧頂元素，即完成一次出隊。

peek() 方法用于獲取隊頭元素但不刪除。邏輯與 pop() 基本一致：先判空，如果隊列為空返回 -1；否則當 s2 為空時，把 s1 中的元素全部搬運到 s2，保證隊頭元素位于 s2 棧頂。不同之處在于這里調用的是 s2.peek()，只讀取不彈出，因此不會改變隊列中的元素個數(shù)。

empty() 方法用于判斷隊列是否為空。實現(xiàn)方式是同時檢查兩個棧：只有當 s1 和 s2 都為空時，隊列才為空。

五、使用隊列實現(xiàn)棧

import java.util.*;
public class MyStack {
    private Queue<Integer> qu1;
    private Queue<Integer> qu2;
    public MyStack(){
        qu1=new LinkedList<>();
        qu2=new LinkedList<>();
    }
    public void push(int x){
        if(!qu1.isEmpty()){
            qu1.offer(x);
        }else if(!qu2.isEmpty()){
            qu2.offer(x);
        }else{
            qu1.offer(x);
        }
    }
    public int pop(){
        if(empty()){
            return -1;
        }
        if(!qu1.isEmpty()){
            int size=qu1.size();
            for(int i=0;i<size-1;i++){
                int x=qu1.poll();
                qu2.offer(x);
            }
            return qu1.poll();
        }else{
            int size=qu2.size();
            for(int i=0;i<size-1;i++){
                int x=qu2.poll();
                qu1.offer(x);
            }
            return qu2.poll();
        }
    }
    public int top(){
        if(empty()){
            return -1;
        }
        if(!qu1.isEmpty()){
            int size=qu1.size();
            int x=-1;
            for(int i=0;i<size;i++){
                x=qu1.poll();
                qu2.offer(x);
            }
            return x;
        }else{
            int size=qu2.size();
            int x=-1;
            for(int i=0;i<size;i++){
                x=qu2.poll();
                qu1.offer(x);
            }
            return x;
        }
    }
    public boolean empty(){
        return qu1.isEmpty()&&qu2.isEmpty();
    }
}

構造函數(shù) MyStack() 的作用是初始化兩個隊列 qu1 和 qu2。這兩個隊列交替充當“數(shù)據(jù)隊列”和“輔助隊列”。由于隊列本身是先進先出（FIFO），而棧需要后進先出（LIFO），因此必須借助隊列之間的元素搬運來實現(xiàn)順序反轉。

push(int x) 方法用于入棧操作。實現(xiàn)策略是：始終把新元素加入當前非空的那個隊列中。如果 qu1 不為空，就加入 qu1；否則如果 qu2 不為空，就加入 qu2；如果兩個隊列都為空（說明是第一個元素），默認加入 qu1。這樣可以保證任意時刻只有一個隊列存放有效數(shù)據(jù)，另一個作為輔助隊列備用。

pop() 方法用于出棧操作。函數(shù)首先通過 empty() 判斷棧是否為空，如果為空返回 -1。否則找到當前存有數(shù)據(jù)的隊列，然后把其中前 size-1 個元素依次出隊并加入另一個隊列，只留下最后一個元素。這個最后留下的元素就是“棧頂元素”，直接出隊返回即可。

top() 方法用于獲取棧頂元素但不刪除。實現(xiàn)思路與 pop() 類似，但有一個關鍵區(qū)別：需要把所有元素都搬運走，并記錄最后一個被搬運的元素值作為棧頂。因為不能真正刪除元素，所以最后一個元素也要放入輔助隊列中。函數(shù)中用變量 x 保存每次出隊的值，循環(huán)結束后 x 就是原棧頂元素。

empty() 方法用于判斷棧是否為空。實現(xiàn)方式是同時檢查兩個隊列：只有當 qu1 和 qu2 都為空時，棧才為空。

到此這篇關于Java實現(xiàn)循環(huán)隊列、棧實現(xiàn)隊列、隊列實現(xiàn)棧的方法的文章就介紹到這了,更多相關java循環(huán)隊列內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: