🔥个人主页：寻星探路

🎬作者简介：Java研发方向学习者

📖个人专栏：《从青铜到王者，就差这讲数据结构！！！》、 《JAVA（SE）----如此简单！！！》、《数据库那些事！！！》

⭐️人生格言：没有人生来就会编程，但我生来倔强！！！

---

---

目录

一、队列(Queue)

1、概念

2、队列的使用

 3、队列模拟实现

 4、循环队列

4.1数组下标循环的小技巧（1）下标最后再往后(offset 小于 array.length): index = (index + offset) % array.length

4.2如何区分空与满

4.3设计循环队列

二、双端队列 (Deque)

三、用队列实现栈。

四、用栈实现队列。

---

一、队列(Queue)

1、概念

        队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out) 入队列：进行插入操作的一端称为队尾（Tail/Rear） 出队列：进行删除操作的一端称为队头 （Head/Front）

2、队列的使用

        在Java中，Queue是个接口，底层是通过链表实现的。

        #注：Queue是个接口，在实例化时必须实例化LinkedList的对象，因为LinkedList实现了Queue接口。

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.size());
    System.out.println(q.peek());  // 获取队头元素
    
    q.poll();
    System.out.println(q.poll());  // 从队头出队列，并将删除的元素返回
    
    if(q.isEmpty()){
        System.out.println("队列空");
    }else{
        System.out.println(q.size());
    }
 }

 3、队列模拟实现

        队列中既然可以存储元素，那底层肯定要有能够保存元素的空间，通过前面线性表的学习了解到常见的空间类型有两种：顺序结构和链式结构。

public class Queue {
     // 双向链表节点
     public static class ListNode{
         ListNode next;
         ListNode prev;
         int value;
 
         ListNode(int value){
             this.value = value;
         }
     }
 
     ListNode first;   // 队头
     ListNode last;    // 队尾
     int size = 0;
     // 入队列---向双向链表位置插入新节点
     public void offer(int e){
         ListNode newNode = new ListNode(e);
         if(first == null){
             first = newNode;
             // last = newNode;
         }else{
             last.next = newNode;
             newNode.prev = last;
             // last = newNode;
         }
 
         last = newNode;
         size++;
     }
 
    // 出队列---将双向链表第一个节点删除掉
    public int poll(){
        // 1. 队列为空
        // 2. 队列中只有一个元素----链表中只有一个节点---直接删除
        // 3. 队列中有多个元素---链表中有多个节点----将第一个节点删除
        int value = 0;
        if(first == null){
            return null;
        }else if(first == last){
            last = null;
            first = null;
        }else{
            value = first.value;
            first = first.next;
            first.prev.next = null;
            first.prev = null;
        }
        --size;
        return value;
    }
 
    // 获取队头元素---获取链表中第一个节点的值域
    public int peek(){
        if(first == null){
            return null;
        }
 
        return first.value;
    }
 
    public int size() {
        return size;
    }
 
    public boolean isEmpty(){
        return first == null;
    }
 }

 4、循环队列

        实际中我们有时还会使用一种队列叫循环队列。如操作系统课程讲解生产者消费者模型时可以就会使用循环队列。 环形队列通常使用数组实现。

4.1数组下标循环的小技巧
（1）下标最后再往后(offset 小于 array.length): index = (index + offset) % array.length

（2）下标最前再往前(offset 小于 array.length): index = (index + array.length - offset) % array.length

4.2如何区分空与满

（1）通过添加 size 属性记录

（2）保留一个位置

（3）使用标记

4.3设计循环队列

class MyCircularQueue {
    public int front; // 队头指针，指向队列的第一个元素
    public int rear;  // 队尾指针，指向队列最后一个元素的下一个位置
    public int[] elem; // 用于存储队列元素的数组
 
    // 构造函数，初始化循环队列，容量为k
    public MyCircularQueue(int k) {
        elem = new int[k+1]; // 因为循环队列会浪费一个空间来判断满队列，所以数组大小为k+1
    }
    
    // 入队操作：向队列尾部插入一个元素value
    public boolean enQueue(int value) {
        if(isFull()){ // 如果队列已满，插入失败
            return false;
        }
        elem[rear] = value; // 将value放入队尾
        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()) { // 队列为空时返回-1
            return -1;
        }
        return elem[front]; // 返回队头元素
    }
    
    // 获取队尾元素
    public int Rear() {
        if(isEmpty()) { // 队列为空时返回-1
            return -1;
        }
        // 计算队尾元素的位置：如果rear为0，则队尾在数组末尾；否则为rear-1
        int index = (rear == 0) ? elem.length-1 : rear-1;
        return elem[index]; // 返回队尾元素
    }
    
    // 判断队列是否为空
    public boolean isEmpty() {
        return rear == front; // 队头和队尾指针相等时队列为空
    }
    
    // 判断队列是否已满
    public boolean isFull() {
        return (rear+1)%elem.length == front; // 队尾指针的下一个位置是队头时队列已满
    }
}

二、双端队列 (Deque)

        双端队列（deque）是指允许两端都可以进行入队和出队操作的队列，deque 是 “double ended queue” 的简称。 那就说明元素可以从队头出队和入队，也可以从队尾出队和入队。

        Deque是一个接口，使用时必须创建LinkedList的对象。

        在实际工程中，使用Deque接口是比较多的，栈和队列均可以使用该接口。

Deque<Integer> stack = new ArrayDeque<>();//双端队列的线性实现
Deque<Integer> queue = new LinkedList<>();//双端队列的链式实现

三、用队列实现栈。

（225. 用队列实现栈 - 力扣（LeetCode））

        我们首先思考一下，队列和栈有什么区别。队列是先进先出的，而栈是先进后出的。我们可以发现，一个队列是无法实现一个栈的。因此我们定义两个队列qu1，qu2。

        模拟出栈，先判断哪个队列为空，另一个队列中前n-1个进入的元素进入到空队列中，最后一个元素再出队列。

        模拟入栈，每次入到不为空的队列当中；如果开始两个队列都为空，则默认放到qu1中。

import java.util.LinkedList;
import java.util.Queue;
 
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(empty()){
             qu1.offer(x);
             return;
         }
         if(!qu1.isEmpty()){//qu1不为空，qu2为空
             qu1.offer(x);
         }else{//qu2不为空，qu1为空
             qu2.offer(x);
         }
    }
 
    //栈顶元素出栈
    public int pop() {
        if(empty()) {
            return -1;
        }
        if(!qu1.isEmpty()) {
            int size = qu1.size();
            while(size-1 != 0) {
                qu2.offer(qu1.poll());
                size--;
            }
            return qu1.poll();
        }else {
            int size = qu2.size();
            while(size-1 != 0) {
                qu1.offer(qu2.poll());
                size--;
            }
            return qu2.poll();
        }
    }
 
    //返回栈顶元素
    public int top() {
        if(empty()){
            return -1;
        }
        if(! qu1.isEmpty()){
            int size = qu1.size();
            int tmp = -1;
            while(size != 0){
                tmp = qu1.poll();
                qu2.offer(tmp);//size前面的元素出队列，并进入另一个队列
                size--;
            }
            return tmp;
        }else{
            int size = qu2.size();
            int tmp = -1;
            while(size-1 != 0){
                tmp = qu2.poll();
                qu1.offer(tmp);
                size--;
            }
            return tmp;
        }
    }
 
    //两个队列都是空，说明模拟栈是空的
    public boolean empty() {
        return qu1.isEmpty() && qu2.isEmpty();
    }
}

四、用栈实现队列。

（232. 用栈实现队列 - 力扣（LeetCode））

        同上，用栈实现队列，也得同时使用两个栈，并且只能使用标准栈操作。

        模拟出队列，我们先让元素进入s1中，然后全部进入s2中，再从s2中弹出元素。这样做的好处是可以只使用s2中的元素。如果s2是空的，那么看s1是不是空？s1不是空，s1中的元素全部倒出来。

        模拟入队列，全部默认放入第一个栈中。

import java.util.Stack;
 
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.isEmpty()){
            //把s1中的数据全部倒出
            while(! s1.isEmpty()){
                s2.push(s1.pop());
            }
        }
        return s2.peek();
    }
 
    //获取队头元素
    public int peek() {
        if(empty()){
            return -1;
        }
        if(s2.isEmpty()){
            //把s1中的数据全部倒出
            while(! s1.isEmpty()){
                s2.push(s1.pop());
            }
        }
        return s2.peek();
    }
 
    //两个栈都为空，则队列为空
    public boolean empty() {
        return s1.isEmpty() && s2.isEmpty();
    }
}