队列(Queue)
概念
队列的使用
注意：Queue是个接口，在实例化时必须实例化LinkedList的对象，因为LinkedList实现了Queue接口。
import java.util.LinkedList;
import java.util.Queue;
public class Test {
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());
}
}
}
队列的模拟实现
队列中既然可以存储元素，那底层肯定要有能够保存元素的空间，通过前面线性表的学习了解到常见的空间类型有两种：顺序结构（数组） 和 链式结构。
队列的实现使用顺序结构还是链式结构好？
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 = last.next;
}
}
//头删
public int poll() {
if (head == null) {
return -1;
}
int ret = head.val;
if (head.next == null) {
head = null;
last = null;
} else {
head = head.next;
head.prev = null;
}
return ret;
}
public int peek() {
if (head == null) {
return -1;
}
int ret = head.val;
return ret;
}
}
循环队列
实际中我们有时还会使用一种队列叫循环队列。如操作系统课程讲解生产者消费者模型时可以就会使用循环队列。环形队列通常使用数组实现。
如何区分空与满
1. 通过添加 size 属性记录
空：size=0 满：us=数组长度
2. 保留一个位置（浪费一个空间）（下面的设计循环队列用的就是此方法）
相遇就是空 满：last的下一个是first
3. 使用标记
Boolean flag
数组下标循环的小技巧
1. 下标最后再往后(offset 小于 array.length): index = (index + offset) % array.length
2. 下标最前再往前(offset 小于 array.length): index = (index + array.length - offset) % array.length
设计循环队列
class MyCircularQueue {
public int[] elem;
public int first;
public int last;
public MyCircularQueue(int k) {
elem = new int[k];
}
public boolean enQueue(int value) {
if (isFull()) {
return false;
}
elem[last] = value;
last = (last + 1) % elem.length;
return true;
}
public boolean deQueue() {
if (isEmpty()) {
return false;
}
first = (first + 1) % elem.length;
return true;
}
//得到队头元素
public int Front() {
if (isEmpty()) {
return -1;
}
return elem[first];
}
//得到队尾元素
public int Rear() {
if (isEmpty()) {
return -1;
}
int index = (last == 0) ? elem.length - 1 : last - 1;
return elem[index];
}
public boolean isEmpty() {
return first == last;
}
public boolean isFull() {
return (last + 1) % elem.length == first;
}
}
/**
* 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();
*/
将elem = new int[k];改为elem = new int[k+1];即可
双端队列
双端队列（deque）是指允许两端都可以进行入队和出队操作的队列，deque 是 “double ended queue” 的简称。那就说明元素可以从队头出队和入队，也可以从队尾出队和入队
Deque是一个接口，使用时必须创建LinkedList的对象。
在实际工程中，使用Deque接口是比较多的，栈和队列均可以使用该接口
Deque<Integer> stack = new ArrayDeque<>();//双端队列的线性实现
Deque<Integer> queue = new LinkedList<>();//双端队列的链式实现
面试题
1.用队列实现栈
import java.util.LinkedList;
import java.util.Queue;
class MyStack {
public Queue<Integer> queue1;
public Queue<Integer> queue2;
public MyStack() {
queue1 = new LinkedList<>();
queue2 = new LinkedList<>();
}
public void push(int x) {
if (empty()) {
queue1.offer(x);
return;
}
if (!queue1.isEmpty()) {
queue1.offer(x);
} else {
queue2.offer(x);
}
}
public int pop() {
if (empty()) {
return -1;
}
if (!queue1.isEmpty()) {
int size = queue1.size();
for (int i = 0; i < size - 1; i++) {
queue2.offer(queue1.poll());
}
return queue1.poll();
} else {
int size = queue2.size();
for (int i = 0; i < size - 1; i++) {
queue1.offer(queue2.poll());
}
return queue2.poll();
}
}
public int top() {
if (empty()) {
return -1;
}
if (!queue1.isEmpty()) {
int size = queue1.size();
int ret = -1;
for (int i = 0; i < size; i++) {
ret = queue1.poll();
queue2.offer(ret);
}
return ret;
} else {
int size = queue2.size();
int ret = -1;
for (int i = 0; i < size; i++) {
ret = queue2.poll();
queue1.offer(ret);
}
return ret;
}
}
public boolean empty() {
return queue1.isEmpty() && queue2.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();
*/2.用栈实现队列
import java.util.Stack;
class MyQueue {
public Stack<Integer> s1;
public 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();
}
}
/**
* 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();
*/