文章目录

一、什么是队列？

二、队列的使用

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

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

三、队列的模拟实现（单链表实现、用数组实现循环队列）

单链表模拟实现队列：

在java当中的队列，其实底层是使用双向链表开实现队列的。

在这里我使用单向链表来实现。但是如果这是一个单纯的单链表，那么会有以下两个问题：

1）从头入队：入队的时间复杂度为O(1),出队的时间复杂度为O(N)。

2)   从尾入队：入队的时间复杂度为O(N)，出队的时间复杂度为O(1)。

但是我们可以给单链表新增一个tail 引用，永远指向尾节点。入队的时候，从tail 后面进行插入，相当于尾插法；出队的时候，从链表的头出队，相当于删除链表的头结点。

代码如下：

 static class ListNode{
        int val;
        ListNode next;

        public ListNode(int val){
            this.val = val;
        }
    }
    public ListNode head;
    public ListNode tail;
    public int usedSize;

    public void offer(int val){
        ListNode node = new ListNode(val);
        if (head == null){
            head = node;
            tail = node;
        }else {
            tail.next = node;
            tail = node;
        }
        usedSize++;
    }

    public int poll(){
        if (head == null){
            return -1;
        }
        int ret = head.val;
        head = head.next;
        if (head == null){
            tail = null;
        }
        usedSize--;
        return ret;
    }

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

    public boolean isEmpty(){
        return usedSize == 0;
    }
    public int getUsedSize(){
        return usedSize;
    }

用数组实现循环队列： 

在一些场景时我们会用到循环队列，比如在使用生产者消费者模型的时候就会使用循环队列。

关键点是如何实现循环，代码如下：

rear = (rear+1) % elem.length;
front = (front+1)%elem.length;

 完整代码如下：

 class MyCircularQueue {
        public int[] elem;
        public int front;//头部
        public int rear;//尾部
        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];
        }

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

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

四、双端队列

这种数据结构，在实际开发中使用的并不是非常多。

五、用队列实现栈

 class MyStack {
        private Queue<Integer> queue1;
        private Queue<Integer> queue2;

        public MyStack() {
            queue1 = new LinkedList<>();
            queue2 = new LinkedList<>();
        }

        public void push(int x) {
            if (!queue1.isEmpty()){
                queue1.offer(x);
            }else if (!queue2.isEmpty()){
                queue2.offer(x);
            }else {
                queue1.offer(x);
            }
        }

        public int pop() {
            if (empty())return -1;
            if (!queue1.isEmpty()){
                int len1 = queue1.size();
                for (int i = 0; i < len1 -1; i++) {
                    queue2.offer(queue1.poll());
                }
                return queue1.poll();
            }else {
                int len2 = queue2.size();
                for (int i = 0; i < len2-1; i++) {
                    queue1.offer(queue2.poll());
                }
                return queue2.poll();
            }
        }

        public int top() {
            if (empty())return -1;
            if (!queue1.isEmpty()){
                int len1 = queue1.size();
                int tmp = -1;
                for (int i = 0; i < len1; i++) {
                    tmp = queue1.poll();
                    queue2.offer(tmp);
                }
                return tmp;
            }else {
                int len2 = queue2.size();
                int tmp = -1;
                for (int i = 0; i < len2; i++) {
                    tmp = queue2.poll();
                    queue2.offer(tmp);
                }
                return tmp;
            }
        }

        public boolean empty() {
            return queue1.isEmpty() && queue2.isEmpty();
        }
    }

六、用栈实现队列

用栈实现队列：完整代码如下

 class MyQueue {
        private Stack<Integer> stack1;
        private Stack<Integer> stack2;
        public MyQueue() {
            stack1 = new Stack<>();
            stack2 = new Stack<>();
        }

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

        public int pop() {
            if (empty())return -1;
            if (!stack2.isEmpty()){
                return stack2.pop();
            }else {
                while (!stack1.isEmpty()){
                    stack2.push(stack1.pop());
                }
                return stack2.pop();
            }
        }

        public int peek() {
            if (empty())return -1;
            if (!stack2.isEmpty()){
                return stack2.peek();
            }else {
                while (!stack1.isEmpty()){
                    stack2.push(stack1.pop());
                }
                return stack2.peek();
            }
        }

        public boolean empty() {
            return stack1.isEmpty() && stack2.isEmpty();
        }
    }