文章目录
- ❓什么是队列
- 💥队列的定义
- ✅队列的方法
- 💦队列的分类
- 0️⃣ 链式队列
- 1️⃣ 单向队列
- 2️⃣ 双向队列
- 3️⃣ 循环队列
- 💕队列导图
- ⚡光脚造轮子
- 🎈练习题
❓什么是队列
💥队列的定义
队列是一种特殊的线性表,特殊之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作,和栈一样,队列是一种操作受限制的线性表。进行插入操作的端称为队尾,进行删除操作的端称为队头。
图片来源于网络。
✅队列的方法
方法名 | 返回值类型 | 方法体 | 描述 |
---|---|---|---|
isEmpty | boolean | boolean isEmpty() | 检测队列是否为空。为空则返回true |
peek | Object | Object peek( ) | 查看队列首部的对象并返回,但不从队列中移除它。 |
poll | Object | Object pool( ) | 移除队列顶部的对象,并作为此函数的值返回该对象。 |
remove | Object | Object remove() | 和poll 方法用法一致,但如果队列为空则会抛出异常 |
add | Object | Object add(Object element) | 把对象压入队列。如果队列已满,会抛出异常 |
offer | Object | Object offer(Object element) | 和add 方法类似,但如果队列已满,不会抛出异常,会返回null |
size | int | int size() | 返回队列中存在的元素数量 |
💦队列的分类
0️⃣ 链式队列
链式队列的容量在理论上来说是无限大的,一般是基于链表进行实现的。
1️⃣ 单向队列
这类队列只能从队列的一个方向进,从另外一个方向出,只能单向操作队列里面的内容,结构比较简单。底层实现一般是基于链表。
2️⃣ 双向队列
双向对列,又叫双端队列(deque)是指允许两端都可以进行入队和出队操作的队列,deque 是 “double ended queue” 的简称。那就说明元素可以从队头出队和入队,也可以从队尾出队和入队。双端队列比普通的队列更加灵活。双端队列可以用双向链表实现。
3️⃣ 循环队列
循环队列一般都是确定大小的,因为是确定大小的,所以一般使用数组进行实现,在队列元素占满的情况下,当一个元素出队列以后,后面的元素是不能进来的,这就造成了队列空间的浪费,所以我们在实现循环队列的时候,一旦有数据出队列,我们将后面所有的数据往前搬一个单位,这时候主要后进队列的数据没有追上前面的数据,则说明队列仍还可以进行数据存储。
💕队列导图
⚡光脚造轮子
使用单向链表构建一个单向队列,并且实现其
size
、isEmpty
、poll
、add
、peek
方法,难度【简单】
/*
* 结点类
* */
class ListNode{
int val;
ListNode next;
public ListNode(int val){
this.val = val;
next = null;
}
}
/*
* 使用尾插
* */
public class LinkedListQueue {
ListNode root;
ListNode last;
int size;
/*
* 构造方法
* */
public LinkedListQueue(){
root = null;
size = 0;
}
/*
* size()方法
* */
public int size(){
return size;
}
/*
* peek()方法
* */
public int peek(){
return root.val;
}
/*
* poll()方法
* */
public int poll(){
int ret = root.val;
root = root.next;
size--;
return ret;
}
/*
* add()方法
* */
public int add(int val){
ListNode last = root;
for(int i = 1;i<size;i++){
last = root.next;
}
last.next = new ListNode(val);
size++;
return val;
}
/*
* isEmpty()方法
* */
public boolean isEmpty(){
return (size == 0);
}
}
可以自己将双向链表实现的双向队列实现,也可以使用数组实现一个循环队列
🎈练习题
- ✅ 【用队列实现栈】LeetCode 225【简单】👉点我立即练习
- ✅ 【无法吃午餐的学生数量】LeetCode 1700【简单】👉点我立即练习
- ✅ 【队列中可以看到的人数】LeetCode 1944【困难】👉点我立即练习