一、 模擬實(shí)現(xiàn)循環(huán)隊(duì)列

??622. 設(shè)計(jì)循環(huán)隊(duì)列

• ????思路：
  
• ??數(shù)據(jù)結(jié)構(gòu)：使用數(shù)組為數(shù)據(jù)結(jié)構(gòu)，且采用犧牲一個(gè)空間的方法來包裝判空和判滿的不同。
  • 判空：Q.rear == Q.front
  • 判滿：Q.rear.next == Q.front/(rear+1)%size == front(滿的時(shí)候可以看上圖，此時(shí)rear指向的空間浪費(fèi)掉了）

?這里就要注意，因?yàn)槭抢速M(fèi)一個(gè)空間來判滿的，所以比如我們需要一個(gè)容量為k的循環(huán)隊(duì)列，那么實(shí)際的物理容量應(yīng)該設(shè)計(jì)為k+1個(gè)！?。。ㄟ@題在下面代碼有體現(xiàn)，否則只能存k-1個(gè)）！

• ??頭尾指針含義（重點(diǎn)）

  • font:指向隊(duì)頭元素
  • rear:下一個(gè)待插入元素的位置

• ??

• ?????♀?代碼：

class MyCircularQueue {
    
    int[] myCircularQueue;
    int front = 0;
    int rear = 0;
    int size = 0;

    //構(gòu)造函數(shù)，創(chuàng)建一個(gè)循環(huán)隊(duì)列
    public MyCircularQueue(int k) {
        this.size = k+1;//!注意，這里需要+1
        this.myCircularQueue = new int[size];
    }
    
    //入隊(duì)操作
    public boolean enQueue(int value) {
        if (isFull()){
            return false;
        }
        myCircularQueue[rear] = value;
        rear = (rear+1)%size;
        return true;
    }
    //出隊(duì)操作
    public boolean deQueue() {
        if(isEmpty()){
            return false;
        }
        front = (front + 1)%size;
        return true;
    }
    //讀取隊(duì)頭元素（注意判空）
    public int Front() {
       if(isEmpty()){
           return -1;
       }
       return myCircularQueue[front];
    }
    //讀取隊(duì)尾元素（注意判空）
    public int Rear() {
        if(isEmpty()){
            return -1;
        }
        return myCircularQueue[(rear - 1 + size) % size ];
    }
    //判空
    public boolean isEmpty() {
        if(front == rear){
            return true;
        }
        return false;
    }
    //判滿
    public boolean isFull() {
        if((rear+1)%size == front){
            return true;
        }
        return false;
    }
}

/**
 * Your MyCircularQueue object will be instantiated and called as such:
 * MyCircularQueue obj = new MyCircularQueue(k);
 * boolean param_1 = obj.enQueue(value);
 * boolean param_2 = obj.deQueue();
 * int param_3 = obj.Front();
 * int param_4 = obj.Rear();
 * boolean param_5 = obj.isEmpty();
 * boolean param_6 = obj.isFull();
 */

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

??232. 用棧實(shí)現(xiàn)隊(duì)列

• ????思路：
  • 若只有一個(gè)棧stack1，是不可能實(shí)現(xiàn)隊(duì)列的，它可以實(shí)現(xiàn)在“隊(duì)尾”入隊(duì)，但不能實(shí)現(xiàn)拿到隊(duì)頭元素
    
  • 于是我們需要一個(gè)輔助的中轉(zhuǎn)棧stack2， 把stack1的元素依次放入，再通過stack2.peek，間接取得隊(duì)頭元素
    
    此時(shí)兩個(gè)棧一起便實(shí)現(xiàn)了隊(duì)列。（注意，當(dāng)stack2為空時(shí)，及時(shí)把stack1的元素挪過去?。?br>
• ?????♀?代碼：

class MyQueue {
   Stack<Integer> stack1;
   Stack<Integer> stack2 ;
    public MyQueue() {
        stack1 = new Stack<>();
        stack2 = new Stack<>();
    }
     /** 添加元素到隊(duì)尾 */
    public void push(int x) {
        stack1.push(x);
    }
    /** 將stack1的元素挪到stack2 */
    public void stack1ToStack2(){
        while(!stack1.empty()){
            stack2.push(stack1.pop());
        }
    }
     /** 刪除隊(duì)頭的元素并返回 */
    public int pop() {
       if(stack2.empty()){
           stack1ToStack2();
       }
       return stack2.pop();
    }
     /** 返回隊(duì)頭元素 */
    public int peek() {
        if(stack2.empty()){
           stack1ToStack2();
       }
       return stack2.peek();
    }
      /** 判斷隊(duì)列是否為空 */
    public boolean empty() {
       return stack1.empty() && stack2.empty();
    }
}

/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue obj = new MyQueue();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.peek();
 * boolean param_4 = obj.empty();
 */

三、225. 用隊(duì)列實(shí)現(xiàn)棧

??225. 用隊(duì)列實(shí)現(xiàn)棧

• ????思路：
  • 一個(gè)隊(duì)列實(shí)現(xiàn)棧的問題在于：可以像棧一樣正常入棧，但是隊(duì)列的話只能拿到棧底元素，無法拿到棧頂（隊(duì)尾）元素。
  • 為了解決這個(gè)問題，關(guān)鍵是，如何在正常入棧操作的基礎(chǔ)上，讓新添加元素（即棧頂元素處于隊(duì)頭位置，這才可以始得每次出隊(duì)列（出棧）拿到的是最新添加的棧頂元素。
• 方法1：?jiǎn)蝹€(gè)隊(duì)列實(shí)現(xiàn)
  即每次加入新元素后，把新元素前面的元素順次彈出，排到該元素后面，即可讓新元素成為隊(duì)頭元素，即棧頂元素。這樣就保證隊(duì)頭元素為棧頂元素。
  
• ?????♀?代碼：

class MyStack {
    Queue<Integer> queue;

    public MyStack() {
        queue = new LinkedList<>();
    }
    
    public void push(int x) {
        //先直接添加
        queue.offer(x);
        //將新元素（棧頂元素）前的所有元素順次移到棧頂元素之后
        for (int i = 0; i < queue.size() - 1; i++){
            queue.offer(queue.poll());
        }
    }
    
    public int pop() {
        return queue.poll();
    }
    
    public int top() {
        return queue.peek();
    }
    
    public boolean empty() {
        return queue.isEmpty();
    }
}

/**
 * Your MyStack object will be instantiated and called as such:
 * MyStack obj = new MyStack();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.top();
 * boolean param_4 = obj.empty();
 */

• 方法2：雙隊(duì)列實(shí)現(xiàn)
  本質(zhì)和單隊(duì)列是一樣的，實(shí)現(xiàn)棧的隊(duì)列是queue1,只不過在添加新元素之前，把新元素放在空的輔助隊(duì)列queue2中——使之處于隊(duì)頭（棧頂），然后將queue1中的元素順次移入，此時(shí)再把queue1和queue2互換即可（脫褲子放屁的感覺，和方法一基本上是一樣的）

class MyStack {
    Queue<Integer> queue1;
    Queue<Integer> queue2;

    public MyStack() {
        queue1 = new LinkedList<Integer>();
        queue2 = new LinkedList<Integer>();
    }
    
    public void push(int x) {
        queue2.offer(x);
        while (!queue1.isEmpty()) {
            queue2.offer(queue1.poll());
        }
        Queue<Integer> temp = queue1;
        queue1 = queue2;
        queue2 = temp;
    }
    
    public int pop() {
        return queue1.poll();
    }
    
    public int top() {
        return queue1.peek();
    }
    
    public boolean empty() {
        return queue1.isEmpty();
    }
}

??若有疑問的地方，歡迎隨時(shí)在評(píng)論區(qū)or私信找瑤瑤子交流討論??

• Java島冒險(xiǎn)記【從小白到大佬之路】
  

• LeetCode每日一題–進(jìn)擊大廠

• Go語言核心編程
  

• 算法文章來源地址http://www.zghlxwxcb.cn/news/detail-681798.html

到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)】隊(duì)列篇| 超清晰圖解和詳解：循環(huán)隊(duì)列模擬、用棧實(shí)現(xiàn)隊(duì)列、用隊(duì)列實(shí)現(xiàn)棧的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！