js數據結構和算法（二）棧和隊列

jsummer 發布于2019-08-21 12:30 / 568人閱讀

摘要：對于棧來說，這個表尾稱為棧的棧頂，相應的表頭稱為棧底。棧和隊列的區別棧的插入和刪除操作都是在一端進行的，而隊列的操作卻是在兩端進行的。出棧操作出棧操作就是在棧頂取出數據，棧頂指針隨之下移的操作。

基本概念

棧和隊列都是動態的集合，在棧中，可以去掉的元素是最近插入的哪一個。棧實現了后進先出。在隊列中，可以去掉的元素總是在集合中存在的時間最長的那一個。隊列實現了先進先出的策略。

棧的官方定義：棧（Stack）是一個后進先出（Last in first out,LIFO）的線性表，它要求只在表尾進行刪除和插入操作。對于棧來說，這個表尾稱為棧的棧頂，相應的表頭稱為棧底。入棧使用push()方法。出棧使用pop()方法。

最開始棧中不含有任何數據，叫做空棧，此時棧頂就是棧底。然后數據從棧頂進入，棧頂棧底分離，整個棧的當前容量變大。數據出棧時從棧頂彈出，棧頂下移，整個棧的當前容量變小。

我們把作用于隊列上的INSERT操作稱為入隊（Enqueue），把作用于隊列上的DELETE操作稱為出隊（Dequeue）。我們使用變量top來記錄棧頂元素的位置和標記哪里可以加入新的元素，當向棧內壓入元素時，該變量增大；從棧內彈出元素時，該變量減小。

棧和隊列的區別

棧的插入和刪除操作都是在一端進行的，而隊列的操作卻是在兩端進行的。

typedef struct
{
    ElemType *base;
    ElemType *top;
    int stackSize;
}sqStack;

這里定義了一個順序存儲的棧，它包含了三個元素：base,top,stackSize。

其中base是指向棧底的指針變量，top是指向棧頂的指針變量，stackSize指示棧的當前可使用的最大容量。

創建一個棧

#define STACK_INIT_SIZE 100

initStack(sqStack *s)
{
    s->base = (ElemType *)malloc( STACK_INIT_SIZE * sizeof(ElemType) );
    if( !s->base )
        exit(0);

    s->top = s->base;   // 最開始，棧頂就是棧底
    s->stackSize = STACK_INIT_SIZE;
}

入棧操作

入棧操作又叫壓棧操作，就是向棧中存放數據。

入棧操作要在棧頂進行，每次向棧中壓入一個數據，top指針就要+1，知道棧滿為止。

出棧操作

出棧操作就是在棧頂取出數據，棧頂指針隨之下移的操作。

每當從棧內彈出一個數據，棧的當前容量就-1。

隊列的順序存儲結構

入隊列操作其實就是在隊尾追加一個元素，不需要任何移動，時間復雜度為O(1)。

出隊列則不同，因為我們已經架設下標為0的位置是隊列的隊頭，因此每次出隊列操作所有元素都要向前移動。

棧的方法和屬性

push()：入棧操作
pop()：出棧操作（返回棧頂元素并刪除t）
peak()：返回棧頂元素而不刪除它
clear()：清除棧內所有元素
length()：記錄棧內元素的個數
empty屬性：表示棧內是否含有元素

棧的實現

function Stack(){
    this.dataStore = [];
    this.top = 0;
    this.push = push;
    this.pop = pop;
    this.peek = peek;
}

用一個數組dataStore來保存棧內元素，變量top記錄棧頂位置

push()方法

先來實現push()方法，當向棧中壓入一個新元素時，需要將其保存在數組中變量top對應的位置，然后將top值加1：

 function push(element){
        this.dataStore[this.top++] = element;//top值加1，指向下一個空位置
    }

pop()方法

function pop(){
    return this.dataStore[--this.top];//pop方法與push相反
}

peek()方法

peek方法返回數組的第一個top-1位置的元素，即棧頂元素：

function peek(){
    return this.dataStore[this.top-1];
}

length()方法

length方法通過返回變量top值的方法返回棧內的元素的個數：

function length(){
    return this.top;
}

clear()方法

將變量top的值設為0，就可以清空一個棧了：

function clear(){
    this.top = 0;
}

云服務器 GPU云服務器棧和隊列面試題棧和隊列 c語言棧和隊列的c語言 js算法和數據結構

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/87637.html

js數據結構與算法--棧和隊列

摘要：后入先出入棧使用方法，出棧使用方法入棧出棧出站隊列隊列是一種特殊的線性表，特殊之處在于它只允許在表的前端進行刪除操作，而在表的后端進行插入操作，和棧一樣，隊列是一種操作受限制的線性表。 1.棧（stack）棧（stack）又名堆棧，它是一種運算受限的線性表。其限制是僅允許在表的一端進行插入和刪除運算。這一端被稱為棧頂，相對地，把另一端稱為棧底。向一個棧插入新元素又稱作進棧、入棧或壓棧...

ddongjian0000 2019-08-22 15:49 評論0 收藏0
CSS技巧

摘要：技巧使你的更加專業這是上關于技巧的一篇譯文，另外你也可以在本項目看到原文。列舉了一些很實用的技巧，比如給空內容的標簽添加內容，逗號分隔列表等等。排序算法看源碼，把它背下來吧排序算法的封裝。主要幫助初學者更好的掌握排序算法的實現。成為專業程序員路上用到的各種優秀資料、神器及框架成為一名專業程序員的道路上，需要堅持練習、學習與積累，技術方面既要有一定的廣度，更要有自己的深度。 Java...

DangoSky 2019-08-22 11:15 評論0 收藏0
CSS技巧

摘要：技巧使你的更加專業這是上關于技巧的一篇譯文，另外你也可以在本項目看到原文。列舉了一些很實用的技巧，比如給空內容的標簽添加內容，逗號分隔列表等等。排序算法看源碼，把它背下來吧排序算法的封裝。主要幫助初學者更好的掌握排序算法的實現。成為專業程序員路上用到的各種優秀資料、神器及框架成為一名專業程序員的道路上，需要堅持練習、學習與積累，技術方面既要有一定的廣度，更要有自己的深度。 Java...

zgbgx 2019-08-29 14:01 評論0 收藏0
JS數據結構與算法_鏈表

摘要：上一篇數據結構與算法棧隊列下一篇數據結構與算法集合字典寫在前面說明數據結構與算法系列文章的代碼和示例均可在此找到上一篇博客發布以后，僅幾天的時間竟然成為了我寫博客以來點贊數最多的一篇博客。上一篇：JS數據結構與算法_棧&隊列下一篇：JS數據結構與算法_集合&字典寫在前面說明：JS數據結構與算法系列文章的代碼和示例均可在此找到上一篇博客發布以后，僅幾天的時間竟然成為了我寫博客以...

NeverSayNever 2019-08-23 14:53 評論0 收藏0