1. 隊(duì)列
1.1 概念
隊(duì)列是一種特殊的線性表,特殊之處在于它只允許在某一端添加數(shù)據(jù),在另一端刪除數(shù)據(jù).進(jìn)行插入操作的端稱為隊(duì)尾, 進(jìn)行刪除操作的端稱為隊(duì)頭.
隊(duì)列可以類比我們現(xiàn)實(shí)生活中的排隊(duì)場(chǎng)景, 先排隊(duì)總是先出隊(duì).符合隊(duì)列的先進(jìn)后出的原則.
在電影院,自助餐廳,雜貨店收銀臺(tái),我們都會(huì)排隊(duì).排在第一位的人會(huì)先接受服務(wù),
1.2創(chuàng)建基本結(jié)構(gòu)
隊(duì)列的基本功能需求如下
1. 入隊(duì) (enqueue);
2. 出隊(duì) (dequeue);
3. 返回隊(duì)列首端數(shù)據(jù), 但不刪除(first);
4. 清空隊(duì)列 (clear)
5. 返回隊(duì)列長(zhǎng)度 (size);
6. 返回隊(duì)列是否為空 (isEmpty);
1. 單鏈隊(duì)列
分析單鏈隊(duì)列利用數(shù)組的push方法將元素追加到數(shù)組的最后來(lái)實(shí)現(xiàn)入隊(duì), 利用shift方法來(lái)刪除第一次元素并返回來(lái)實(shí)現(xiàn)出隊(duì).
// 單向隊(duì)列
class Queue {
constructor() {
this.queue = []
}
//入隊(duì)
enQueue(...items){
return items.map(item => {
this.queue.push(item);
return item
})
}
// 出隊(duì)
deQueue(){
return this.queue.shift()
}
// 返回隊(duì)頭
first(){
return this.queue[0];
}
//清空隊(duì)列
clear(){
this.queue = [];
}
// 返回隊(duì)列的長(zhǎng)度
size(){
return this.items.length;
}
//隊(duì)列是否為空
isEmpty(){
return this.size() === 0
}
}
下面我們簡(jiǎn)單使用這個(gè)隊(duì)列來(lái)模擬排隊(duì)
let queue = new Queue();
console.log("隊(duì)列是否為空" + queue.isEmpty())
console.log('入隊(duì)的人'+ queue.enQueue('A', 'B', 'C'));
console.log('出隊(duì)的人' + queue.deQueue());
console.log('出隊(duì)的人' + queue.deQueue());
console.log('出隊(duì)的人' + queue.deQueue());
console.log("隊(duì)列是否為空" + queue.isEmpty())
控制臺(tái)打印如下結(jié)果
2 .循環(huán)隊(duì)列
因?yàn)閱捂滉?duì)列在出隊(duì)操作時(shí)我們?nèi)〕隽岁?duì)首,也就是array[0],那么后面的元素都是一個(gè)一個(gè)往前摞位置,都摞完位置后 花費(fèi)的自然就是O(n)的時(shí)間復(fù)雜度, 所以引入了循環(huán)隊(duì)列.循環(huán)隊(duì)列的出隊(duì)操作平均是O(1)的時(shí)間復(fù)雜度.
分析 循環(huán)隊(duì)列在進(jìn)行新增元素操作即入隊(duì)時(shí),首先判斷隊(duì)列是否為滿,如果已蠻則擴(kuò)展數(shù)組,如果不滿則將新元素賦值隊(duì)尾,并讓隊(duì)尾的指針rear++, 如果已經(jīng)排列到數(shù)組最后的位置,則rear指針重新指向頭部.在進(jìn)行刪除操作即出隊(duì)操作時(shí),需要判斷隊(duì)列是否為空,然后將隊(duì)頭賦值給返回, 并將front指針往后移一位. 如果已經(jīng)移到了隊(duì)尾的位置則把front指針重新指向到頭部.
class SqQueue {
constructor(length) {
this.queue = new Array(length+1);
// 隊(duì)頭
this.front = 0;
//隊(duì)尾
this.rear = 0;
// 當(dāng)前隊(duì)列大小
this.size = 0
}
// 入隊(duì)
enQueue(item){
/*
* 判斷隊(duì)尾+1 是否為隊(duì)頭
* 如果是就代表需要擴(kuò)展數(shù)組
* % this.queue.length是防止數(shù)組越界
* */
if(this.front === (this.rear +1) % this.queue.length){
// 對(duì)數(shù)組進(jìn)行擴(kuò)容, 長(zhǎng)度翻2倍并加1
this.resize(this.getSize() * 2 + 1);
}
//將新元素賦值給隊(duì)尾
this.queue[this.rear] = item;
// 隊(duì)列長(zhǎng)度++
this.size++;
//rear指針往后移一位 并判斷是否已經(jīng)排列到最后的位置,如果是則重新指向頭部
this.rear = (this.rear + 1) % this.queue.length;
}
//出隊(duì)
deQueue(){
if(this.isEmpty()) throw Error('Queue is Empty');
// 保存隊(duì)頭元素
let res = this.queue[this.front];
//清空當(dāng)前隊(duì)頭元素
this.queue[this.front] = null;
// front指針后移, 如
this.front = (this.front + 1) % this.queue.length;
this.size--;
/*
* 判斷當(dāng)前隊(duì)列大小是否過(guò)小.
* 為了保證不浪費(fèi)空間,在隊(duì)列空間等于總長(zhǎng)度的四分之一時(shí)
* 且不為2是縮小總長(zhǎng)度為當(dāng)前的一半
* */
if(this.size === this.getSize() && this.getSize() / 2 !== 0){
console.log(22)
this.resize(this.getSize() / 2)
}
return res
}
// 獲取隊(duì)頭
getHeader(){
if(this.isEmpty()) throw Error('Queue is Empty');
return this.queue[this.front];
}
// 獲取隊(duì)列個(gè)數(shù)
getSize(){
return this.queue.length -1
}
//重新計(jì)算數(shù)組
resize(length){
let q = new Array(length);
for(let i = 0;i < length; i++){
// 從原隊(duì)列的頭節(jié)點(diǎn)開(kāi)始, 依次移動(dòng)front指針
// 并跟原隊(duì)列長(zhǎng)度進(jìn)行求模, 防止越界, 從原數(shù)組獲取不到對(duì)應(yīng)的元素
q[i] = this.queue[(i + this.front) % this.queue.length]
}
// 將數(shù)組擴(kuò)容, 并將front指向0, rear指向最后
this.queue = q;
this.front = 0;
this.rear = this.size;
}
// 返回隊(duì)列是否為空
isEmpty(){
return this.front === this.rear
}
}
3. 優(yōu)先隊(duì)列
優(yōu)先隊(duì)列非常簡(jiǎn)單, 根據(jù)優(yōu)先級(jí)來(lái)決定插入的順序,就好像登記時(shí)的貴賓通道一樣,
const Queue = (function (){
// 定義一個(gè)獨(dú)一無(wú)二的鍵, 避免外界可以利用鍵直接訪問(wèn)數(shù)據(jù)
let sym = Symbol();
// 用來(lái)豐富儲(chǔ)存的數(shù)據(jù)
class Priority{
constructor(ele,pri) {
this.element = ele;
this.priority = pri;
}
}
return class {
constructor() {
this[sym] = [];
}
/*
* 入隊(duì)時(shí)進(jìn)行根據(jù)優(yōu)先級(jí)進(jìn)行排序
* 遍歷當(dāng)前隊(duì)列,如果新插入的元素的優(yōu)先級(jí)比當(dāng)前遍歷
* 的元素優(yōu)先級(jí)小即跳過(guò),直到找到優(yōu)先級(jí)小比插入元素的優(yōu)先級(jí)小的為止
* 則插入當(dāng)前元素的前面
* */
enqueue(ele,pri){
let node = new Priority(ele,pri);
let index = 0;
while (index < this.size()){
if(this[sym][index].priority < pri) break;
index++
}
//利用數(shù)組splice方法進(jìn)行插隊(duì)
this[sym].splice(index,0,node)
}
dequeue(){
return this[sym].shift().element;
}
first(){
return this[sym][0].element;
}
clear(){
this[sym] = [];
}
size(){
return this[sym].length;
}
print(){
// 打印排隊(duì)信息
while (this.size())
console.log( this.dequeue());
}
}
})();
let queue = new Queue();
queue.enqueue("張三",1);
queue.enqueue("李四",2);
queue.enqueue("王五",3);
queue.print()
我們通過(guò)在元素入隊(duì)時(shí)傳遞了第二個(gè)參數(shù)即優(yōu)先級(jí),然后內(nèi)部利用優(yōu)先級(jí)來(lái)對(duì)元素的順序進(jìn)行重新排列, 我們可以很清楚得看到上面的代碼在控制臺(tái)依次打印出王五, 李四, 張三.
4. 雙端隊(duì)列
雙端隊(duì)列 (deque, 或稱Double-ended queue), 是一種允許我們同時(shí)從前端和后端添加和刪除的元素的特殊隊(duì)列.
雙端隊(duì)列在現(xiàn)實(shí)生活中的簡(jiǎn)答例子有,餐廳中排隊(duì)的隊(duì)伍等.舉個(gè)例子, 一個(gè)剛剛買了票的人如果只是還需要在問(wèn)一些簡(jiǎn)單的信息,就可以直接回到隊(duì)伍的頭部.另外在隊(duì)伍的末尾的人如果趕時(shí)間,它可以直接離開(kāi)隊(duì)伍.
//雙端隊(duì)列
let Queue = (function(){
let symbol = Symbol();
return class{
constructor(){
this[symbol] = [];
}
//從隊(duì)列前端入隊(duì)
enqueueFront(ele){
this[symbol].unshift(ele);
}
//從隊(duì)列后端入隊(duì)
enqueueBack(ele){
this[symbol].push(ele);
}
//從隊(duì)列列頭出隊(duì)
dequeueFront(){
return this[symbol].shift();
}
//從隊(duì)列列尾出隊(duì)
dequeueBack(){
return this[symbol].pop();
}
//返回列首數(shù)據(jù)，不刪除
peekFront(){
return this[symbol][0];
}
//返回列尾數(shù)據(jù)，不刪除
peekBack(){
return this[symbol][this.size()-1];
}
//返回隊(duì)列長(zhǎng)度
size(){
return this[symbol].length;
}
//清空隊(duì)列
clear(){
this[symbol] = [];
}
//按照隊(duì)列排列順序依次打印元素
print(){
this[symbol].forEach(v=>{
console.log(v);
});
}
}
})();
1.3 隊(duì)列結(jié)構(gòu)的應(yīng)用
隊(duì)列是一種極其基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu),不管在哪都能夠運(yùn)用到,通常需要配合其他代碼才能實(shí)現(xiàn)強(qiáng)大的功能的功能.比如整個(gè)JavaScript的運(yùn)行機(jī)制其實(shí)就是單線程, 因?yàn)槭菃尉€程,所以多任務(wù)之間都是通過(guò)隊(duì)列的方排然后在執(zhí)行.在借助事件循環(huán)實(shí)現(xiàn)這個(gè)JavaScript的強(qiáng)大功能.比如jquery中的animate方法最基本的結(jié)構(gòu)就是使用了隊(duì)列.所以說(shuō)我們無(wú)時(shí)無(wú)刻不在用著隊(duì)列, 因?yàn)樗鼘?shí)在太常用太實(shí)用了,只不過(guò),使用時(shí)的api已經(jīng)寫好了,而不需要我們定義實(shí)現(xiàn).
1. 基于隊(duì)列實(shí)現(xiàn)類似于jq的動(dòng)畫隊(duì)列.
// 單向隊(duì)列
class Queue {
constructor() {
this.queue = []
}
//入隊(duì)
enQueue(...items){
return items.map(item => {
this.queue.push(item);
return item
})
}
// 出隊(duì)
deQueue(){
console.log(this)
return this.queue.shift()
}
// 返回隊(duì)頭
first(){
return this.queue[0];
}
//清空隊(duì)列
clear(){
this.queue = [];
}
// 返回隊(duì)列的長(zhǎng)度
size(){
return this.queue.length;
}
//隊(duì)列是否為空
isEmpty(){
return this.size() === 0
}
}
const aq = (function () {
// 繼承Queue 實(shí)現(xiàn)一個(gè)當(dāng)前適合需求類
class _Queue extends Queue{
constructor(props) {
super(props);
// 保存動(dòng)畫是否運(yùn)行完成;
this.ifRun = false;
}
run(){
//如果動(dòng)畫還沒(méi)有運(yùn)行完成則打斷
if(this.ifRun) return;
// 遞歸來(lái)完成動(dòng)畫隊(duì)列的清空
this.ifRun = true;
// 由于自執(zhí)行函數(shù)內(nèi)部this默認(rèn)指向window,所以我們得手動(dòng)綁定this
(function r() {
if(this.size()){
// 往Promise傳入executor執(zhí)行者函數(shù)時(shí)
// 會(huì)自動(dòng)調(diào)用執(zhí)行者, 動(dòng)畫調(diào)用完成后會(huì)執(zhí)行then方法
new Promise(this.deQueue())
.then(res =>{
console.log(res);// 動(dòng)畫執(zhí)行完成
// 執(zhí)行下一個(gè)動(dòng)畫隊(duì)列
r.call(this)
})
}else{
this.ifRun = false;
}
}).call(this)
};
}
//用來(lái)存儲(chǔ)所有dom節(jié)點(diǎn)的動(dòng)畫隊(duì)列
let animateMap = new Map();
//init類
class init{
constructor(selector) {
this.dom = document.querySelector(selector)
}
animate(options,time=300){
// 判斷DOM節(jié)點(diǎn)是否注冊(cè)過(guò)隊(duì)列,如果沒(méi)有則注冊(cè)
if(!animateMap.get(this.dom)) {
animateMap.set(this.dom,new _Queue())
}
// 獲取DOM節(jié)點(diǎn)對(duì)應(yīng)的動(dòng)畫隊(duì)列
let queue = animateMap.get(this.dom);
// 動(dòng)畫任務(wù)入隊(duì)
queue.enQueue((resolve) =>{
this.dom.style.transition = time/1000 + "s";
// 計(jì)算offsetTop. 觸發(fā)頁(yè)面重繪, 生成動(dòng)畫效果
this.dom.offsetTop;
for(let [key,val] of Object.entries(options)){
this.dom.style[key] = val + "px";
}
// 動(dòng)畫執(zhí)行完成后觸發(fā)調(diào)用resolve
setTimeout(resolve,time)
});
//動(dòng)畫隊(duì)列調(diào)用
queue.run();
// 返回this 方便鏈?zhǔn)秸{(diào)用
return this
}
}
// 入口函數(shù) 返回一個(gè)實(shí)例對(duì)象
return function (selector) {
return new init(selector)
}
})();
下面我們簡(jiǎn)單測(cè)試一下
此時(shí)頁(yè)面有一個(gè)非常簡(jiǎn)單的box元素
<div class="box"></div>
我們寫一點(diǎn)css來(lái)進(jìn)行裝飾
.box{
width: 200px;
height: 300px;
background: #f46;
}
接下來(lái)我們通過(guò)上面寫好的aq方法來(lái)進(jìn)行調(diào)用
aq('.box')
.animate({width:"300"})
.animate({height:"100"});
總結(jié) 隊(duì)列是一種嚴(yán)格遵循先進(jìn)先出的數(shù)據(jù)結(jié)構(gòu). 隊(duì)列在尾部添加新元素,即入隊(duì),并在頭部移除元素,即出隊(duì). 最新出隊(duì)的元素必須排在隊(duì)列的末尾,JavaScript的事件循環(huán)也用到了隊(duì)列的數(shù)據(jù)結(jié)構(gòu),隊(duì)列的數(shù)據(jù)結(jié)構(gòu)在現(xiàn)實(shí)生活中非常常見(jiàn),合理的場(chǎng)景下利用隊(duì)列數(shù)據(jù)結(jié)構(gòu)可以極大的提高我們的代碼執(zhí)行效率和解決問(wèn)題的效率.
