目錄

1. 佇列的概念

2. 佇列的使用

3. 佇列的模擬實作

4. 回圈佇列

5. 雙端佇列

6. OJ題

1. 佇列的概念

佇列只允許在一端進行插入操作，在另一端進行洗掉操作的特殊線性表，佇列具有先進先出（FIFO）的特性，進行插入操作的一端為隊尾，進行洗掉操作的一端為隊頭，

2. 佇列的使用

在Java中，Queue是一個介面，底層是通過鏈表來實作的

注意：佇列Queue是一個介面，在實體化物件時必須實體化LinkedList物件，因為LinkedList實作了Queue介面

import java.util.LinkedList;
import java.util.Queue;

public class TestQueue {
    public static void main(String[] args) {
        Queue<Integer> q = new LinkedList<>();
        q.offer(1);
        q.offer(2);
        q.offer(3);
        q.offer(4);
        q.offer(5);
        System.out.println(q);
        System.out.println(q.size());
        q.poll();
        q.poll();
        System.out.println(q);
        System.out.println(q.isEmpty());
    }
}
//執行結果：[1, 2, 3, 4, 5]
//         5
//         [3, 4, 5]
//         false

3. 佇列的模擬實作

public class Queue<E> {
    public static class ListNode<E>{
        E val;
        ListNode<E> next;
        ListNode<E> pre;
        ListNode(E val){
            this.val = val;
        }
    }
    ListNode<E> first;    //隊頭
    ListNode<E> last;     //隊尾
    int size = 0;
    //入佇列---插新節點
    public void offer(E e){
        ListNode<E> newNode = new ListNode<>(e);
        if(first==null){
            first = newNode;
            last = newNode;
        }else{
            last.next = newNode;
            newNode.pre = last;
            last = newNode;
        }
        size++;
    }
    //出佇列---洗掉頭
    public E poll(){
        E val = null;
        if(first==null){
            return null;
        }else if(first == last){
            first = null;
            last = null;
        }else{
            val = first.val;
            first = first.next;
            first.pre.next = null;
            first.pre = null;
        }
        size--;
        return val;
    }
    //獲取隊頭元素
    public E peek(){
        if(first == null){
            return null;
        }
        return first.val;
    }
    //獲取長度
    public int size(){
        return size;
    }
    //判空
    public boolean isEmpty(){
        return first==null;
    }
    //堆疊和佇列一般不進行遍歷操作
    public static void main(String[] args) {
        Queue<Integer> q = new Queue<>();
        q.offer(1);
        q.offer(2);
        q.offer(3);
        q.offer(4);
        System.out.println(q.size());
        System.out.println(q.peek());
        q.poll();
        System.out.println(q.size());


    }
}

4. 回圈佇列

回圈佇列使用的是回圈陣列，為什么不使用普通的陣列呢？

如果使用一段連續的空間則會造成空間假溢位，造成空間的浪費，因為佇列是在尾端進行插入，在頭部進行洗掉，這樣會造成陣列中的元素偏后，如下面的情形：

所以使用的回圈陣列，回圈佇列就是解決空間的假溢位，

當對頭與隊尾重合時如何區分回圈佇列的空與滿呢？我們可以通過添加size來記錄佇列元素的個數，當size為0時佇列為空，當size不為0時，佇列為滿，

下面是回圈佇列的實作：

//回圈佇列
public class CircularQueue {
    int array[];
    int rear = 0;  //隊尾下標
    int front = 0;  //隊頭下標
    int count = 0;   //佇列的有效元素的個數
    int N;          
    public CircularQueue(int k) {
        array = new int[k];             //創建一個陣列
        N = array.length;         //用N標記陣列的長度
    }

    public boolean enQueue(int value) {     //入佇列
        if(isFull()){
            return false;     //如果佇列已經滿了，則回傳false
        }
        array[rear] = value;
        rear++;
        if(rear==N){        //rear回傳起始位置
            rear = 0;
        }
        count++;
        return true;
    }

    public boolean deQueue() {     //出佇列
        if(isEmpty()){           //如果佇列為空，則回傳false
            return false; 
        }
        front++;
        front%=N;       //front回傳起始位置
        count--;
        return true;
    }

    public int Front() {    //獲取隊頭元素
        if(isEmpty()){
            return -1;
        }
        return array[front];
    }

    public int Rear() {      //獲取隊尾元素
        if(isEmpty()){
            return -1;
        }
        return array[(rear-1+N)%N];      //隊尾元素的下標為rear-1，如果rear為0，則下標就為-1了，所以需要（rear-1+n）% n
    }

    public boolean isEmpty() {     //檢測佇列是否為空
        return count==0;
    }

    public boolean isFull() {      //檢測佇列是否已滿
        return count==N;
    }
}

5. 雙端佇列

雙端佇列是指允許兩端都可以進行入佇列和出佇列操作的佇列，deque（double ended queue的簡稱），

6. OJ題

1. 用佇列實作堆疊 （LeetCode225）用佇列實作堆疊

可以點開上面鏈接來查看題目

方法：

1. 先創建兩個佇列

2. 判空：如果兩個佇列都為空，則回傳true，否則回傳false

3. 插入元素：當兩個佇列都為空的時候，隨便選一個佇列往里插入元素，當有一個佇列不為空的時候，往這個不為空的佇列里插入元素

4. 洗掉堆疊頂元素：哪一個佇列不為空，就將這個佇列的元素往另一個為空的佇列里放，直到不為空的佇列剩余一個元素，最后再將這個元素出佇列，用一個變數接收并回傳

5. 獲取堆疊頂元素：這個操作和前面洗掉堆疊頂元素大概相同，只是在回傳元素之前，將這個元素插入另一個不為空的佇列中

參考代碼：

class MyStack {
    Queue<Integer> q1 = new LinkedList<>();
    Queue<Integer> q2 = new LinkedList<>();
    public MyStack() {
    }
    
    public void push(int x) {
        if(q2.isEmpty()){
            q1.offer(x);
        }else{
            q2.offer(x);
        }
    }
    
    public int pop() {
        int ret = 0;
        if(!q1.isEmpty()){
            while(q1.size()>1){
                q2.offer(q1.poll());
            }
            ret = q1.poll();
        }else{
            while(q2.size()>1){
                q1.offer(q2.poll());
            }
            ret = q2.poll();
        }
        return ret;
    }
    
    public int top() {
        int ret = 0;
        if(!q1.isEmpty()){
            while(q1.size()>1){
                q2.offer(q1.poll());
            }
            ret = q1.poll();
            q2.offer(ret);
        }else{
            while(q2.size()>1){
                q1.offer(q2.poll());
            }
            ret = q2.poll();
            q1.offer(ret);
        }
        return ret;
    }
    
    public boolean empty() {
        if(q1.isEmpty()&&q2.isEmpty()){
            return true;
        }
        return false;
    }
}

2. 實作一個最小堆疊（LeetCode155）最小堆疊

點上述鏈接查看題目

方法：

1. 先構造兩個堆疊，堆疊s1儲存所有元素，堆疊s2儲存最小元素

2. 入堆疊：第一個元素給兩個堆疊都添加，下來的元素如果小于等于s2的堆疊頂元素，則將元素入堆疊s2，所有元素都入堆疊s1

3. 獲取堆疊頂元素：直接獲取堆疊s1的堆疊頂元素

4. 洗掉堆疊頂元素：對于s2：如果s1堆疊頂元素與s2堆疊頂元素相等，則出堆疊；對于s1：依次出堆疊

5. 獲取堆疊里的最小元素：直接回傳堆疊s2的堆疊頂元素

參考代碼：

class MinStack {
    Stack<Integer> s1 = new Stack<>();
    Stack<Integer> s2 = new Stack<>();
   public MinStack() {

    }
    
    public void push(int val) {
        if(s1.empty()||val<=s2.peek()){
            s2.push(val);
        }
        s1.push(val);
    }
    
    public void pop() {
        if(s1.peek().equals(s2.peek())){
            s2.pop();
        }
        s1.pop();
    }
    
    public int top() {
        return s1.peek();
    }
    
    public int getMin() {
        return s2.peek();
    }
}

3. 用堆疊實作佇列（LeetCode232）用堆疊實作佇列

查看上面鏈接查看題目

方法：

1. 構造兩個堆疊，一個輸入堆疊s1，一個輸出堆疊s2

2. 判空：當兩個堆疊都為空時，回傳true，否則回傳false

3. 入佇列：直接往堆疊s1插入元素

4. 出佇列：當s2為空時，將s1的所有元素入s2，然后將s2的元素出堆疊

5. 獲取隊頭元素：當s2為空時，將s1的所有元素入s2，直接獲取s2堆疊頂元素并回傳

參考代碼：

class MyQueue {
    Stack<Integer> s1 = new Stack<>();   //輸入
    Stack<Integer> s2 = new Stack<>();   //輸出
    public MyQueue() {

    }
    
    public void push(int x) {
        s1.push(x);
    }
    
    public int pop() {
        if(s2.empty()){
            while(!s1.empty()){
                s2.push(s1.pop());
            }
        }
        return s2.pop();
    }
    
    public int peek() {
         if(s2.empty()){
            while(!s1.empty()){
                s2.push(s1.pop());
            }
        }
        return s2.peek();
    }
    
    public boolean empty() {
        if(s1.empty()&&s2.empty()){
            return true;
        }
        return false;
    }
}