数据结构 之 队列(Queue)
1. 定义：
队列和栈类似，是一种只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表；
进入队列的一端称为队尾，离开队列的一端称为队头；
队列这个结构遵循先进先出的原则；
在日常生活中，例如：
多人在网上对老师提交任务时，会将我们所提交的任务存放到一个队列中，然后队列将这些任务按照先进先出的顺序进行出队和入队的操作，老师看到的任务，也就会按照提交时间的先后来排序；
由上图可以看出Queue是一个接口，底层是由链表（LinkedList）实现的；
2. 队列的常用方法和模拟实现：
2.1 常用方法：
方法作用offer（E e）将e进行入队操作E poll（） 将e进行出队列操作，并且返回e的值 E peek（）获取队头元素int size（）获取队列的长度boolean isEmpty（）判断队列是否为空
（在队列的模拟实现中，我们并不使用泛型，而是使用整形来代替泛型）
以上就是队列的常用方法，接下来我们进行模拟实现：
2.2 模拟实现：
队列的底层是由链表来实现的，我们先创建一个My_Queue类：
public class My_Queue {
public static class ListNode {
ListNode next; //节点的后继
ListNode prev; //节点的前驱
int value; //节点的值
public ListNode() {
//不带参数的构造方法
}
public ListNode(int value){
//带一个参数的构造方法，将节点的值赋为value
this.value = value;
}
}
ListNode first; //队头节点
ListNode last; //队尾节点
int size = 0; //队列长度
}< 1 > offer方法：
offer方法是将指定元素插入到队列的队尾：
与之前的栈和顺序表不同，由于队列的底层是用链表实现的，故不需要判断队列是否满了；
// 入队列---向双向链表位置插入新节点
public void offer(int e){
ListNode newNode = new ListNode(e); //实例化一个节点
if(first == null){ //若该队列为空
first = newNode; //将队头和队尾都更新为newNode
last = newNode;
}else{ //若队列不为空
last.next = newNode; //将newNode赋值给队尾.next
newNode.prev = last; //将newNode的pre赋值为队尾
last = newNode; //将队尾更新为newNode
}
last = newNode; //更新队尾
size++; //队列长度 +1
}< 2 > poll方法：
poll方法是将队头的元素进行出队操作，并返回队头元素的值：
在进行该操作之前，我们需要判断队列是否为空，若为空，则需抛出异常：
异常代码如下：
public class QueueEmptyException extends RuntimeException {
public QueueEmptyException () {
super();
}
public QueueEmptyException (String str) {
super(str);
}
}poll方法如下：
public int poll(){
// 1. 队列为空
// 2. 队列中只有一个元素----链表中只有一个节点---直接删除
// 3. 队列中有多个元素---链表中有多个节点----将第一个节点删除
int value = 0;
if(first == null){ //若为空，则抛出异常
throw new QueueEmptyException("队列为空，不能进行poll操作！！！");
}else if(first == last){ //若只有一个节点，则直接删除该节点
last = null;
first = null;
}else{
value = first.value; //将队头的元素赋值给value
first = first.next; //将队头更新为队头的下一个节点
first.prev.next = null;
first.prev = null;
}
size--; //将队列长度 -1
return value; //返回队头的值
}< 3 > peek方法：
peek方法是返回队头的节点的值：
// 获取队头元素---获取链表中第一个节点的值域
public int peek(){
if(first == null){ //若队列为空，则抛出异常
throw new QueueEmptyException("队列为空，不能进行peek操作！！！");
}
return first.value; //返回队头的值
}< 4 > size方法：
size方法是返回队列的长度：
public int size() {
return size; //返回队列的长度
}< 5 > isEmpty方法：
isEmpty是判断队列是否为空：
public boolean isEmpty(){
return first == null; //返回队头是否为空 的值
}3. 队列的模拟实现源码：
public class My_Queue {
public static class ListNode {
ListNode next; //节点的后继
ListNode prev; //节点的前驱
int value; //节点的值
public ListNode() {
//不带参数的构造方法
}
public ListNode(int value){
//带一个参数的构造方法，将节点的值赋为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; //将队头和队尾都更新为newNode
last = newNode;
}else{ //若队列不为空
last.next = newNode; //将newNode赋值给队尾.next
newNode.prev = last; //将newNode的pre赋值为队尾
last = newNode; //将队尾更新为newNode
}
last = newNode; //更新队尾
size++; //队列长度 +1
}
// 出队列---将双向链表第一个节点删除掉
public int poll(){
// 1. 队列为空
// 2. 队列中只有一个元素----链表中只有一个节点---直接删除
// 3. 队列中有多个元素---链表中有多个节点----将第一个节点删除
int value = 0;
if(first == null){ //若为空，则抛出异常
throw new QueueEmptyException("队列为空，不能进行poll操作！！！");
}else if(first == last){ //若只有一个节点，则直接删除该节点
last = null;
first = null;
}else{
value = first.value; //将队头的元素赋值给value
first = first.next; //将队头更新为队头的下一个节点
first.prev.next = null;
first.prev = null;
}
size--; //将队列长度 -1
return value; //返回队头的值
}
// 获取队头元素---获取链表中第一个节点的值域
public int peek(){
if(first == null){ //若队列为空，则抛出异常
throw new QueueEmptyException("队列为空，不能进行peek操作！！！");
}
return first.value; //返回队头的值
}
public int size() {
return size; //返回队列的长度
}
public boolean isEmpty(){
return first == null; //返回队头是否为空 的值
}
}4. 循环队列
实际中我们有时还会使用一种队列叫循环队列。如操作系统课程讲解生产者消费者模型时可以就会使用循环队列。 环形队列通常使用数组实现。
4.1 模拟实现：
/*
解题思路：
1. 注意，循环队列底层空间大小是固定的
2. 采用计数方式实现队列空或者满的判断
3. 入队列时：队列可能满，往队尾插入，注意back在末尾特殊情况
4. 出队列时：队列可能空，删除队头元素，注意front可能在队尾
5. 获取队头注意空队列时返回-1
6. 获取队尾时，注意back-1可能为负数，队尾元素下标：
(back-1+array.length)%array.length
*/
class MyCircularQueue {
int[] array;
int front; // 队头
int back; // 队尾
int count; // 队列中有效元素个数
public MyCircularQueue(int k) {
array = new int[k];
}
public boolean enQueue(int value) {
if(isFull()){
return false;
}
// 在队尾插入一个元素，然后back往后移动
array[back] = value;
back++;
// back往后移动之后，可能会来到空间末尾
// 此时将back挪到空间起始位置
if(back == array.length){
back = 0;
}
count++;
return true;
}
public boolean deQueue() {
if(isEmpty()){
return false;
}
// 出队列，队头往后移动
++front;
// 队头往后移动之后也可能会来到空间末尾
// 此时需要挪到空间起始位置
front %= array.length;
--count;
return true;
}
public int Front() {
if(isEmpty()){
return -1;
}
// 如果队列不空，说明队列中有元素，队头元素直接返回front即可
return array[front];
}
public int Rear() {
if(isEmpty()){
return -1;
}
// 如果队列不空，说明队列中有元素
// 队尾元素即：back-1,
// 如果back不在0号位置，back-1就是队尾元素下标
// 如果back在0号位置，-1之后就是负数，因此需要+数组长度
// 两个结合起来：
return array[(back - 1 + array.length)%array.length];
}
public boolean isEmpty() {
return 0 == count;
}
public boolean isFull() {
return count == array.length;
}
}5. 双端队列：
双端队列（deque）是指允许两端都可以进行入队和出队操作的队列，deque 是 “double ended queue” 的简称。 那就说明元素可以从队头出队和入队，也可以从队尾出队和入队。
Deque是一个接口，使用时必须创建LinkedList的对象。
以上就是队列的全部内容：感谢观看！！！！
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2024-03-15，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
