数据结构（Java）：队列&集合Queue&力扣面试OJ题

1、队列

1.1 队列的概念

队列是一个特殊的线性表，只允许在一端（队尾）进行插入数据操作，在另一端（对头）进行删除数据。队列具有先进先出FIFO(First In First Out)的特性。

入队：数据只能从队尾进队列       出队：数据只能从对头出队列

即：队尾进队头出

我们可以把队列想象为一个排队的队伍，从队尾开始排队，排到了再从队头出队：

1.2 队列的设计

实现队列，我们可以使用单链表、双向链表、数组来实现。

1. 单链表：我们可以使用last来作为标记尾结点的引用，入队时采用尾插法，出队时采用头删法，这样出队和入队时的时间复杂度都可以达到O（1）。注意:入队不可以采用头插法，因为出队时还需要找尾结点的前一个节点，时间复杂度必为O（n）。
2. 双向链表：因为具有next和prev域，头插、尾插入队都是可以的，都为O（1）。
3. 数组：普通的数组实现队列会产生很多空间的浪费，每当数据出队时，front前面的空间就会被浪费掉。我们可以设计循环队列来减少空间浪费。

接下来我们来聊一聊如何设计循环队列。

 1.2.1 循环队列

循环队列又叫做环形队列，通常是由数组实现的。

我们定义front和rear分别指向队头和队尾，rear的位置就是入队元素要插入的位置，起始时front和rear都在0下标处。

循环队列就是将数组的两端相连接，这样即使有元素出队，出队元素的位置，rear指针也可以达到，能够让新元素入队，减少空间的浪费。

当在rear为7下标时，进行入队操作后（假设队列不为满），rear要来到0下标的位置，那么要进行的操作是：rear == （rear+1）% len

于是更新rear的操作为：rear == （rear+1）% len

如果基于以上的设计，那么循环队列为空和队列为满时的条件均为：rear == front

那么对于循环队列，该如何进行判空和判满呢？我们给出改善设计：

判空：rear == front

判满（三种方法）：

1. 通过添加 size 属性记录（记录元素个数，size == 数组长度时为满）
2.  浪费一个位置，判断rear的下一个是不是front。（front == （rear+1）% len时，说明队列满）
3.  使用标记（在有元素的地方定义boolean类型为true，没有元素的地方定义为false，当front和rear相遇且boolean类型为true时，说明队列满）

1.2.2 实现循环队列

我们通过一道OJ题来设计循环队列。（使用浪费一个空间的方法来判满）

. - 力扣（LeetCode）

 代码：

class MyCircularQueue {
    public int front;
    public int rear;
    public int[] elem;

    public MyCircularQueue(int k) {
        //题目要求我们k个位置均能存储数据
        //因为我们使用浪费一个空间的方法来判满，所以我们这里要开辟k+1个空间
        elem = new int[k + 1];
    }
    
    public boolean enQueue(int value) {
        if(isFull()) {
            //不满时才能入队
            return false;
        }
        //在rear位置插入数据，并更新rear
        elem[rear] = value;
        rear = (rear+1) % elem.length;
        return true;
    }
    
    public boolean deQueue() {
        if(isEmpty()) {
            //不空时才能出队
            return false;
        }
        //直接更新front即可，新数据入队会覆盖
        front = (front+1) % elem.length;
        return true;
    }
    
    public int Front() {
       if(isEmpty()) {
        return -1;
       } 
       //front指向的位置就是队头元素
       return elem[front];
    }
    
    public int Rear() {
        if(isEmpty()) {
            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;
    }
}

2、队列Queue

在Java中，Queue是一个接口，底层是用链表来实现的：

注意：Queue是一个接口，在实例化时必须实例化实现Queue接口的类的对象。

2.1 Queue的方法

2.2、双端队列（Deque）

双端队列，元素可以在队头和队尾任意插入和删除元素，也就是说，元素可以从队头出队和入队，也可以从队尾出队和入队。

Java给出的双端队列Deque也是一个接口（Queue的扩展接口），在实例化时必须实例化实现Deque接口的类的对象。

2.3 使用Queue和Deque

在Java中，有多个类实现了Queue和Deque，这里我们只谈LinkedList和ArrayDeque。

我们可以使用LinkedList来实现队列和双端队列，为链式实现，底层为链表。

也可以使用ArrayDeque来实现队列和双端队列，为顺序实现，底层为数组。

同时，LinkedList和ArrayDeque中也实现了集合类Stack中的方法（Deque接口中包含了Stack的方法，而LinkedList和ArrayDeque实现了Deque接口），所以我们也可以使用LinkedList和ArrayDeque来实现栈。

注意：只有Deque接口中包含了Stack的方法，Queue接口没有包含。

也就是说，我们以后如果要构建栈、队列、双端队列...都可以通过LinkedList和ArrayDeque来实现，其方法更加丰富。

3、面试OJ题

3.1 用队列实现栈

. - 力扣（LeetCode）

3.1.1 思路分析

我们需要两个队列来模拟实现栈。

入栈：把数据放到不为空的队列当中，如果两个队列都为空，则随机放入即可。

出栈：两个队列必有一个为空，将不为空的队列中的size-1个元素移到空队列中，剩下的1个元素就是要模拟“出栈”的元素。

取栈顶元素：两个队列必有一个为空，将不为空的队列中的全部元素移到空队列中，并使用变量记录每次进新队列元素的数值，最后一次进队的元素就是“栈顶”元素。

 3.1.2 代码

class MyStack {
    Queue<Integer> qu1;
    Queue<Integer> qu2;

    public MyStack() {
        qu1 = new LinkedList<>();
        qu2 = new LinkedList<>();
    }
    
    //模拟入栈：把元素放到不为空的队列中
    public void push(int x) {
        if (empty()) {
            //两个队列都为空时 默认放到qu1中
            qu1.offer(x);
        } else if (qu1.isEmpty()) {
            qu2.offer(x);
        }else {
            qu1.offer(x);
        }
    }
    
    //将有元素的队列中的size-1个元素导入进空队列中
    //剩下的1个元素，就是要出栈的元素
    public int pop() {
        if (qu1.isEmpty()) {
            while (qu2.size() != 1) {
                int x = qu2.poll();
                qu1.offer(x);
            }
            return qu2.poll();
        }else {
            while (qu1.size() != 1) {
                int x = qu1.poll();
                qu2.offer(x);
            }
            return qu1.poll();
        }
    }
    
    //将有元素的队列中的全部元素导入进空队列中
    //并用变量记录每一次导进的元素，最后一次导入的元素就是栈顶元素
    public int top() {
        int x = 0;
        if (qu1.isEmpty()) {
            while (!qu2.isEmpty()) {
                x = qu2.poll();
                qu1.offer(x);
            }
            return x;
        }else {
            while (!qu1.isEmpty()) {
                x = qu1.poll();
                qu2.offer(x);
            }
            return x;
        }
    }
    
    //当两个队列都为空时，说明栈为空
    public boolean empty() {
        return qu1.isEmpty() && qu2.isEmpty();
    }
}

3.2 用栈实现队列

. - 力扣（LeetCode） 

3.2.1 思路分析

模拟入队操作：“入队”的元素全部放入第一个栈中
模拟出队操作：
需要先判断第2个栈为不为空，
1.如果未空，需要把第一个栈当中的所有元素都放到第二个栈中，弹出第二个栈当中的栈顶元素
2.如果不为空，直接弹出第二个栈当中的栈顶元素

也就是说第二个栈的栈顶元素，其实就是我们所模拟队列的队头元素。

 3.2.2 代码

class MyQueue {

    ArrayDeque<Integer> stack1;//"入队"的元素统一放到stack1中
    ArrayDeque<Integer> stack2;//统一在stack2中出队

    public MyQueue() {
        stack1 = new ArrayDeque<>();
        stack2 = new ArrayDeque<>();
    }

    public void push(int x) {
        stack1.push(x);//"入队"的元素统一放到stack1中
    }

    public int pop() {
        if (stack2.isEmpty()) {
            //若stack2为空，则将stack1中的元素导入stack2中，
            // stack2的栈顶元素即为模拟出队的“队头”元素
            while (!stack1.isEmpty()) {
                int x = stack1.pop();
                stack2.push(x);
            }
            return stack2.pop();
        }else {
            //若stack2不为空，其栈顶元素即为模拟出队的“队头”元素
            return stack2.pop();
        }
    }

    public int peek() {
        if (stack2.isEmpty()) {
            while (!stack1.isEmpty()) {
                int x = stack1.pop();
                stack2.push(x);
            }
            return stack2.peek();
        }else {
            return stack2.peek();
        }
    }

    public boolean empty() {
        //当stack1和stack2均为空时，说明模拟的队列为空
        return stack1.isEmpty() && stack2.isEmpty();
    }
}

OK~本次博客到这里就结束了，

感谢大家的阅读~欢迎大家在评论区交流问题~

如果博客出现错误可以提在评论区~

创作不易，请大家多多支持~