本片博客参考到银国徽老师的《Js版数据结构与算法》
队列
队列的定义
相信通过上篇博客大家对栈有了一个大概的认识,今天我们开始对队列的学习。
我们还是先看一下百度百科上对队列的定义:
说白了就是队列是一种受限的线性表,''受限''体现在只能从表的前端(队头)进行删除,只能从表的后端(队尾)进行插入。接下来我还是用一个比喻更形象的说明一下我对队列的理解。
队列的理解
相信大家平时都会路过一些网红店如‘喜茶’,‘一点点’,‘BONUS’(雇人排队的行为不值得提倡😀)，每次路过时都是门庭若市,我家楼下的也有一家烤肠店,每到周末都会排起很长的队伍。
图 1
这个时候排队的大家就形成了一个队列
图片中最前面的蓝色衣服的大叔就是队头
在最后面拍照片的我呢就是队尾了
这时候当大叔交完钱拿到自己的烤肠后就可以离开我们的'队列'(称为出队,只能从队头离开)
如果隔壁家的小孩被馋哭了的话他也只能去我的后面开始排队(称为入队,只能从队尾入队)
注意: 大叔是先去排队的,所以他也是先拿到自己的烤肠离开的,小朋友是后来的,所以他也会后拿到自己的烤肠,这也就是我们常说的'先进先出'。
对比栈的后进先出,是不是还挺有趣的?
js实现一个简单的顺序队列
首先我们要清楚的是队列分为顺序队列和循环队列,上边的例子我们排队买烤肠就是顺序队列,至于循环队列我会在接下来的例题中进行说明,我们先实现一个简单的顺序队列。
图 2
队列有两个指针，分别为队头指针front和队尾指针rear，
front指向队头元素,rear指向下一个入队元素的存储位置。(如图2)
下方的ArrayQuene函数就实现一个简单功能的顺序队列:
function ArrayQueue(){
var arr = [];
//入队操作
this.push = function(element){
arr.push(element);
return true;
}
//出队操作
this.pop = function(){
return arr.shift();
}
//获取队首
this.getFront = function(){
return arr[0];
}
//获取队尾
this.getRear = function(){
return arr[arr.length - 1]
}
//清空队列
this.clear = function(){
arr = [];
}
//获取队长
this.size = function(){
return length;
}
} 例题:设计循环队列
循环队列理解
在实际使用队列时，为了使队列空间能重复使用，往往对队列的使用方法稍加改进：无论插入或删除，一旦rear指针增1或front指针增1时超出了所分配的队列空间，就让它指向这片连续空间的起始位置。
这实际上是把队列空间想象成一个环形空间，环形空间中的存储单元循环使用，用这种方法管理的队列也就称为循环队列。除了一些简单应用之外，真正实用的队列是循环队列。
在上文中提到过顺序队列中有两个指针,front指向队头元素,rear指针指向下一个入队的元素的存储位置。结合下面这张图我们分析一下循环队列在不同情况下front指针和rear指针的指向。
图 3
- (a)在初始空队时,front和rear指针同时指向队头初始的位置(即0的位置,队列长度为6)
- (b)a,b,c三个元素入队时,rear指针会随着添加元素的个数移动到相应的位置(三个元素,向前移动1位,此时rear由0移动到3)
- (c)a出队,front指针也会随着删除元素的个数移动到相应的位置(删除1个元素,向前移动1位,此时front由0移动到1)
- (d)d,e,f,g入队,rear向前移动4位,由3移动到1,此时队列空间全部占满,rear和front同时指向1
- (e)g出队(由于g处于队头的位置,所以可以出队),front向前移动1位,由0移动到1
相信大家对循环队列有了一个初步的认识,话不多说,我们直接上例题
例题
原题地址(LeetCode 622题)
设计你的循环队列实现。 循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。
循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。
你的实现应该支持如下操作：
MyCircularQueue(k): 构造器，设置队列长度为 k 。Front: 从队首获取元素。如果队列为空，返回 -1 。Rear: 获取队尾元素。如果队列为空，返回 -1 。enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。isEmpty(): 检查循环队列是否为空。isFull(): 检查循环队列是否已满。
题目不是很难,我们简单的分析一下题目里面需要我们实现的操作:
- 建立一个长度为k的数组arr,并声明front和rear指针,初始值都设置为0,当插入或删除元素时我们需要手动操作指针的位置。
- 队首元素直接返回arr[front]即可。
- 如果rear不指向0时,队尾元素是arr[rear-1],如果rear指向0的时候队尾元素就是arr[k-1] 若队列为空 返回-1。
- 插入元素,直接将插入元素赋值给arr[rear],注意要先判断下队列是否是满的状态。
- 删除元素,将元素arr[front]赋值为空,注意要先判断一下队列是否是空的状态。
- 检查队列是否为空,当front和rear的指向相同且队首元素也为空时,队列为空。
- 检查队列是否已满,当front和rear的指向相同且队首元素有值时,队列已满。
代码如下:
class MyCircularQueue{
// 构造器
constructor (k) {
// 建立长度为k的循环队列
this.arr= Array(k)
this.length = k
// 声明队首指针front
this.front = 0
// 声明队尾指针rear
this.rear = 0
}
// 获取队首元素
Front () {
// 如果队列为空,返回-1 否则直接返回front指向的值
return this.isEmpty()? -1 : this.arr[this.front]
}
// 获取队尾元素
Rear () {
// 如果此时rear指针指向0的位置,返回队列最后一位,否则返回下一位
let rearItem = this.rear -1 < 0 ? this.length -1 : this.rear -1
return this.isEmpty()?-1: this.arr[rearItem]
}
// 插入元素
enQueue (value) {
// 先判断队列是否是已满状态
if(this.isFull()){
return false
}else{
// 插入元素
this.arr[this.rear] = value
// 移动rear指针位置,考虑到循环队列指针的变动,用取模的方式
this.rear = (this.rear+1) % this.length
return true
}
}
// 删除元素
deQueue () {
// 先判断队列是否为空
if(this.isEmpty()){
return false
}else{
this.arr[this.front] = ''
this.front = (this.front+1) % this.length
return true
}
}
// 判断队列是否为空
isEmpty () {
// 头尾指针指向同一个地址并且队首元素为空
return this.rear === this.front && !this.arr[this.front]
}
// 判断队列是否已满
isFull () {
// 头尾指针指向同一个地址并且队首元素不为空
return this.rear === this.front && !!this.arr[this.front]
}
}总结
栈和队列是相对简单的数据结构,相信通过两篇博客大家对这两种数据结构都有了简单的认识,接下来我将介绍相对复杂一些的数据结构。
