JavaScript中的數據結構——棧和隊列

棧在JavaScript中的實現和原理

棧(stack)，也稱堆棧，在計算機科學領域中，棧是一種線性數據結構，它只能在數據串列或陣列的一端進行入棧(push)和出棧(pop)操作，按照後進先出(LIFO)原理進行運作，一張圖表示棧的工作如圖1：

下面將使用JavaScript實現這一數據結構。

棧的操作

根據棧的工作方式，我們定義棧的兩個操作：

1.push(data):加入數據，也稱入棧。

2.pop():將最近加入的數據移除，也稱出棧。

棧的具體實現

通過使用JavaScript構造函數和原型的方式實現棧的功能。每個構造函數擁有_size和_storage兩個屬性。

_storage:存儲棧的數據，使用對象作為棧數據的集合；

_size:棧的數據長度，當棧新增加(push)一個數據,時，size長度加1，當棧彈出(pop)一個數據，size長度減1。

有了Stack構造函數，接下來通過原型對象實現push(data)方法（因為push方法時所有棧共有方法，故使用prototype使得該方法共享）。

push(data)方法需要具備以下兩個功能：

1.每次增加一個數據，我們希望增加棧的數據長度；

2.每次增加一個數據，我們希望將此數據加在棧的頂端。

具體的代碼實現如下：

push(data)方法之後就是pop()方法，針對pop()的設計思想是：

1.通過棧的當前的長度獲取棧頂數據；

2.刪除第一步獲得的棧頂數據；

3.棧長度size減1；

4.返回彈出棧的數據。

具體的代碼實現如下：

故JavaScript實現棧功能的完整代碼如下：

另一種實現方式

上面是通過構造函數和原型模式實現了棧的push(data)和pop()操作，實際上，JavaScript的Array已經有現成的push()和pop()方法，通過這兩個現成的方法可以輕鬆實現數據的棧操作。

firebug下的運行結果如下：

文章來源：

http://geocld.github.io/2015/12/28/stack_in_javascript/

隊列在JavaScript中的實現和原理

隊列(queue)與棧(stack)類似，也是一種線性結構，操作與棧類似，但與棧不同的是，隊列使用的是先進先出(FIFO)的操作方式，隊列的操作和生活中的排隊一樣，排隊的隊伍中，先到的在隊伍前排的會先處理，後來排隊的後處理，一張圖表示如下：

隊列的操作

隊列的操作和棧非常類似，根據棧的操作，這裡定義三個隊列操作：

1.size()：隊列長度

2.enqueue(data)： 添加數據插入隊尾。

3.dequeue()：讀取隊列頭節點數據並刪除該節點。

可以發現在操作方法上，隊列和棧就已經有區別了，隊列多了一個計算長度的size()方法，這是因為隊列的兩端操作有關，後面會進行介紹。

隊列的具體實現

同樣先使用構造函數+原型模式實現隊列操作，構造函數需要具備三個屬性：_oldestIndex，_newestIndex和_storage:

_newestIndex：隊列隊尾元素「指針」；

_storage：隊列的存儲空間。

size()方法

計算隊列的長度需要使用兩個變數_oldestIndex和_newestIndex，而在棧計算長度是只使用了一個size變數，存在這種差異的原因與兩種數據結構的數據出入方式不同有關。

棧的方式為LIFO，元素的操作只會在棧頂發生，棧底元素的位置不會變，故只用簡單的加減法即可計算出棧的長度。

但是隊列卻不同，正如上圖顯示的，隊列的操作為FIFO操作，元素的進出發生在隊列的兩端，如果只用一個size進行簡單的加減法操作，我們無法準確獲得隊列當前隊首和隊尾的位置，這時候，就需要使用兩個變數(在C語言里就是指針)記錄隊首和隊尾的位置。

故隊列的size()具體實現如下：

enqueue(data)和dequeue()方法

有了size()的原理後，enqueue(data)和dequeue()操作就簡單多了。

先是enqueue(data)方法，這個方法的操作會影響兩個變數：

1.使用_storage對象存儲新加入的元素；

2._newestIndex作為隊尾的鍵值，當新元素入隊時，_newestIndex加1，初始值為1。

使用JavaScript實現的具體代碼如下：

接下來是dequeue()操作，該操作有一樣有兩個變數受影響：

1.使用當前的_oldestIndex作為鍵值從_storage中刪除排在最前面的元素；

2._oldestIndex鍵值加1，指向當前新的隊首元素的位置。

具體實現代碼如下：

故JavaScript實現隊列操作的完整代碼如下：

隊列的另一種實現方式

在棧的操作中，最後使用了數組的push()和pop()操作模擬了棧的操作，同樣的，隊列操作也可以，在棧操作的基礎上使用reverse()可以輕鬆模擬，具體代碼如下：

總結

通過本文和上文的介紹，對常用的兩種線性數據結構——棧和隊列進行了介紹：棧存儲數據並從最新的元素中進行出棧操作；隊列存儲數據並從最舊的元素中進行出隊操作。並通過JavaScript實現了這兩種數據結構的操作。

在具體的實際使用中，棧操作和隊列操作比上面所說的複雜很多，但是基本的設計原則如下：

如果需要解決的問題是需要對數據進行有序操作，那麼優先考慮棧和隊列。

文章來源：

http://geocld.github.io/2015/12/29/queue_in_javascript/?utm_source=tuicool&utm_medium=referral

點擊展開全文

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！