目录
一.队列(Queue)
队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出 FIFO(First In First Out) 后进后出的特点
进行插入操作的一端称为队尾
出队列，进行删除操作的一端称为队头
二.队列的使用
在Java中，Queue是个接口，底层是通过链表实现的。
如图，队列中主要有这些方法
其实，1和2中方法的效果几乎差不多，但是我们经常使用的是方框2中的方法，某种程度上，2中的几个方法更好
| 方法 | 功能 |
| boolean offer(E e) | 入队列 |
| E poll() | 出队列 |
| peek() | 获取队头元素，但不删除元素 |
| int size() | 获取队列中有效元素个数 |
| boolean isEmpty() | 检测队列是否为空 |
-
public
static
void
main
(String[] args) {
-
Queue<Integer> queue =
new
LinkedList<>();
-
queue.offer(
1);
-
queue.offer(
2);
-
queue.offer(
3);
-
queue.offer(
4);
-
System.out.println(queue.poll());
//从队头出队列，并将删除的元素返回
-
Integer
val
= queue.peek();
//获取队头元素，但不删除
-
System.out.println(val);
-
if (queue.isEmpty()) {
-
System.out.println(
"队列空");
-
}
else {
-
System.out.println(queue.size());
-
}
-
}
三.队列的模拟实现（单链表实现）
首先，我们提出一个疑问：入队采用头插法还是尾插法呢？
如果入队采用的是头插法：入队的时候就是从头入：头插法【O(1)】
出队的时候：删除尾节点【O(n)】
如果入队采用的是尾插法：入队的时候就是从尾入：尾插法【O(n)】
出队的时候：删除头节点【O(1)】
可当我们给单向链表加一个last属性以标记尾节点时，采用尾插法入队的入队和出队的时间复杂度都是O(1)，而采用头插法入队的入队是O(1)，出队仍是O(n) 【这是因为要删除尾节点，就得找到尾节点的前一个】
所以，我们如果要用单链表，采用尾插法入队更好，即尾巴入队，从头出队的方法
但如果是双向链表，不管从哪边入队，时间复杂度都是O(1)
下面我们来看一下用单链表模拟实现队列的代码吧
-
public
class
MyLinkedList {
-
class
Node{
-
public
int val;
-
public Node next;
-
public
Node
(int val){
-
this.val = val;
-
}
-
public Node head;
-
public Node last;
-
public
int UsedSize;
-
-
/**
-
* 入队
-
* @param val
-
*/
-
public
void
offer
(int val){
-
Node
node
=
new
Node(val);
-
if(
this.head ==
null){
-
head = node;
-
last = node;
-
}
else{
-
last.next = node;
-
last = node;
-
}
-
this.UsedSize++;
-
}
-
-
/**
-
* 出队(从头出)
-
* @return
-
*/
-
public
int
poll
(){
-
if(isEmpty()){
-
throw
new
RuntimeException(
"队列为空！");
-
}
else{
-
int
val
=
this.head.val;
-
head = head.next;
-
//处理只有一个节点的情况
-
if(
this.head ==
null){
-
last =
null;
-
}
-
this.UsedSize--;
-
return val;
-
}
-
}
-
-
/**
-
* 出队但是不删除
-
* @return
-
*/
-
public
int
peek
(){
-
if(isEmpty()){
-
throw
new
RuntimeException(
"队列为空！");
-
}
-
return
this.head.val;
-
}
-
-
public
int
size
(){
-
return
this.UsedSize;
-
}
-
-
public
boolean
isEmpty
(){
-
return UsedSize==
0 ;
-
}
-
}
-
}
四.循环队列
实际使用中，我们有时还会使用一种特殊的队列——循环队列
循环队列通常用数组实现
我们分析一下如何实现
数组下标循环的小技巧
1. 下标最后再往后(offset 小于 array.length): index = (index + offset) % array.length
2. 下标最前再往前(offset 小于 array.length): index = (index + array.length - offset) % array.length
如何区分空与满
- 通过添加 size 属性记录(UsedSize)
- 使用标记
- 保留一个位置（空一个位置）
例题
设计循环队列：具体的解析都写在注释里啦~
-
class
MyCircularQueue {
-
private
int[] elem;
-
private
int front;
//表示队头下标
-
private
int rear;
//表示队尾下标
-
/**
-
* 构造方法
-
* @param k k个大小
-
*/
-
public
MyCircularQueue
(int k) {
-
elem =
new
int[k+
1];
//由于我们需要浪费一个空间来确定是否为满，所以k要加 1
-
//如果不加 1 ，就用UsedSize==length来判断满
-
}
-
-
/**
-
* 入队
-
* 1.判断队列是否是满的
-
* 2.不满，则把当前需要的元素放到 rear下标的地方
-
* @param value
-
* @return
-
*/
-
public
boolean
enQueue
(int value) {
-
if(isFull()) {
-
return
false;
-
}
-
this.elem[rear] = value;
-
//this.rear++; 这是错误的，因为是一个循环队列，要考虑大小,直接加可能会导致数组越界
-
this.rear = (rear+
1) % elem.length;
-
return
true;
-
}
-
-
/**
-
* 出队
-
* 1.判断队列是否为空的
-
* @return
-
*/
-
public
boolean
deQueue
() {
-
if(isEmpty()) {
-
return
false;
-
}
-
this.front = (
this.front+
1) %
this.elem.length;
//不能直接加 1
-
return
true;
-
}
-
-
/**
-
* 得到队头元素
-
* @return
-
*/
-
public
int
Front
() {
-
if(isEmpty()) {
-
return -
1;
-
}
-
return elem[front];
-
}
-
-
/**
-
* 得到队尾元素
-
* @return
-
*/
-
public
int
Rear
() {
-
if(isEmpty()) {
-
return -
1;
-
}
-
/*
-
return elem[rear];
-
这样写是错误的，由于(0-1)=-1,会越界，我们应该考虑 rear=0的情况
-
*/
-
int
index
= (
this.rear==
0) ? (
this.elem.length-
1) : (
this.rear-
1);
-
return elem[index];
-
}
-
-
/**
-
* 判断当前队列是否为空
-
* rear和front相遇就是空的
-
* @return
-
*/
-
public
boolean
isEmpty
() {
-
return
rear
== front;
//rear和front相遇就是空的
-
}
-
-
/**
-
* 判断当前队列是否为满
-
* 浪费一个空间来表示满
-
* @return
-
*/
-
public
boolean
isFull
() {
-
if( (rear+
1)%elem.length == front ){
-
return
true;
-
}
-
return
false;
-
}
-
}
五.双端队列（了解）
下面我们再来简单的介绍一下双端队列(Deque)
双端队列（deque）是指允许两端都可以进行入队和出队操作的队列，deque 是 “double ended queue” 的简称。
那就说明元素可以从队头出队和入队，也可以从队尾出队和入队。
Deque是一个接口，使用时必须创建LinkedList的对象。
以上是一些队列的有关知识
转载：https://blog.csdn.net/Living_Amethyst/article/details/125386843