队列的定义
- 队列（queue）是只允许在一端进行插入操作，而在另一端进行删除操作的线性表；
- 与栈相反，队列是一种 先进先出 的线性表；
- 与栈相同的是，队列也是一种重要的线性结构，实现一个队列同样需要顺序表和链表作为基础；
队列的存储结构
-
链式存储结构
![]( "链式存储结构")
-
顺序存储结构
![]( "顺序存储结构")
队列
单端队列（基于数组）
class Queue {
constructor() {
// 用于存储队列数据
this.queue = []
this.count = 0
}
// 入队方法
enQueue(item) {
this.queue[this.count++] = item
}
// 出队方法
deQueue() {
if (this.isEmpty()) {
return
}
// 删除 queue 的第一个元素，值会被删除，位置仍然被占用
// delete this.queue[0]
// 利用 shift() 移除数组的第一个元素
this.count--
return this.queue.shift()
}
isEmpty() {
return this.count === 0
}
// 获取队首元素值
top() {
if (this.isEmpty()) {
return
}
return this.queue[0]
}
get size() {
return this.count
}
clear() {
// this.queue = []
this.length = 0
this.count = 0
}
}
const q = new Queue()
单端队列（基于对象）
class Queue {
constructor() {
this.queue = {}
this.count = 0
// 用于记录队首的键
this.head = 0
}
// 入队方法
enQueue(item) {
this.queue[this.count++] = item
}
// 出队方法
deQueue() {
if (this.isEmpty()) {
return
}
const headData = this.queue[this.head]
delete this.queue[this.head]
this.head++
this.count--
return headData
}
isEmpty() {
return this.count === 0
}
// 获取队首元素值
top() {
if (this.isEmpty()) {
return
}
return this.queue[this.head]
}
get size() {
return this.count
}
clear() {
this.queue = {}
this.count = 0
this.head = 0
}
}
const q = new Queue()
双端队列 （基于对象）
class Deque {
constructor() {
this.queue = {}
this.count = 0
this.head = 0
}
// 队首添加
addFront(item) {
this.queue[--this.head] = item
}
// 队尾添加
addBack(item) {
this.queue[this.count++] = item
}
// 队首删除
removeFront() {
if (this.isEmpty()) {
return
}
const headData = this.queue[this.head]
delete this.queue[this.head++]
return headData
}
// 队尾删除
removeBack() {
if (this.isEmpty()) {
return
}
const backData = this.queue[this.count - 1]
delete this.queue[--this.count]
// this.count-- 与 上一步 this.count - 1 合并
return backData
}
// 获取队首值
frontTop() {
if (this.isEmpty()) {
return
}
return this.queue[this.head]
}
// 获取队尾值
backTop() {
if (this.isEmpty()) {
return
}
return this.queue[this.count - 1]
}
isEmpty() {
return this.size === 0
}
get size() {
return this.count - this.head
}
}
const deq = new Deque()
参考资料
打赏作者
您的打赏是我前进的动力
微信
支付宝
算法基础🔮 栈
上一篇
评论
