喬布斯經(jīng)常說到一句話：“Stay hungry, Stay foolish”
- Stay hungry:永不滿足框全，
- Stay foolish: 是說埋頭做自己的事塘慕，不要理會前行路上的各種嘲諷聲音胃夏。
大家好耻讽，我是柒八九拼余。
今天，我們繼續(xù)探索JS算法相關的知識點轿亮。我們來談談關于<span style="font-weight:800;color:#FFA500;font-size:18px">{隊列| Queue}</span>的相關知識點和具體的算法疮薇。
如果，想了解其他數(shù)據(jù)結構的算法介紹我注，可以參考我們已經(jīng)發(fā)布的文章按咒。如下是算法系列的往期文章。
文章list
好了但骨，天不早了励七，干點正事哇。
你能所學到的知識點
- JS隊列的各種實現(xiàn)
- 滑動窗口的概念和對應算法
- 利用隊列解決和二叉樹層樹相關的算法
文章概要
- 知識點簡講
- 滑動窗口
- 二叉樹的廣度優(yōu)先搜索（BFS）
知識點簡講
隊列是個啥
隊列是一種遵從先進先出（FIFO）原則的有序集合奔缠。隊列在尾部添加新元素掠抬，并從頂部移除元素。最新添加的元素必須排在隊列的末尾校哎。
在現(xiàn)實中两波，最常見的隊列的例子就是排隊。
JS版本的Queue
由于JS語言的特殊性，不存在真正意義上的Queue結構，一般使用數(shù)組特定的Api（push/shift）模擬最簡單的queue使得能夠滿足先進先出的特性唠椭。
let queue = [];
queue.push(1);
queue.push(2);
==== 入隊 1择克、2====
queue.shift() // 1出隊
queue.shift() // 2出隊
在一些簡單的場景下，利用數(shù)組來模擬隊列是可以滿足條件的。但是作為一個功能完備的數(shù)據(jù)結構，還有一些其他的功能，使用上述的實現(xiàn)方式顯的有點捉襟見肘局冰。
這里做一個簡單的補充：其實針對stack/queue的實現(xiàn)方式有兩種测蘑，一種是利用數(shù)組實現(xiàn)一個存儲地址連續(xù)的結構，另外一種實現(xiàn)方式是利用鏈表實現(xiàn)存儲地址不連續(xù)的結構康二。
那么碳胳，我們就自己實現(xiàn)一個比較功能完備的queue。它有如下的功能點
-
enqueue(element(s))：向隊列尾部添加一個（或多個）新的項赠摇。 -
dequeue()：移除隊列的第一項（即排在隊列最前面的項）并返回被移除的元素固逗。 -
peek()：返回隊列中第一個元素——最先被添加，也將是最先被移除的元素藕帜。隊列不做任何變動（不移除元素烫罩，只返回元素信息——與Stack類的peek方法非常類似）。 -
isEmpty()：如果隊列中不包含任何元素洽故，返回true贝攒，否則返回false。 -
size()：返回隊列包含的元素個數(shù)时甚，與數(shù)組的length屬性類似隘弊。
數(shù)組版本
class Queue {
constructor() {
this.items = [];
}
// 入隊
enqueue(element) {
this.items.push(element);
}
// 出隊，并返回隊首元素
dequeue() {
return this.items.shift();
}
// 查看荒适，隊首元素
peek() {
return this.items[0]
}
// 如果隊列里沒有任何元素就返回`true`,否則返回`false`
isEmpty() {
return this.items.length === 0;
}
// 返回隊列的元素個數(shù)
size() {
return this.items.length;
}
// 移除隊列里所有的元素
clear() {
this.items = [];
}
}
上面是使用數(shù)組來實現(xiàn)queue,能夠?qū)崿F(xiàn)基本的CRUD梨熙。但是，如果還記得我們在介紹stack的時候刀诬，也利用數(shù)組實現(xiàn)了一個Stack咽扇。
下面是用數(shù)組實現(xiàn)stack和queue的具體代碼∩乱迹可以發(fā)現(xiàn)质欲，在利用數(shù)組實現(xiàn)這兩個數(shù)據(jù)結構時候，除了針對剔除/查看數(shù)據(jù)有點不同糠馆，其他方法都一模一樣嘶伟。(除去方法名的差異)
在針對一些不強調(diào)消耗和性能的情況下，用數(shù)組實現(xiàn)queue是一個不錯且簡單的方式又碌。但是九昧，由于queue刪除數(shù)據(jù)的位置是在隊首。在利用數(shù)組實現(xiàn)的queue中毕匀，每次刪除一個元素铸鹰，數(shù)組剩余的元素的序號地址，都需要進行變更期揪。這樣會造成不必要的性能損耗。
所以规个，大部分情況下凤薛，queue是利用鏈表構建的姓建。
鏈表版本
這里再做一個簡單說明，在js中缤苫，對象類型數(shù)據(jù),它本身就是一個以零散方式存儲的速兔。我們來簡單做一個實驗。
class TestObject {
constructor() {
this.elements = {
o1:{},
o2:{},
};
}
}
let to = new TestObject()
我們利用Memory獲取了活玲，此時內(nèi)存信息涣狗。我們特意查看了TestObject中elements發(fā)現(xiàn)，針對他兩個屬性o1/o2所存的數(shù)據(jù)都放在不同的內(nèi)存地址上舒憾。
我們可以使用對象來存儲元素信息镀钓。這樣，就不需要額外的構建鏈表節(jié)點镀迂。
class Queue {
constructor() {
this.elements = {};
this.head = 0;
this.tail = 0;
}
enqueue(element) {
this.elements[this.tail] = element;
this.tail++;
}
dequeue() {
const item = this.elements[this.head];
delete this.elements[this.head];
this.head++;
return item;
}
peek() {
return this.elements[this.head];
}
size() {
return this.tail - this.head;
}
isEmpty() {
return this.tail - this.head === 0;
}
}
滑動窗口
在數(shù)組中某一個長度的子數(shù)組可以看成數(shù)組的一個窗口丁溅。若給定數(shù)組[1,2,3,4,5,6],那么子數(shù)組[2,3,4]就是其中一個大小為3的窗口。窗口向右滑動一個數(shù)字探遵，那么窗口就包含數(shù)字[3,4,5]窟赏。
也就是向右滑動窗口，每向右滑動一個數(shù)字箱季，都在窗口的最右邊插入一個數(shù)字涯穷，同時把最左邊的數(shù)字刪除。即滿足隊列 先進先出的特性藏雏。
滑動窗口的平均值
題目描述：
給定一個整數(shù)數(shù)據(jù)流和一個窗口大小拷况，根據(jù)該滑動窗口的大小，計算滑動窗口里所有數(shù)字的平均值诉稍。
- 該類型的構造函數(shù)的參數(shù)確定滑動窗口的大小
- 每次調(diào)用
next函數(shù)蝠嘉，會在滑動窗口中添加一個整數(shù)，并返回滑動窗口的所有數(shù)字的平均值
分析
- 在窗口中添加數(shù)字杯巨，當窗口中的數(shù)字的數(shù)目超過限制時蚤告，還可以從窗口中刪除數(shù)字。
- 例如服爷，當窗口的大小為3,在添加第四個數(shù)字時杜恰，就需要從窗口中刪除最早添加進來的數(shù)字。
- 這是一種先進先出的順序仍源，對應的數(shù)據(jù)容器為隊列
- 每次在窗口中添加數(shù)字之后心褐，需要判斷是否超出窗口的大小限制。如果超出限制笼踩，從隊列中刪除一個數(shù)字
- 利用
sum實時記錄逗爹，窗口中現(xiàn)存數(shù)據(jù)的和
代碼實現(xiàn)
class MovingAverage {
constructor(size) {
this.nums = new Queue();
this.capacity = size;
this.sum = 0;
}
next(val) {
this.nums.enqueue(val);
this.sum+=val;
if(this.nums.size()>this.capacity){
this.sum -=this.nums.dequeue();
}
return this.sum / this.nums.size()
}
}
二叉樹的廣度優(yōu)先搜索（BFS）
二叉樹的廣度優(yōu)先搜索是從上到下按層遍歷二叉樹，從二叉樹的根節(jié)點開始嚎于，先遍歷二叉樹的第一層掘而，再遍歷第二層挟冠，以此類推。
通常基于隊列來實現(xiàn)二叉樹的廣度優(yōu)先搜索袍睡。
- 從二叉樹的根節(jié)點開始知染，先把根節(jié)點放入到一個隊列中，然后每次從隊列中取出一個節(jié)點遍歷斑胜。
- 如果該節(jié)點有左右子節(jié)點控淡，則分別將它們添加到隊列中。（先左后右）
- 以此類推止潘，直到所有節(jié)點都被遍歷
二叉樹節(jié)點
class TreeNode {
val: number
left: TreeNode | null
right: TreeNode | null
constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
this.val = (val===undefined ? 0 : val)
this.left = (left===undefined ? null : left)
this.right = (right===undefined ? null : right)
}
}
利用queue實現(xiàn)二叉樹廣度優(yōu)先遍歷
function bfs(root){
let queue = new Queue();
if(root!=null) {
queue.enqueue(root);
}
let result = [];
while(!queue.isEmpty()){
let node = queue.dequeue();
result.push(node.val)
if(node.left!=null){
queue.enqueue(node.left);
}
if(node.right!=null){
queue.enqueue(node.right);
}
}
return result;
}
由于queue的先進先出特性掺炭，二叉樹的某一層節(jié)點按照從左到右的順序插入隊列中。因此覆山，這些節(jié)點一定會按照從左到右的順序遍歷到竹伸。用廣度優(yōu)先(BFS)的順序遍歷二叉樹，很容易知道
- 每層最左邊或者最右邊的節(jié)點
- 每層的最大值或者最小值
也就是說簇宽，關于二叉樹的題目如果出現(xiàn)層的概念勋篓，嘗試用廣度優(yōu)先來解決問題。
二叉樹中每層的最大值
題目描述：
輸入一課二叉樹魏割，請找出二叉樹中每層的最大值譬嚣。
示例：輸入: root = [1,3,2,5,3,null,9]
輸出: [1,3,9]
用一個隊列實現(xiàn)二叉樹的廣度優(yōu)先搜索
分析
- 找出二叉樹中每層的最大值，在遍歷的時需要知道每層什么時候開始钞它，什么時候結束拜银。
- 因為，在某個時刻遭垛，隊列中可能存在位于不同層的節(jié)點尼桶，如果不做區(qū)分的話，是無法獲取到某層數(shù)據(jù)的最大值
- 解決上述問題的一個辦法就是計數(shù)
- 用兩個變量分別記錄兩層節(jié)點的數(shù)目
- 變量
current記錄當前遍歷這一層中位于隊列之中節(jié)點的數(shù)量 - 變量
next記錄下一層中位于隊列之中節(jié)點的數(shù)量
- 最開始把根節(jié)點插入隊列中锯仪，把變量
current初始化為1.- 逐個從隊列中取出節(jié)點遍歷
- 每當從隊列中取出一個節(jié)點時泵督，當前層的剩余節(jié)點數(shù)就少一個，即
current - 1 - 當前遍歷的節(jié)點有子節(jié)點庶喜，將子節(jié)點插入隊列中小腊，此時變量
next的數(shù)目增加1即next + 1
- 當
current的數(shù)值變成0時，表示當前層的所有節(jié)點都已經(jīng)遍歷完久窟。秩冈、- 此時，可以通過比較當前層的所有節(jié)點的值斥扛，找出最大值
- 在開始遍歷下一層節(jié)點之前
- 需要把
current的值設為next的值 - 變量
next重新初始化為0
- 需要把
代碼實現(xiàn)
function largestValues(root) {
let current = 0;
let next = 0;
let queue = new Queue();
let result = [];
if(root!=null){
queue.enqueue(root);
current++;
}
let max = Number.MIN_SAFE_INTEGER;
while(!queue.isEmpty()){
let node = queue.dequeue();
current--;
max = Math.max(max,node.val);
if(node.left!=null){
queue.enqueue(node.left);
next++;
}
if(node.right !=null){
queue.enqueue(node.right);
next++;
}
if(current==0){
result.push(max);
max = Number.MIN_SAFE_INTEGER;
current = next;
next = 0;
}
}
return result;
}
用兩個隊列實現(xiàn)二叉樹的廣度優(yōu)先搜索
分析
- 利用一個隊列區(qū)分不同的層入问，需要用到兩個變量
current/next，我們可以換一個思路。將不同層樹的節(jié)點芬失，存入不同的隊列中卷仑。-
queue1只放當前遍歷層的節(jié)點 -
queue2只放下一層的節(jié)點
-
- 最開始時，把二叉樹的根節(jié)點放入隊列
queue1中麸折。- 接下來，每次從隊列中取出一個節(jié)點遍歷
- 隊列
queue1用來存放當前遍歷層的節(jié)點粘昨，總是從隊列queue1中取出節(jié)點來遍歷 - 如果當前遍歷的節(jié)點有子節(jié)點垢啼，并且子節(jié)點位于下一層，則把子節(jié)點放入隊列
queue2
- 當隊列
queue1被清空時张肾，此時能夠獲取到當前層的最大值 - 在開始遍歷下一層之前芭析，
- 把隊列
queue1指向queue2 - 將隊列
queue2重新初始化為空隊列
- 把隊列
代碼實現(xiàn)
function largestValues(root) {
let q1 = new Queue();
let q2 = new Queue();
let result = [];
if(root!=null){
q1.enqueue(root);
}
let max = Number.MIN_SAFE_INTEGER;
while(!q1.isEmpty()){
let node = q1.dequeue();
max = Math.max(max,node.val);
if(node.left!=null){
q2.enqueue(node.left);
}
if(node.right !=null){
q2.enqueue(node.right);
}
if(q1.isEmpty()){
result.push(max);
max = Number.MIN_SAFE_INTEGER;
q1 = q2;
q2 = new Queue();
}
}
return result;
}
二叉樹最底層最左邊的值
題目描述：
輸入一課二叉樹，找出它最底層最左邊節(jié)點的值吞瞪。
示例：輸入: root = [1,2,3,4,null,5,6,null,null,7]
輸出: 7
分析
- 題目越短馁启，越需要咬文嚼字。
- 二叉樹
- 最底層
- 根據(jù)①所得芍秆，我們可以使用二叉樹的廣度優(yōu)先遍歷(BFS)來進行層級的處理惯疙。
- 最底層最左邊的節(jié)點就是最后一層的第一個節(jié)點
- 可以使用一個
bottomLeft來保存每層最左邊的節(jié)點的值。沒當新的層級出現(xiàn)時候妖啥，將bottomLeft的值變更為第一個節(jié)點的值霉颠。 - 需要區(qū)分不同的層，我們采用兩個隊列的方式來實現(xiàn)
代碼實現(xiàn)
function findBottomLeftValue(root){
let q1 = new Queue();
let q2 = new Queue();
q1.enqueue(root);
let bottomLeft = root.val;
while(!q1.isEmpty()){
let node = q1.dequeue();
if(node.left !=null){
q2.enqueue(node.left)
}
if(node.right !=null){
q2.enqueue(node.right)
}
if(q1.isEmpty()){
q1 = q2;
q2 = new Queue();
// 當q1為空時荆虱，開始遍歷下一層蒿偎，如果下一層還有節(jié)點，則更新bottomLeft
if(!q1.isEmpty()){
bottomLeft = q1.peek().val;
}
}
}
return bottomLeft
}
二叉樹的右側(cè)視圖
題目描述：
輸入一課二叉樹诉位，站在該二叉樹的右側(cè)，從上到下看到的節(jié)點構成二叉樹的右側(cè)視圖。
示例：輸入: root = [1,2,3,null,5,null,4]
輸出: [1,3,4]
分析
- 題目越怪枫耳，越需要向已知套路靠
- 根據(jù)右側(cè)視圖的概念和示例的結果分析钻心，其實它就是想要每層最右邊的一個節(jié)點摊沉，因此二叉樹的右側(cè)視圖其實就是從上到下每層最右邊的節(jié)點
- 有幾個關鍵節(jié)點
- 二叉樹
- 區(qū)分不同的層
- 最右邊的節(jié)點
- 直接二叉樹bfs安排上
代碼實現(xiàn)
function rightSideView(root){
let result = [];
if(root==null) return result;
let q1 = new Queue();
let q2 = new Queue();
q1.enqueue(root);
while(!q1.isEmpty()){
let node = q1.dequeue();
if(node.left!=null){
q2.enqueue(node.left)
}
if(node.right !=null){
q2.enqueue(node.right)
}
if(q1.isEmpty()){
result.push(node.val); //此時node是當前層的最后一個節(jié)點
q1= q2;
q2 = new Queue();
}
}
return result;
}
后記
分享是一種態(tài)度苍柏。
參考資料：劍指offer/leetcode官網(wǎng)/學習JavaScript數(shù)據(jù)結構與算法第3版
全文完棺棵，既然看到這里了，如果覺得不錯，隨手點個贊和“在看”吧。
