数据结构：队列

特点

手搓一个队列 

 

链式队列

 

开始动手

队列属于插入元素后需要从头部来删除，我们可以用双链表来模拟它

尾巴进，头部出 

接下来整个的过程跟双链表差不多，大家可以参考我之前一篇博客

链表（3）：双链表_cx努力编程中的博客-CSDN博客

初始化 

    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;

offer

尾插法

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

poll

    public int poll(){
        //没有节点
        if(head == null){
            return -1;
        }
        int retVal = head.val;
        //只有一个节点
        if(head.next == null){
            head = null;
            last = null;
            return retVal;
        }
        //两个及以上的节点
        head = head.next;
        head.prev = null;
        usedSize--;
        return retVal;
    }

peek

    public int peek(){
        if(head == null){
            return -1;
        }
        return head.val;
    }

empty和size

    public boolean empty(){
        return head == null;
    }
 
    public int size(){
        return usedSize;
    }

---

数组队列

622. 设计循环队列 - 力扣（LeetCode）

简单介绍一下

假设有一个容量为5的数组，要操作12 23 34 45 56 67 78 7个数字

队头front，队尾rear先放在0位置，分别往后遍历

每次加入一个元素rear就++，每次弹出一个元素front就++

 

但是这会出现一个问题

当我们加到56这个元素之后，rear跑到数组外面去了，越界了

极限一点，当我们把当前队列的元素全部poll之后，front也跑到数组外面去了

其实队列弹出元素后，前面的必然会是空的，我们可以让rear走到前面来

整个队列弹空了之后也把front移到前面的空格处

如图，我们依次往队列加45 56 12 23 34，此时rear走到数组末端，我们把45弹出，rear就可以重新回到数组头

这么一看，整个数组队列就是一个循环，一个圈

 

🆗我们依次加入元素，每次加入rear就往后走

rear走了一圈又和front相遇了，此时问题来了

1. 队列此时是空的还是满的？

（1）使用usedSize来记录，放入一个元素usedSize++

（2）浪费一个空间来表示满

相当于你要过河，总得扔个石头试试深浅的道理一样，在front前面开辟一块空间，什么元素都不放，当rear走到这块空间时，判断一下rear下一个元素位置是不是front，是的话就证明队列满了

（3）使用标记

第一次相遇（起始位置）标记一下，第二次相遇的时候就证明它满了

2. rear怎么从7下标来到0下标？

公式：rear = (rear + 1) % len

front = (front + 1) % len

    public boolean isEmpty() {
        return front == rear;
    }
 
    public boolean isFull() {
        return (rear+1) % elem.length == front;
    }

入队和出队

    public MyCircularQueue(int k) {
        elem = new int[k];
    }
    //入队
    public boolean enQueue(int value) {
        if(isFull()){
            return false;
        }
        
        elem[rear] = 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()){
            return -1;
        }
        return elem[front];
    }
    //得到队尾元素
    public int Rear() {
        if(isEmpty()){
            return -1;
        }
        int index = (rear == 0) ? elem.length - 1:rear-1;
        return elem[index];
    }

得到队尾元素的部分要注意一下，不能直接rear-1，因为如果rear=0的时候，rear-1=-1是不合法的

🆗你以为结束了吗？当我们把这段代码放入到力扣里面，我们发现报错了，报错结果：

在执行3的入队操作时，预期的是true，而我们输出了false

当我们空间为3的时候，确实只能存2个元素，因为存第3个元素空间会被浪费

那我们可以投机地改一下代码

或者使用usedSize，就没有浪费空间这么一说了

代码具体就是定义完usedSize，enQueue就usedSize++，deQueue就usedSize--

---

双端队列

指的是在队列两边都可以进行入队和出队的操作

链式队列就能实现这个功能

 

那数组队列也可以实现吗

ArrayDeque的底层也是有这些头插尾插方法的

 

这两个不仅仅可以当作队列，也可以当作栈。这两个当作栈的情况比较多

---

队列题目

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

请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。

实现 MyStack 类：

• void push(int x) 将元素 x 压入栈顶。
• int pop() 移除并返回栈顶元素。
• int top() 返回栈顶元素。
• boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。

我们知道，队列和栈的出栈顺序本来就是矛盾的，所以一个队列实现不了栈，但是两个队列可以啊

假设我们要操作12 23 34 45这四个数，把前3个数加入后，栈要弹出元素，就是34第一个出

 

观察到qu2队列是空的，那qu1就把12和23分别弹出来扔到qu2里面存储起来，qu1再把34弹出，这样就实现了栈弹出34的操作

解题步骤：

1.入栈：哪个队列不为空就放到哪个队列里面，两个都为空就扔到qu1里面

2.出栈：哪个队列不为空就出size-1个元素，并扔到空队列里面

3.当两个队列都为空的时候，栈就是空的

整个代码

class MyStack {
    private Queue qu1;
    private Queue 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里面
            qu1.offer(x);
        }
    }
 
    public int pop() {
        if(empty()){
            return -1;
        }
        if(!qu1.isEmpty()){
            int size1 = qu1.size();//让一个size1记录qu1的大小，防止循环的时候循环条件里的size没有变化
            for (int i = 0; i < size1-1; i++) {
                int x = qu1.poll();
                qu2.offer(x);
            }
            return qu1.poll();
        }else{
            int size2 = qu2.size();
            for (int i = 0; i < size2-1; i++) {
                int x = qu2.poll();
                qu1.offer(x);
            }
            return qu2.poll();
        }
    }
 
    public int top() {
        if(empty()){
            return -1;
        }
        if(!qu1.isEmpty()){
            int size1 = qu1.size();
            int x = -1;
            for (int i = 0; i < size1; i++) {
                x = qu1.poll();
                qu2.offer(x);
            }
            return x;
        }else{
            int x = -1;
            int size2 = qu2.size();
            for (int i = 0; i < size2; i++) {
                x = qu2.poll();
                qu1.offer(x);
            }
            return x;
        }
    }
 
    public boolean empty() {
        return qu1.isEmpty() && qu2.isEmpty();
    }
}

---

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

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：

实现 MyQueue 类：

• void push(int x) 将元素 x 推到队列的末尾
• int pop() 从队列的开头移除并返回元素
• int peek() 返回队列开头的元素
• boolean empty() 如果队列为空，返回 true ；否则，返回 false

和上面那道题同理，一个栈实现不了队列，所以我们要用两个栈

1.入队的时候，放到s1里面

2.出队的时候，都出s2当中的元素，当s2没有元素的时候，把s1里面的元素全部倒过来

整个的代码：

class MyQueue {
 
    private Stack s1;
    private Stack 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();
    }
}