✨hello，进来的小伙伴们，你们好耶！✨

🍅🍅系列专栏:【数据结构与算法】

✈️✈️本篇内容:  循环队列，双端队列以及面试OJ题！

⛵⛵作者简介：一名双非本科大三在读的科班Java编程小白，道阻且长，你我同行！

🍱🍱码云存放仓库gitee：Java数据结构代码托管！

  一、循环队列

环形队列通常使用数组实现。

 那么在使用我们的循环队列时，我们可以发现很明显的一个问题就是如何区分空与满，因为刚开始没有存元素的时候我们的head和tail都是在同一位置，随着我们相继向队列中存元素，那么我们的head不动，tail往后走，当tail再次和head相遇的时候，那么问题来了，这个时候队列是满还是空的呢？如何解决？

如何区分空与满

1. 通过添加 size 属性记录
2. 保留一个位置
3. 使用标记

那么今天博主给大家演示就是通过保留一个位置(计数器)来实现循环队列！

一、实现类

class MyCircularQueue {
    private int front;
    private int rear;
    private int capacity;
    private int[] elements;//通过计数器的方式实现

    public MyCircularQueue(int k) {
        capacity = k + 1;
        elements = new int[capacity];
        rear = front = 0;
    }
}

2、插入一个元素

 public boolean enQueue(int value) {//插入一个元素
        if (isFull()) {
            return false;
        }
        elements[rear] = value;
        rear = (rear + 1) % capacity;
        return true;
    }

3、删除一个元素

    public boolean deQueue() {//删除一个元素
        if (isEmpty()) {
            return false;
        }
        front = (front + 1) % capacity;
        return true;
    }

4、获取队首元素

    public int Front() {//获取队首元素
        if (isEmpty()) {
            return -1;
        }
        return elements[front];
    }

5、获取队尾元素

 public int Rear() {//获取队尾元素
        if (isEmpty()) {
            return -1;
        }
        return elements[(rear - 1 + capacity) % capacity];
    }

6、判断是否为空

    public boolean isEmpty() {
        return rear == front;
    }

7、判断是否满

    public boolean isFull() {
        return ((rear + 1) % capacity) == front;
    }

二、双端队列

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

 Deque是一个接口，使用时必须创建LinkedList的对象。由于在实际开发中Deque使用的并不是非常多，所以大家只需了解一下即可！

三、面试题

1. 用队列实现栈。

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

实现 MyStack 类：

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

示例：

输入：
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 2, 2, false]

解释：
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // 返回 2
myStack.pop(); // 返回 2
myStack.empty(); // 返回 False

解题思路：

因为栈是后进先出结构，而我们的队列是先进先出结构，我们可以用两个队列来模拟实现栈的结构，qu1用来进栈，当我们需要出栈时，将qu1里面的元素出栈size-1个元素，就能得到我们的栈顶元素，注意，进栈的时候先判断两个队列谁不为空往哪个队列进，只有两个队列都为空的时候我们的栈也为空。

代码实现：

class MyStack {

    private Queue<Integer> qu1;
    private Queue<Integer> 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.offer(x);
        }
    }

    
    //出栈
    public int pop() {
        if(empty()) {
            return -1;//
        }
        if(!qu1.isEmpty()) {
            int size = qu1.size();
            for (int i = 0; i < size-1; i++) {

                qu2.offer(qu1.poll());
            }
            return qu1.poll();
        }else {
            int size = qu2.size();
            for (int i = 0; i < size-1; i++) {

                qu1.offer(qu2.poll());
            }
            return qu2.poll();
        }
    }


    //peek操作
    public int top() {
        if(empty()) {
            return -1;//
        }
        if(!qu1.isEmpty()) {
            int size = qu1.size();
            int ret = -1;
            for (int i = 0; i < size; i++) {
                ret = qu1.poll();
                qu2.offer(ret);
            }
            return ret;
        }else {
            int size = qu2.size();
            int ret = -1;
            for (int i = 0; i < size; i++) {
                ret =  qu2.poll();
                qu1.offer(ret);
            }
            return ret;
        }
    }


    //两个队列都为空 那么就是栈为空
    public boolean empty() {
        return qu1.isEmpty() && qu2.isEmpty();
    }
}

2. 用栈实现队列。

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

实现 MyQueue 类：

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

说明：

你 只能 使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。

示例 1：

输入：
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 1, 1, false]

解题思路：

1、用两个栈实现队列，先将元素全部入栈到第一个栈s1当中。

2、pop()操作，先判断s1是否为空，如果为空则返回-1，接着判断条件为s2为空,s1不为空，将s1中的元素全部进栈到s2当中，然后return s2.pop()便是出队操作。

3、跟操作2类似，最后返回s2.peek()便可！

代码实现：

import java.util.*;

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.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();
    }
}

🍻好了，那么关于队列的知识点就先讲到这里啦，我们下期见，拜拜！🥞