數(shù)據(jù)結(jié)構(gòu)有許多種吞杭，上篇文章分享的是可以存儲簡單數(shù)據(jù)的列表盏浇，例如待辦事項，購物清單等芽狗。今天要跟大家分享的是兩種非常常見的也必須了解的數(shù)據(jù)結(jié)構(gòu)——棧與隊列绢掰。
棧的定義
什么是棧呢？它是一種“后入先出”的數(shù)據(jù)結(jié)構(gòu)，它跟列表一樣滴劲，都是可以用來存儲數(shù)據(jù)攻晒，但是卻要比列表嚴格的多，棧的數(shù)據(jù)只能在棧頂添加或刪除班挖。舉個例子鲁捏，在麥當勞用餐時的那些盤子，撿餐員在拿盤子時聪姿，總是從一摞盤子的最上端拿（棧頂）碴萧，然后放上食品在端給客人，而那些擦餐盤的人末购，也總是在最上面拿起餐盤擦拭后不斷地疊放成一摞餐盤，這里的餐盤就可看成是棧虎谢，數(shù)據(jù)的添加或刪除總是在最上端進行盟榴。下圖展示了棧的構(gòu)成以及簡單的入棧與出棧過程。
棧的主要操作方法
棧的常用操作就是入棧和出棧婴噩，入棧用的是 push() 方法擎场，出棧用的是 pop() 方法，還有一個方法是 peek() 几莽，該方法可以返回棧頂?shù)脑囟粍h除它迅办，相應(yīng)的 pop() 方法雖然也可以得到棧頂?shù)脑兀珪⑺鼊h除章蚣。
棧的實現(xiàn)
在 JavaScript 中站欺，通常使用數(shù)組來實現(xiàn)棧。下面我們定義一個名為 Stack 的構(gòu)造函數(shù)用來表示棧纤垂。
function Stack() {
this.dataStore = [];
this,top = 0;
this.push = push;
this.pop = pop;
this.peek = peek;
}
dataStore 是一個數(shù)組矾策，用來存儲棧中的元素，而變量 top 記錄棧頂?shù)奈恢们吐伲跏嘉恢脼?0贾虽，push 、pop 和 peek 分別對應(yīng)三個方法吼鱼，下面來實現(xiàn)這些方法蓬豁。
首先是 push() ,入棧。
function push() {
this.dataStore[this.top++] = element;
}
這里 top++ 很有意思菇肃，要知道 + 號在變量后和變量前是不同的地粪，這里的邏輯是，當元素入棧后巷送，變量 top 的值就對應(yīng)當前入棧元素的位置驶忌，然后 top++ ，自增后的值就是下一個元素入棧時的位置了。
接下來是出棧方法 pop() 付魔。
function pop() {
return this.dataStore[--this.top];
}
前面說了聊品，棧只能在最頂端添加、刪除數(shù)據(jù)几苍，所以我們必須要知道棧頂現(xiàn)在存放的是哪個數(shù)值才能將它刪除翻屈，于是我們使用 top 來標記它的位置，現(xiàn)在出棧妻坝，只需要把指向棧頂?shù)奈恢玫墓?jié)點數(shù)據(jù)拿掉就行了伸眶。
最后一個方法是取棧頂元素的 peek() 方法,相信也不難理解，就把棧頂元素直接返回就行刽宪，注意棧頂元素的位置是第 top - 1 個位置厘贼。
function peek() {
return this.dataStore[this.top - 1];
}
除了上述的基本操作方法外，還有其它方法可以有作用圣拄。來看下面這兩個方法
function length() {
return this.top;
}
function clear() {
this.top = 0;
}
上面的方法一個是可以獲取棧內(nèi)存儲了多少個元素的 length() 方法嘴秸， 另一個是 clear() ,聽名字就知道是把一個棧清空，通過將 top 的值歸零庇谆。
棧的完整代碼
棧的完整代碼以及測試如下
function Stack() {
this.dataStore = [];
this,top = 0;
this.push = push;
this.pop = pop;
this.peek = peek;
this.length = length;
this.clear = clear;
}
function push() {
this.dataStore[this.top++] = element;
}
function pop() {
return this.dataStore[--this.top];
}
function peek() {
return this.dataStore[this.top - 1];
}
function length() {
return this.top;
}
function clear() {
this.top = 0;
}
var s = new Stack();
s.push("xiaoming");
s.push("xiaohong");
s.push("Mike");
console.log("棧的長度為： "+s.length());
console.log(s.peek());
s.clear();
console.log("當前長度為： "+s.length());
運行結(jié)果為：
棧的長度為： 3
Mike
當前長度為： 0
隊列的定義
隊列是一種與棧截然不同的數(shù)據(jù)結(jié)構(gòu)岳掐，棧的特點是后入先出，最后入棧的元素會優(yōu)先處理而彈出饭耳，而隊列的特點則是先入先出串述，最先進棧的也會最終先出棧，這有點類似于銀行窗口前排隊辦業(yè)務(wù)的人群寞肖，排在最前面的先辦理業(yè)務(wù)纲酗，后面來的就依次排隊。
隊列的主要操作方法
與棧一樣逝淹，隊列也是用數(shù)組來實現(xiàn)耕姊，它的主要操作方法同樣是入隊（enqueue）,出隊（dequeue）和讀取隊頭的元素（peek）,讀取隊頭元素同樣不會刪除元素，只返回栅葡。此外還有清空隊列元素（clear）和獲取隊列元素個數(shù)（length）茉兰。
隊列的實現(xiàn)
首先定義一個 Queue 類用來表示隊列。
function Queue() {
this.dataStore = []; // 存儲隊列元素
this.enqueue = enqueue;
this.dequeue = dequeue;
this.front = front;
this.back = back;
this.toString = toString;
this.empty = empty;
}
接下來實現(xiàn)入隊方法 enqueue() ：
function enqueue(element) {
this.dataStore.push(element);
}
可以看到欣簇，用數(shù)組來實現(xiàn)隊列非常簡單规脸，入隊只需一個 push() 方法即可向隊尾添加元素。
function dequeue() {
return this.dataStore.shift();
}
shift 是數(shù)組的一個操作方法熊咽，可以將數(shù)組的第一個元素刪除莫鸭。
function front() {
return this,dataStore[0];
}
function back() {
return this.dataStore[this.dataStore.length - 1];
}
這兩個分別是讀取隊列的第一個元素和最后一個元素，很簡單横殴，直接返回數(shù)組的第一個元素和最后一個元素即可被因。
function toString() {
var str = "";
for (var i = 0; i < this.dataStore.length; i++) {
str += this.dataStore[i] + "\n";
}
return str;
}
這個方法顯示隊列元素卿拴，類似控制臺 console 輸出元素。
function empty() {
if (this.dataStore.length == 0) {
return true;
}
else {
return false;
}
}
這是一個判空方法梨与，每次使用隊列前要判斷是否為空才可進行下一步的操作堕花。
隊列完整代碼及測試
function Queue() {
this.dataStore = []; // 存儲隊列元素
this.enqueue = enqueue;
this.dequeue = dequeue;
this.front = front;
this.back = back;
this.toString = toString;
this.empty = empty;
}
function enqueue(element) {
this.dataStore.push(element);
}
function dequeue() {
return this.dataStore.shift();
}
function front() {
return this,dataStore[0];
}
function back() {
return this.dataStore[this.dataStore.length - 1];
}
function toString() {
var str = "";
for (var i = 0; i < this.dataStore.length; i++) {
str += this.dataStore[i] + "\n";
}
return str;
}
function empty() {
if (this.dataStore.length == 0) {
return true;
}
else {
return false;
}
}
var q = new Queue();
q.enqueue("Mike");
q.enqueue("Hello");
q.enqueue("hhhh");
console.log(q.toString());
q.dequeue();
console.log(q.toString());
console.log("隊列的第一個元素是: " + q.front());
console.log("隊列的最后一個元素是: " + q.back());
運行結(jié)果如下：
Mike
Hello
hhhh
Hello
hhhh
隊列的第一個元素是: Hello
隊列的最后一個元素是: hhhh
