亚洲中字慕日产2020,大陆极品少妇内射AAAAAA,无码av大香线蕉伊人久久,久久精品国产亚洲av麻豆网站

資訊專欄INFORMATION COLUMN

js數(shù)據(jù)結(jié)構(gòu)和算法（二）棧和隊(duì)列

jsummer / 607人閱讀

摘要：對(duì)于棧來(lái)說(shuō)，這個(gè)表尾稱為棧的棧頂，相應(yīng)的表頭稱為棧底。棧和隊(duì)列的區(qū)別棧的插入和刪除操作都是在一端進(jìn)行的，而隊(duì)列的操作卻是在兩端進(jìn)行的。出棧操作出棧操作就是在棧頂取出數(shù)據(jù)，棧頂指針隨之下移的操作。

基本概念

棧和隊(duì)列都是動(dòng)態(tài)的集合，在棧中，可以去掉的元素是最近插入的哪一個(gè)。棧實(shí)現(xiàn)了后進(jìn)先出。在隊(duì)列中，可以去掉的元素總是在集合中存在的時(shí)間最長(zhǎng)的那一個(gè)。隊(duì)列實(shí)現(xiàn)了先進(jìn)先出的策略。

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

最開(kāi)始棧中不含有任何數(shù)據(jù)，叫做空棧，此時(shí)棧頂就是棧底。然后數(shù)據(jù)從棧頂進(jìn)入，棧頂棧底分離，整個(gè)棧的當(dāng)前容量變大。數(shù)據(jù)出棧時(shí)從棧頂彈出，棧頂下移，整個(gè)棧的當(dāng)前容量變小。

我們把作用于隊(duì)列上的INSERT操作稱為入隊(duì)（Enqueue），把作用于隊(duì)列上的DELETE操作稱為出隊(duì)（Dequeue）。我們使用變量top來(lái)記錄棧頂元素的位置和標(biāo)記哪里可以加入新的元素，當(dāng)向棧內(nèi)壓入元素時(shí)，該變量增大；從棧內(nèi)彈出元素時(shí)，該變量減小。

棧和隊(duì)列的區(qū)別

棧的插入和刪除操作都是在一端進(jìn)行的，而隊(duì)列的操作卻是在兩端進(jìn)行的。

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

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

其中base是指向棧底的指針變量，top是指向棧頂?shù)闹羔樧兞?，stackSize指示棧的當(dāng)前可使用的最大容量。

創(chuàng)建一個(gè)棧 
#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;   // 最開(kāi)始，棧頂就是棧底
    s->stackSize = STACK_INIT_SIZE;
}
入棧操作

入棧操作又叫壓棧操作，就是向棧中存放數(shù)據(jù)。

入棧操作要在棧頂進(jìn)行，每次向棧中壓入一個(gè)數(shù)據(jù)，top指針就要+1，知道棧滿為止。

出棧操作

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

每當(dāng)從棧內(nèi)彈出一個(gè)數(shù)據(jù)，棧的當(dāng)前容量就-1。

隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)

入隊(duì)列操作其實(shí)就是在隊(duì)尾追加一個(gè)元素，不需要任何移動(dòng)，時(shí)間復(fù)雜度為O(1)。

出隊(duì)列則不同，因?yàn)槲覀円呀?jīng)架設(shè)下標(biāo)為0的位置是隊(duì)列的隊(duì)頭，因此每次出隊(duì)列操作所有元素都要向前移動(dòng)。

棧的方法和屬性 
push()：入棧操作
pop()：出棧操作（返回棧頂元素并刪除t）
peak()：返回棧頂元素而不刪除它
clear()：清除棧內(nèi)所有元素
length()：記錄棧內(nèi)元素的個(gè)數(shù)
empty屬性：表示棧內(nèi)是否含有元素
棧的實(shí)現(xiàn) 
function Stack(){
    this.dataStore = [];
    this.top = 0;
    this.push = push;
    this.pop = pop;
    this.peek = peek;
}

用一個(gè)數(shù)組dataStore來(lái)保存棧內(nèi)元素，變量top記錄棧頂位置

push()方法

先來(lái)實(shí)現(xiàn)push()方法，當(dāng)向棧中壓入一個(gè)新元素時(shí)，需要將其保存在數(shù)組中變量top對(duì)應(yīng)的位置，然后將top值加1：

 function push(element){
        this.dataStore[this.top++] = element;//top值加1，指向下一個(gè)空位置
    }
pop()方法 
function pop(){
    return this.dataStore[--this.top];//pop方法與push相反
}
peek()方法

peek方法返回?cái)?shù)組的第一個(gè)top-1位置的元素，即棧頂元素：

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

length方法通過(guò)返回變量top值的方法返回棧內(nèi)的元素的個(gè)數(shù)：

function length(){
    return this.top;
}
clear()方法

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

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

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://www.ezyhdfw.cn/yun/87637.html

相關(guān)文章

  • js數(shù)據(jù)結(jié)構(gòu)與算法--棧和隊(duì)列

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

    ddongjian0000 評(píng)論0 收藏0

  • CSS技巧

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

    DangoSky 評(píng)論0 收藏0

  • CSS技巧

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

    zgbgx 評(píng)論0 收藏0

  • JS數(shù)據(jù)結(jié)構(gòu)與算法_鏈表

    摘要：上一篇數(shù)據(jù)結(jié)構(gòu)與算法棧隊(duì)列下一篇數(shù)據(jù)結(jié)構(gòu)與算法集合字典寫(xiě)在前面說(shuō)明數(shù)據(jù)結(jié)構(gòu)與算法系列文章的代碼和示例均可在此找到上一篇博客發(fā)布以后，僅幾天的時(shí)間竟然成為了我寫(xiě)博客以來(lái)點(diǎn)贊數(shù)最多的一篇博客。 上一篇：JS數(shù)據(jù)結(jié)構(gòu)與算法_棧&隊(duì)列下一篇：JS數(shù)據(jù)結(jié)構(gòu)與算法_集合&字典 寫(xiě)在前面 說(shuō)明：JS數(shù)據(jù)結(jié)構(gòu)與算法 系列文章的代碼和示例均可在此找到 上一篇博客發(fā)布以后，僅幾天的時(shí)間竟然成為了我寫(xiě)博客以...

    NeverSayNever 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<