目录
4.1数组下标循环的小技巧（1）下标最后再往后(offset 小于 array.length): index = (index + offset) % array.length
一、队列(Queue)
1、概念
队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out) 入队列：进行插入操作的一端称为队尾（Tail/Rear） 出队列：进行删除操作的一端称为队头 （Head/Front）
2、队列的使用
在Java中，Queue是个接口，底层是通过链表实现的。
#注：Queue是个接口，在实例化时必须实例化LinkedList的对象，因为LinkedList实现了Queue接口。
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());
}
}3、队列模拟实现
队列中既然可以存储元素，那底层肯定要有能够保存元素的空间，通过前面线性表的学习了解到常见的空间类型有两种：顺序结构和链式结构。
public class Queue {
// 双向链表节点
public static class ListNode{
ListNode next;
ListNode prev;
int value;
ListNode(int value){
this.value = value;
}
}
ListNode first; // 队头
ListNode last; // 队尾
int size = 0;
// 入队列---向双向链表位置插入新节点
public void offer(int e){
ListNode newNode = new ListNode(e);
if(first == null){
first = newNode;
// last = newNode;
}else{
last.next = newNode;
newNode.prev = last;
// last = newNode;
}
last = newNode;
size++;
}
// 出队列---将双向链表第一个节点删除掉
public int poll(){
// 1. 队列为空
// 2. 队列中只有一个元素----链表中只有一个节点---直接删除
// 3. 队列中有多个元素---链表中有多个节点----将第一个节点删除
int value = 0;
if(first == null){
return null;
}else if(first == last){
last = null;
first = null;
}else{
value = first.value;
first = first.next;
first.prev.next = null;
first.prev = null;
}
--size;
return value;
}
// 获取队头元素---获取链表中第一个节点的值域
public int peek(){
if(first == null){
return null;
}
return first.value;
}
public int size() {
return size;
}
public boolean isEmpty(){
return first == null;
}
}4、循环队列
实际中我们有时还会使用一种队列叫循环队列。如操作系统课程讲解生产者消费者模型时可以就会使用循环队列。 环形队列通常使用数组实现。
4.1数组下标循环的小技巧
（1）下标最后再往后(offset 小于 array.length): index = (index + offset) % array.length
（2）下标最前再往前(offset 小于 array.length): index = (index + array.length - offset) % array.length
4.2如何区分空与满
（1）通过添加 size 属性记录
（2）保留一个位置
（3）使用标记
4.3设计循环队列
class MyCircularQueue {
public int front; // 队头指针，指向队列的第一个元素
public int rear; // 队尾指针，指向队列最后一个元素的下一个位置
public int[] elem; // 用于存储队列元素的数组
// 构造函数，初始化循环队列，容量为k
public MyCircularQueue(int k) {
elem = new int[k+1]; // 因为循环队列会浪费一个空间来判断满队列，所以数组大小为k+1
}
// 入队操作：向队列尾部插入一个元素value
public boolean enQueue(int value) {
if(isFull()){ // 如果队列已满，插入失败
return false;
}
elem[rear] = value; // 将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()) { // 队列为空时返回-1
return -1;
}
return elem[front]; // 返回队头元素
}
// 获取队尾元素
public int Rear() {
if(isEmpty()) { // 队列为空时返回-1
return -1;
}
// 计算队尾元素的位置：如果rear为0，则队尾在数组末尾；否则为rear-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; // 队尾指针的下一个位置是队头时队列已满
}
}二、双端队列 (Deque)
双端队列（deque）是指允许两端都可以进行入队和出队操作的队列，deque 是 “double ended queue” 的简称。 那就说明元素可以从队头出队和入队，也可以从队尾出队和入队。
Deque是一个接口，使用时必须创建LinkedList的对象。
在实际工程中，使用Deque接口是比较多的，栈和队列均可以使用该接口。
Deque<Integer> stack = new ArrayDeque<>();//双端队列的线性实现
Deque<Integer> queue = new LinkedList<>();//双端队列的链式实现三、用队列实现栈。
我们首先思考一下，队列和栈有什么区别。队列是先进先出的，而栈是先进后出的。我们可以发现，一个队列是无法实现一个栈的。因此我们定义两个队列qu1，qu2。
模拟出栈，先判断哪个队列为空，另一个队列中前n-1个进入的元素进入到空队列中，最后一个元素再出队列。
模拟入栈，每次入到不为空的队列当中；如果开始两个队列都为空，则默认放到qu1中。
import java.util.LinkedList;
import java.util.Queue;
public 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不为空，qu2为空
qu1.offer(x);
}else{//qu2不为空，qu1为空
qu2.offer(x);
}
}
//栈顶元素出栈
public int pop() {
if(empty()) {
return -1;
}
if(!qu1.isEmpty()) {
int size = qu1.size();
while(size-1 != 0) {
qu2.offer(qu1.poll());
size--;
}
return qu1.poll();
}else {
int size = qu2.size();
while(size-1 != 0) {
qu1.offer(qu2.poll());
size--;
}
return qu2.poll();
}
}
//返回栈顶元素
public int top() {
if(empty()){
return -1;
}
if(! qu1.isEmpty()){
int size = qu1.size();
int tmp = -1;
while(size != 0){
tmp = qu1.poll();
qu2.offer(tmp);//size前面的元素出队列，并进入另一个队列
size--;
}
return tmp;
}else{
int size = qu2.size();
int tmp = -1;
while(size-1 != 0){
tmp = qu2.poll();
qu1.offer(tmp);
size--;
}
return tmp;
}
}
//两个队列都是空，说明模拟栈是空的
public boolean empty() {
return qu1.isEmpty() && qu2.isEmpty();
}
}四、用栈实现队列。
同上，用栈实现队列，也得同时使用两个栈，并且只能使用标准栈操作。
模拟出队列，我们先让元素进入s1中，然后全部进入s2中，再从s2中弹出元素。这样做的好处是可以只使用s2中的元素。如果s2是空的，那么看s1是不是空？s1不是空，s1中的元素全部倒出来。
模拟入队列，全部默认放入第一个栈中。
import java.util.Stack;
public 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()){
//把s1中的数据全部倒出
while(! s1.isEmpty()){
s2.push(s1.pop());
}
}
return s2.peek();
}
//获取队头元素
public int peek() {
if(empty()){
return -1;
}
if(s2.isEmpty()){
//把s1中的数据全部倒出
while(! s1.isEmpty()){
s2.push(s1.pop());
}
}
return s2.peek();
}
//两个栈都为空，则队列为空
public boolean empty() {
return s1.isEmpty() && s2.isEmpty();
}
}