1. 队列概念及结构

队列一种先进先出的数据结构, 先入队列的数据先出队列

单链表能实现队列 ?

所以以原来的单链表无法用来实现队列, 如何修改 ?

只需再加个last引用指向尾，这样尾插入队操作复杂度就能达到O(1）

但是需要注意:

这种结构的单链表只能头插实现出队 尾插实现入队, 不能头插实现入队 尾插实现出队

因为单链表的尾删需要找到删除节点的前一个，需要遍历链表复杂度O(N）

双向链表能实现队列 ?

无论是头删出队 尾插入队，头插入队尾删出队都可以实现队列 

双向链表实现队列:

https://github.com/znxcmakhsd/DS/tree/main/12-20/MyQueue

2. 设计循环队列

数组是否可以用来实现队列 ?

答:  数组不仅可以用来实现普通队列还可以用来实现循环队列

以上是解这道题的重点，关于入队出队操作可以参考下面代码

class MyCircularQueue {

    private int[] elem;
    private int front; // 指向队头
    private int rear;  // 指向队尾

    // k = 有效数据 不考虑用来判空满的空间
    public MyCircularQueue(int k) {
        this.elem = new int[k+1];
        this.front = 0;
        this.rear = 0;
    }

    public boolean enQueue(int value) {
        // 满了不能入队
        if (isFull()) {
            return false;
        }
        this.elem[rear] = value;
        rear = (rear + 1) % elem.length;
        return true;
    }

    public boolean deQueue() {
        // 空了不能出队
        if (isEmpty()) {
            return false;
        }
        this.front = (front + 1) % elem.length;
        return true;
    }

    public int Front() {
        if (isEmpty()) {
            return -1;
        }
        return this.elem[front];
    }

    public int Rear() {
        if (isEmpty()) {
            return -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;
    }
}

/**
 * Your MyCircularQueue object will be instantiated and called as such:
 * MyCircularQueue obj = new MyCircularQueue(k);
 * boolean param_1 = obj.enQueue(value);
 * boolean param_2 = obj.deQueue();
 * int param_3 = obj.Front();
 * int param_4 = obj.Rear();
 * boolean param_5 = obj.isEmpty();
 * boolean param_6 = obj.isFull();
 */

3. 用队列实现栈

// 队列实现栈
class MyStack {
    public Queue<Integer> queueA;
    public Queue<Integer> queueB;

    public MyStack() {
        queueA = new LinkedList<>();
        queueB = new LinkedList<>();
    }

    public void push(int x) {
        // 如果两个队列都为空入QueueA
        if (empty()) {
            queueA.offer(x);
            return;
        }
        // 入不为空的队列
        if (!queueA.isEmpty()) {
            queueA.offer(x);
        }else {
            queueB.offer(x);
        }
    }

    public int pop() {
        int tmp = -1;
        if (!queueA.isEmpty()) {
            int n = queueA.size();
            for (int i = 0;i < n - 1;i++) {
                queueB.offer(queueA.poll());
            }
            tmp = queueA.poll();
        }else {
            int n = queueB.size();
            for (int i = 0;i < n - 1;i++) {
                queueA.offer(queueB.poll());
            }
            tmp = queueB.poll();

        }
        return tmp;
    }

    public int top() {
        int tmp = -1;
        if (!queueA.isEmpty()) {
            int n = queueA.size();
            for (int i = 0;i < n;i++) {
                tmp = queueA.poll();
                queueB.offer(tmp);
            }
        }else {
            int n = queueB.size();
            for (int i = 0;i < n;i++) {
                tmp = queueB.poll();
                queueA.offer(tmp);
            }
        }
        return tmp;
    }

    public boolean empty() {
        return queueA.isEmpty() && queueB.isEmpty();
    }
}

/**
 * Your MyStack object will be instantiated and called as such:
 * MyStack obj = new MyStack();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.top();
 * boolean param_4 = obj.empty();
 */

4. 用栈实现队列

class MyQueue {
    private Stack<Integer> pushst;
    private Stack<Integer> popst;

    public MyQueue() {
        pushst = new Stack<>();
        popst = new Stack<>();
    }

    public void push(int x) {
        pushst.push(x);
    }

    public int pop() {
        if (empty()) {
            return -1;
        }
        if (popst.isEmpty()) {
            while (!pushst.isEmpty()) {
                popst.push(pushst.pop());
            }
        }
        return popst.pop();
    }

    public int peek() {
        if (empty()) {
            return -1;
        }
        if (popst.isEmpty()) {
            while (!pushst.isEmpty()) {
                popst.push(pushst.pop());
            }
        }
        return popst.peek();
    }

    public boolean empty() {
        return pushst.isEmpty() && popst.isEmpty();
    }
}

/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue obj = new MyQueue();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.peek();
 * boolean param_4 = obj.empty();
 */