一、隊(duì)列的介紹

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

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

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

二、循環(huán)隊(duì)列的實(shí)現(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;
    }
}

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

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

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

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

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

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

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

三、鏈?zhǔn)疥?duì)列的實(shí)現(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;
    }
}

        構(gòu)造的內(nèi)部類 ListNode 是鏈?zhǔn)疥?duì)列的節(jié)點(diǎn)結(jié)構(gòu)。每個(gè)節(jié)點(diǎn)包含三個(gè)部分：val 用來存儲(chǔ)數(shù)據(jù)，next 指向后繼節(jié)點(diǎn)，prev 指向前驅(qū)節(jié)點(diǎn)。。

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

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

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

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

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

四、使用棧實(shí)現(xiàn)隊(duì)列

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();
    }
}

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

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

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

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

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

五、使用隊(duì)列實(shí)現(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();
    }
}

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

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

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

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

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

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

最新評(píng)論