資訊專欄INFORMATION COLUMN
摘要：隊(duì)列上一篇數(shù)據(jù)結(jié)構(gòu)講到了棧，隊(duì)列和棧非常類似。棧入棧后假設(shè)數(shù)據(jù)為，隊(duì)列遵循先入先出，所以的時(shí)候的順序應(yīng)該是那么下面我們看如何利用棧出棧。首先棧出棧后的數(shù)據(jù)則為正好倒過(guò)來(lái)我們利用循環(huán)將棧出棧的數(shù)據(jù)到棧，則棧中的數(shù)據(jù)就會(huì)是。
隊(duì)列
上一篇數(shù)據(jù)結(jié)構(gòu)講到了棧，隊(duì)列和棧非常類似。隊(duì)列也是一種特殊的列表，它與棧的區(qū)別在于，棧是先入后出，而隊(duì)列則是遵循FIFO先入先出的原則，換言之隊(duì)列只能在隊(duì)尾插入元素，而在隊(duì)列的頭部去刪除元素。
舉個(gè)簡(jiǎn)單的例子，隊(duì)列就相當(dāng)于在生活中排隊(duì)購(gòu)物，后來(lái)的人需要排在隊(duì)尾，而隊(duì)伍最前面的人會(huì)一次結(jié)賬后出列。隊(duì)列的應(yīng)用非常廣泛，常用于實(shí)現(xiàn)緩沖區(qū)，廣度優(yōu)先搜索，優(yōu)先級(jí)隊(duì)列等等。
隊(duì)列最主要的兩個(gè)操作分別是enqueue(入列)和dequeue(出列)
隊(duì)列的實(shí)現(xiàn)邏輯通過(guò)上面這張圖我們可以看到隊(duì)列的幾個(gè)特點(diǎn)
初始化
有一塊連續(xù)的空間用來(lái)去存儲(chǔ)隊(duì)列
有一個(gè)頭部指向第一個(gè)數(shù)據(jù)的地址
有一個(gè)尾部指向數(shù)據(jù)后一個(gè)空位的地址
空間的大小
隊(duì)列內(nèi)部數(shù)據(jù)的長(zhǎng)度
class Queue {
constructor(max=1000){
// 定義一塊連續(xù)的存儲(chǔ)空間用來(lái)存儲(chǔ)數(shù)據(jù)
this.data = new Array(1000);
// 開(kāi)辟的空間大小
this.max = max;
// 頭部位置
this.head = 0;
// 尾部位置
this.tail = 0;
// 數(shù)據(jù)長(zhǎng)度
this.size = 0;
}
}
enqueue 入列
當(dāng)數(shù)據(jù)長(zhǎng)度超出了開(kāi)辟的空間大小會(huì)報(bào)overflow的錯(cuò)誤
向尾部添加新數(shù)據(jù)
尾部指針向后挪動(dòng)一位，如果尾部沒(méi)有空間，則指向0（見(jiàn)上圖的兩個(gè)enqueue操作）
enqueue(x) {
// 溢出
if(this.size === this.max){
throw "overflow"
}
// 添加新數(shù)據(jù)到尾部
this.data[this.tail] = x;
// 數(shù)據(jù)長(zhǎng)度+1
this.size++;
// 尾部指針向后挪動(dòng)一位，如果后面沒(méi)有空間，則指向0
if(this.tail === this.max-1){
this.tail = 0;
}else{
this.tail++
}
}
dequeue出列
如果當(dāng)前數(shù)據(jù)長(zhǎng)度為0，則拋出underflow的錯(cuò)誤
取出頭部位置的數(shù)據(jù)
頭部指針向后挪動(dòng)一位
數(shù)據(jù)長(zhǎng)度-1
返回該數(shù)據(jù)
dequeue(){
if(this.size === 0){
throw "underflow";
}
const x = this.data[this.head];
this.head++;
this.size--;
return x;
}
整個(gè)代碼
class Queue {
constructor(max = 1000) {
this.data = new Array(max);
this.max = max;
this.head = 0;
this.tail = 0;
this.size = 0;
}
// 入列
enqueue(x) {
if (this.size === this.max) {
throw "overflow";
}
this.data[this.tail] = x;
this.size++;
if (this.tail === this.max - 1) {
this.tail = 0;
} else {
this.tail++;
}
}
// 出列
dequeue() {
if (this.size === 0) {
throw "underflow";
}
const x = this.data[this.head];
this.head++;
this.size--;
return x;
}
get length() {
return this.size;
}
}
module.exports = Queue;
擴(kuò)展--棧實(shí)現(xiàn)隊(duì)列
隊(duì)列也可以通過(guò)兩個(gè)棧來(lái)實(shí)現(xiàn)，不了解棧的同學(xué)可以看上一篇關(guān)于棧文章，接下來(lái)會(huì)引入之前寫(xiě)好的棧，具體代碼見(jiàn)下面。
// 上一節(jié)中，棧的實(shí)現(xiàn)代碼
const Stack = require("./stack");
class Queue {
constructor(max=1000){
// 實(shí)例化兩個(gè)棧，分別是s1和s2, s1棧用來(lái)做入列,s2棧用來(lái)出列使用
this.s1 = new Stack(max);
this.s2 = new Stack(max);
this.max = max;
}
// 入列
enqueue(x) {
if(this.s1.length === this.max){
throw "overflow"
}
// s1作為入列
this.s1.push(x);
}
// 出列
dequeue(){
if(this.s2.length>0){
return this.s2.pop;
}
while(this.s1.length){
this.s2.push(this.s1.pop());
}
return this.s2.pop();
}
}
在這里大致簡(jiǎn)單的說(shuō)明一下以上用兩個(gè)棧來(lái)實(shí)現(xiàn)隊(duì)列的邏輯吧。
棧s1 入棧后假設(shè)數(shù)據(jù)為 1,2,3,4,5，隊(duì)列遵循先入先出，所以dequeue的時(shí)候的順序應(yīng)該是1,2,3,4,5,那么下面我們看如何利用棧s2出棧。
首先棧s1 pop()出棧后的數(shù)據(jù)則為 5,4,3,2,1 正好倒過(guò)來(lái), 我們利用循環(huán)將棧s1出棧的數(shù)據(jù)push到棧s2，則棧s2中的數(shù)據(jù)就會(huì)是5,4,3,2,1。下面我們?cè)賵?zhí)行s2.pop()的時(shí)候，是不是就能剛好能依次拿到1,2,3,4,5這幾個(gè)數(shù)據(jù)了
后續(xù)下一張的數(shù)據(jù)結(jié)構(gòu)會(huì)為大家介紹鏈表
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://www.ezyhdfw.cn/yun/100531.html
摘要：任務(wù)隊(duì)列中的代碼被加載到函數(shù)調(diào)用棧中去執(zhí)行。說(shuō)到這里，你基本上對(duì)事件循環(huán)有個(gè)大致的了解了。 在理解事件循環(huán)之前，我總會(huì)遇到一些奇奇怪怪的問(wèn)題：比如明明已經(jīng)調(diào)接口拿到了數(shù)據(jù)，可是跟在調(diào)數(shù)據(jù)之后的操作卻沒(méi)有正常執(zhí)行；又或者不知道為啥，代碼里非得加個(gè)setTimeout才能正常跑通；特別是在運(yùn)用Promise的時(shí)候，更是有各種問(wèn)題百思不得解。遇上問(wèn)題要解決，更要知道問(wèn)題產(chǎn)生的原因，這樣才能h...
摘要：內(nèi)存空間又被分為兩種，棧內(nèi)存與堆內(nèi)存。今天就堆棧隊(duì)列的內(nèi)容就大概說(shuō)到這里下一篇博客在繼續(xù)說(shuō)一下，有什么說(shuō)的不對(duì)或者不足的地方，請(qǐng)大家批評(píng)指正 棧的定義 棧是計(jì)算機(jī)科學(xué)中的一種抽象數(shù)據(jù)類型，只允許在有序的線性數(shù)據(jù)集合的一端（稱為堆棧頂端，英語(yǔ)：top）進(jìn)行加入數(shù)據(jù)（英語(yǔ)：push）和移除數(shù)據(jù)（英語(yǔ)：pop）的運(yùn)算。因而按照后進(jìn)先出（LIFO, Last In First Out）的原理運(yùn)...
摘要：隊(duì)列是一種先進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)，與棧不同的是，它操作的元素是在兩端，而且進(jìn)行的是不一樣的操作。 隊(duì)列(Queue)是一種先進(jìn)先出(First-In-First-Out, FIFO)的數(shù)據(jù)結(jié)構(gòu)，與棧不同的是，它操作的元素是在兩端，而且進(jìn)行的是不一樣的操作。向隊(duì)列的隊(duì)尾加入一個(gè)元素叫做入隊(duì)列(enQueue)，向隊(duì)列的隊(duì)首刪除一個(gè)元素叫做出隊(duì)列(delQueue). showImg(http...
摘要：而且目前大部分編程語(yǔ)言的高級(jí)應(yīng)用都會(huì)用到數(shù)據(jù)結(jié)構(gòu)與算法以及設(shè)計(jì)模式。隊(duì)列在尾部添加新元素，并從頂部移除元素。最新添加的元素必須排在隊(duì)列的末尾。 前言 JavaScript是當(dāng)下最流行的編程語(yǔ)言之一，它可以做很多事情： 數(shù)據(jù)可視化（D3.js，Three.js，Chart.js）; 移動(dòng)端應(yīng)用(React Native,Weex,AppCan,Flutter,Hybrid App,小程...
摘要：異步請(qǐng)求線程在在連接后是通過(guò)瀏覽器新開(kāi)一個(gè)線程請(qǐng)求將檢測(cè)到狀態(tài)變更時(shí)，如果設(shè)置有回調(diào)函數(shù)，異步線程就產(chǎn)生狀態(tài)變更事件，將這個(gè)回調(diào)再放入事件循環(huán)隊(duì)列中。 基礎(chǔ)：瀏覽器 -- 多進(jìn)程，每個(gè)tab頁(yè)獨(dú)立一個(gè)瀏覽器渲染進(jìn)程（瀏覽器內(nèi)核） 每個(gè)瀏覽器渲染進(jìn)程是多線程的，主要包括：GUI渲染線程 JS引擎線程 也稱為JS內(nèi)核，負(fù)責(zé)處理Javascript腳本程序。（例如V8引擎） JS引擎線程負(fù)...
摘要：的單線程，與它的用途有關(guān)。特點(diǎn)的顯著特點(diǎn)異步機(jī)制事件驅(qū)動(dòng)。隊(duì)列的讀取輪詢線程，事件的消費(fèi)者，的主角。它將不同的任務(wù)分配給不同的線程，形成一個(gè)事件循環(huán)，以異步的方式將任務(wù)的執(zhí)行結(jié)果返回給引擎。 這兩天跟同事同事討論遇到的一個(gè)問(wèn)題，js中的event loop，引出了chrome與node中運(yùn)行具有setTimeout和Promise的程序時(shí)候執(zhí)行結(jié)果不一樣的問(wèn)題，從而引出了Nodejs的...
閱讀 1371·2023-04-26 01:03
閱讀 2017·2021-11-23 09:51
閱讀 3375·2021-11-22 15:24
閱讀 2727·2021-09-22 15:18
閱讀 1066·2019-08-30 15:55
閱讀 3620·2019-08-30 15:54
閱讀 2375·2019-08-30 15:53
閱讀 2442·2019-08-30 15:44
