【数据结构】队列的使用|模拟实现|循环队列|双端队列|面试题

一、队列(Queue)

1.1 概念

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out) 入队列：进行插入操作的一端称为队尾（Tail/Rear） 出队列：进行删除操作的一端称为队头（Head/Front）

队列和栈的区别：队列是先进先出（队尾进，队头出），栈是先进后出

1.2 队列的使用

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

方法	功能
boolean offer(E e)	入队列
E poll()	出队列
peek()	获取队头元素
int size()	获取队列中有效元素个数
boolean isEmpty()	检测队列是否为空

注意：Queue是个接口，在实例化时必须实例化LinkedList的对象，因为LinkedList实现了Queue接口 Queue<Integer> q = new LinkedList<>();

Queue 的方法有以下六种，每两种都是一样的功能（添| 删 |查），但是还是存在一定的差异

差异：

（1）add，remove，element都是Collection的通用方法

offer，poll，peek是队列专有的方法

（2）Collection实现的通用方法中有些情况会报异常

而队列专有的方法中不会报异常

eg：如果想在一个满的队列中加入一个新项，调用 add() 方法就会抛出一个 unchecked 异常，而调用 offer() 方法会返回 false

public static void main(String[] args) {
    Queue<Integer> q = new LinkedList<>();
    q.offer(1);
    q.offer(2);
    q.offer(3);
    q.offer(4);
    q.offer(5); // 从队尾入队列
    System.out.println(q.size());
    System.out.println(q.peek()); // 获取队头元素

    q.poll();
    System.out.println(q.poll()); // 从队头出队列，并将删除的元素返回

    if(q.isEmpty()){
        System.out.println("队列空");
    } else {
        System.out.println(q.size());
    }
}

1.3 队列模拟实现

队列中既然可以存储元素，那底层肯定要有能够保存元素的空间，通过前面线性表的学习了解到常见的空间类型有两种：顺序结构和链式结构。同学们思考下：队列的实现使用顺序结构还是链式结构好？

（1）单链表模拟实现：为了保证时间复杂度为O（1）

肯定不能从队头进，队尾出，这样删尾节点时间复杂度就为O（N）

所以采用从队尾进，队头出，但是这个时候就需要last指针来指向队尾，这样的尾插，头删才满足条件

（2）双向链表模拟实现：无论从队头进，队尾出，还是从队尾进，队头出，都是可以的

双向链表就是神一般的存在 LinkedList：可以当作双向链表，栈，队列

（3）数组模拟实现：可以用来实现循环队列，如果实现普通队列，就会存在删除元素的前面（front指针的前面）无法再进行添加元素

下面这个代码是由双向链表(尾插，头删）实现队列：

import java.security.PublicKey;
//双向链表(尾插，头删）实现队列
public class MyQueue {
    static class ListNode {
        public int val;
        public ListNode prev;
        public ListNode next;

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

    }
    public ListNode head;
    public ListNode last;

    //入队
    public void offer(int val) {
        ListNode node = new ListNode(val);
        //尾插
        if(head == null) {
            head = last = node;
        } else {
            last.next = node;
            node.prev = last;
            last = node;
        }
    }

    //出队
    public int poll() {
        //空队列
        if(head == null) {
            return -1;
        }
        //一个节点
        int val = -1;
        if (head.next == null) {
            val = head.val;
            head = null;
            last = null;
            return val;
        }
        val = head.val;
        head = head.next;
        head.prev = null;
        return val;
    }

    //判断是否为空
    public boolean empty() {
        return head == null;
    }

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

1.4 循环队列

实际中我们有时还会使用一种队列叫循环队列。如操作系统课程讲解生产者消费者模型时可以就会使用循环队列。环形队列通常使用数组实现

数组下标循环的小技巧

1. 下标最后再往后(offset 小于 array.length): index = (index + offset) % array.length

2. 下标最前再往前(offset 小于 array.length): index = (index + array.length - offset) % array.length

如何区分空与满

1. 通过添加 size 计数的方式来判断（这个较简单）

2. 保留一个位置，浪费空间来表示满（这个用的较多）

3. 使用标记boolean flg （开始前在同一位置标记为false，再次相遇标记为true）（这个也比较简单）

设计循环队列

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

    public MyCircularQueue(int k) {
        elem = new int[k + 1];// 浪费一个空间，也就是需要多开一个元素的空间
    }

    // 入队操作
    public boolean enQueue(int value) {
        if (isFull()) {
            return false;
        }
        elem[rear] = value;
        rear = (rear + 1) % elem.length;// 注意点1：不可直接rear+1
        return true;
    }

    // 删除队头元素（空不空 + front移动）
    public boolean deQueue() {
        if (isEmpty()) {
            return false;
        }
        front = (front + 1) % elem.length; // 注意点2：不可直接front+1
        return true;
    }

    // 得到队头元素 不删除
    public int Front() {
        if (isEmpty()) {
            return -1;
        }
        return elem[front];
    }

    // 得到队尾元素 不删除
    public int Rear() {
        if (isEmpty()) {
            return -1;
        }
        // rear=0说明刚刚走过一圈以上，那么队尾就为elem.length-1
        // rear!=0说明还没到跨越的位置，直接-1即可
        int index = (rear == 0) ? elem.length - 1 : rear - 1;
        return elem[index];
    }

    // 判空 front和rear都在起始点
    public boolean isEmpty() {
        return front == rear;
    }

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

1.5 双端队列 (Deque)

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

Deque是一个接口，使用时必须创建LinkedList的对象（所以他可以当作双向链表|栈使用）

在实际工程中，使用Deque接口是比较多的，栈和队列均可以使用该接口

Deque<Integer> stack = new ArrayDeque<>(); //双端队列的线性实现

Deque<Integer> queue = new LinkedList<>(); //双端队列的链式实现

Stack这个类不是唯一的，可以是栈，LinkedList ，也可以是ArrayDeque

二、面试题

1. 用队列实现栈

思考：一个普通的队列能否实现一个栈？肯定是不可以的，一个是先进先出，一个是先进后出

思路：

（1）当两个队列都是空的时候放到第一个队列

（2）再次" 入栈 “ 的时候，放到不为空的队列

（3）“出栈”的时候，出不为空的队列，出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(empty()) {
            qu1.offer(x);
            return;
        } 
        //入栈，放到不为空的队列
        if(!qu1.isEmpty()) {
            qu1.offer(x);
        } else {
            qu2.offer(x);
        }
        
    }
    
    public int pop() {
        if(empty()) {
            return -1;
        } 
        //找到不为空的队列 ，出size-1个元素
        if(!qu1.isEmpty()) {
            int size = qu1.size();
            for(int i =0;i<size-1;i++) { //这里不能写成i<qu1.size(),因为qu1.size()一直在变
                //出size-1个元素都放到另一个队列
                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();
        }
    }
    
    public int top() {
        if(empty()) {
            return -1;
        } 
        //找到不为空的队列 ，出size个元素
        if(!qu1.isEmpty()) {
            int size = qu1.size();
            int tmp = -1;
            for(int i =0;i<size;i++) { 
                //出size个元素都放到另一个队列,并用tmp记录下这个数
                tmp = qu1.poll();
                qu2.offer(tmp);
            }
            //返回最后出本队列的元素
            return tmp;
        } else {
          int size = qu2.size();
            int tmp = -1;
            for(int i =0;i<size;i++) { 
                tmp = qu2.poll();
                qu1.offer(tmp);
            }
            return tmp;
        }
    }
    
    //两个队列都是空代表栈为空
    public boolean empty() {
        return qu1.isEmpty() && qu2.isEmpty();
    }
}

2. 用栈实现队列

思路：

（1）“入队”:把数据放到第一个栈当中

（2）“出队”：出 s2 这个栈当中栈顶的元素即可，如果 s2 为空，把 s1 里面所有元素全部放到 s2

（3）当两个栈都为空说明模拟的队列为空

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.isEmpty()) {
            //s2为空，把s1中所有的元素放入s2中
        while(!s1.isEmpty()) {
            s2.push(s1.pop());
            }
        }
        return s2.pop();

    }
    
    public int peek() {
        if(empty()) {
            return -1;
        }
        if(s2.isEmpty()) {
            //s2为空，把s1中所有的元素放入s2中
        while(!s1.isEmpty()) {
            s2.push(s1.pop());
            }
        }
        return s2.peek();
    }
    
    public boolean empty() {
        return s1.isEmpty() && s2.isEmpty();
    }
}