棧與隊(duì)列(一)

在這篇文章里渤刃,我們來(lái)實(shí)現(xiàn)自定義的鏈?zhǔn)綏3枘J紫任覀儊?lái)看看鏈?zhǔn)綏5慕Y(jié)構(gòu)及操作定義。

鏈?zhǔn)綏=Y(jié)構(gòu)定義

首先运怖,新建兩個(gè)文件拼弃,分別為 mystack.hmystack.cpp。在 mystack.h 中給出鏈?zhǔn)綏5慕Y(jié)構(gòu)定義及接口聲明摇展。

#ifndef _MYSTACK_H_
#define _MYSTACK_H_
#include <iostream>

using namespace std;

typedef char ELEMTYPE;
struct Node;

typedef struct Node *PNode;

struct Node {
    ELEMTYPE info;
    PNode link;
};

struct stStack {
    PNode top;
    size_t length;
};

typedef struct stStack *PLStack;

PLStack create();
bool destroy(PLStack *pstack);

bool print(PLStack pstack);
bool clear(PLStack pstack);

bool push(PLStack pstack, ELEMTYPE x);
bool pop(PLStack pstack);
bool top(PLStack pstack, ELEMTYPE *x);

bool isEmpty(PLStack pstack);
bool isFull(PLStack pstack);

#endif

從本次實(shí)驗(yàn)開始吻氧,我們使用 C++語(yǔ)言 的標(biāo)準(zhǔn)輸入輸出流進(jìn)行程序的輸入輸出操作。

要使用 C++語(yǔ)言的標(biāo)準(zhǔn)輸入輸出流咏连,我們需要在 mystack.h 頭文件中加入如下語(yǔ)句:

#include <iostream>

using namespace std;

C++語(yǔ)言中頭文件均不需要加 .h 作為后綴盯孙。iostream 頭文件對(duì)C++語(yǔ)言的 I/O 流進(jìn)行了定義及聲明。此外祟滴,C++語(yǔ)言還引入了 命名空間 的概念振惰,其本質(zhì)上就是定義一個(gè)新的作用域,在該作用域范圍內(nèi)再定義類踱启、變量及函數(shù)等报账,從而避免不同開發(fā)者因類、變量及函數(shù)命名同名而導(dǎo)致的沖突問(wèn)題埠偿。

因?yàn)镃++的標(biāo)準(zhǔn)輸入輸出流在 std 命名空間內(nèi)進(jìn)行定義透罢,因此我們需要加入using namespace std;這條語(yǔ)句,以便引入 std 這個(gè)命名空間冠蒋。

我們接下來(lái)解釋一下 mystack.h 頭文件中各數(shù)據(jù)結(jié)構(gòu)及函數(shù)聲明的含義羽圃。

首先,我們定義了兩個(gè)結(jié)構(gòu)體抖剿,分別是 struct Nodestruct stStack 朽寞。其中 Node 結(jié)構(gòu)用于表示鏈?zhǔn)綏V械墓?jié)點(diǎn),其包含數(shù)據(jù)域 info 以及指針域 link斩郎。而 stStack 結(jié)構(gòu)體表示鏈?zhǔn)綏?duì)象脑融,其包含指向鏈?zhǔn)綏m數(shù)?top 指針,以及表示鏈?zhǔn)綏0?jié)點(diǎn)元素個(gè)數(shù)的 length 變量缩宜。

其次肘迎,對(duì)于鏈?zhǔn)綏#覀兌x其所能進(jìn)行的操作如下:

  • 創(chuàng)建棧 : create
  • 銷毀棧 : destroy
  • 清空棧 : clear
  • 打印棧元素 : print
  • 元素入棧 : push
  • 元素出棧 : pop
  • 取棧頂元素 : top
  • 判斷棧是否為空 : isEmpty
  • 判斷棧是否為滿 : isFull

當(dāng)然對(duì)于鏈?zhǔn)綏6远突停袧M操作應(yīng)該返回 true妓布。我們?cè)诒疚闹薪o出該操作只是為了兼容性的目的。

鏈?zhǔn)綏=涌趯?shí)現(xiàn)

接下來(lái)我們依次來(lái)實(shí)現(xiàn)鏈?zhǔn)綏5母鱾€(gè)接口宋梧。首先實(shí)現(xiàn) create匣沼、 destroy 操作。

創(chuàng)建棧-create接口

創(chuàng)建棧接口原型如下所示:

PLStack create();

接口返回值為 PLStack 類型捂龄,該類型是 struct stStack 結(jié)構(gòu)體指針释涛,因此我們需要在接口中動(dòng)態(tài)分配該結(jié)構(gòu)體空間加叁,并初始化該結(jié)構(gòu)體。

由于 struct stStack結(jié)構(gòu)體包含兩個(gè)域:

  • top 為鏈?zhǔn)綏9?jié)點(diǎn)指針枢贿,指向鏈?zhǔn)綏m敼?jié)點(diǎn)殉农;
  • length 為鏈?zhǔn)綏9?jié)點(diǎn)元素計(jì)數(shù)器,用于記錄鏈?zhǔn)綏V挟?dāng)前節(jié)點(diǎn)元素個(gè)數(shù)局荚;

初始化時(shí)超凳,top 指針直接賦值為 NULL 即可,而由于初始化鏈?zhǔn)綏r(shí)耀态,棧內(nèi)無(wú)元素轮傍,因此 length 計(jì)數(shù)器直接置為 0 即可。以下是 create 接口的實(shí)現(xiàn):

PLStack create()
{
    PLStack pstack = (PLStack) malloc (sizeof(struct stStack));

    if (pstack != NULL)
    {
        pstack->top = NULL;
        pstack->length = 0;
        return pstack;
    }
    
    return NULL;
}

銷毀棧-destroy接口

接下來(lái)首装,我們來(lái)完成銷毀棧的操作创夜。因?yàn)槭擎準(zhǔn)綏#卦谌霔r(shí)均需要分配新的節(jié)點(diǎn)空間用于存儲(chǔ)棧元素仙逻。因此在銷毀棧時(shí)驰吓,需要將其中每個(gè)節(jié)點(diǎn)的空間都釋放掉。完成節(jié)點(diǎn)空間釋放操作后系奉,還需要將棧結(jié)構(gòu)體(struct stStack)分配的空間也一并釋放掉檬贰。

因此這兩步操作可以分解為:

  1. 釋放棧中所有節(jié)點(diǎn)(清空棧節(jié)點(diǎn));
  2. 釋放棧結(jié)構(gòu)體指針指向的內(nèi)存空間缺亮;

其中第一步操作可以利用我們后續(xù)將實(shí)現(xiàn)的 clear 操作來(lái)完成翁涤,而釋放棧結(jié)構(gòu)體指針這直接使用 free 函數(shù)即可。以下給出銷毀棧的接口實(shí)現(xiàn):

bool destroy(PLStack pstack)
{
    if (pstack == NULL)
    {
        return false;
    }
    
    clear(pstack);
    free(pstack);

    return true;
}

在銷毀棧時(shí)萌踱,我們首先判斷 pstack 指針是否為空葵礼,如果為空則不做任何操作。否則調(diào)用 clear 接口清空該棧并鸵,接著調(diào)用 free 函數(shù)釋放 pstack 指針指向的內(nèi)存空間鸳粉。

我們?cè)谥暗奈恼轮兄v過(guò),盡快使項(xiàng)目的原型運(yùn)行起來(lái)园担,不要試圖將所有代碼編寫完成后再進(jìn)行編譯届谈。目前我們實(shí)現(xiàn)了 createdestroy兩個(gè)接口,但由于在 destroy 接口中還調(diào)用了 clear 接口粉铐,因此我們先實(shí)現(xiàn) clear 接口后再進(jìn)行編譯工作疼约。

清空棧-clear接口

清空棧操作卤档,需要依次將元素從棧頂逐個(gè)彈出(元素出棧蝙泼,pop),直到棧為空為止(isEmpty)劝枣√捞ぃ可見织鲸,在 clear 接口中我們還需要調(diào)用popisEmpty接口溪胶。以下給出 clear 接口的實(shí)現(xiàn):

bool clear(PLStack pstack)
{
    if (pstack == NULL)
    {
        return false;
    }
    
    while (!isEmpty(pstack))
    {
        pop(pstack);
    }
    
    return true;
}

判斷棧是否為空-isEmpty接口

既然清空棧 clear 接口使用到了判斷棧是否為空操作搂擦,我們接著實(shí)現(xiàn) isEmptyisFull 兩個(gè)接口。

判斷棧是否為空哗脖,可以根據(jù)以下兩個(gè)情況:

  1. top 指針指向?yàn)榭眨?/li>
  2. length 計(jì)數(shù)器為 0瀑踢;

以上兩種情況均可用于判斷棧是否為空。以下給出 isEmpty 接口的實(shí)現(xiàn):

bool isEmpty(PLStack pstack)
{
    if (pstack == NULL)
    {
        return true;
    }

    return (pstack->length == 0);
}

判斷棧是否為滿-isFull接口

判斷棧是否未滿才避,只有在順序棧中才具有實(shí)際意義橱夭。鏈?zhǔn)綏R蚱涔?jié)點(diǎn)均是在元素入棧時(shí)進(jìn)行內(nèi)存空間動(dòng)態(tài)分配的。因此桑逝,此處給出的判滿接口僅僅為了兼容性的需求棘劣。

bool isFull(PLStack pstack)
{
    if (pstack == NULL)
    {
        return true;
    }
    
    return true;
}

元素出棧-pop接口

鏈?zhǔn)綏_M(jìn)行 pop 操作的示意圖如下:

元素出棧

首先判斷棧是否為空,若不為空則更新棧頂 top 指針楞遏,其次釋放原棧頂元素內(nèi)存空間(由 tmp 指針指向)茬暇,最后更新 length 計(jì)數(shù)器。

以下我們給出鏈?zhǔn)綏T爻鰲2僮鞯膶?shí)現(xiàn):

bool pop(PLStack pstack)
{
    PNode p;

    if (pstack == NULL)
    {
        return false;
    }
    
    if (!isEmpty(pstack))
    { 
        return false;
    }
    
    p = pstack->top;
    pstack->top = pstack->top->link;
    pstack->length = pstack->length - 1;
    free (p);
    
    return true;
}

元素入棧-push接口

鏈?zhǔn)綏_M(jìn)行 push 操作的示意圖如下:

元素入棧

首先嘗試分配新節(jié)點(diǎn)空間用于新入棧元素寡喝,其次更新 top 指針指向新棧頂元素糙俗,最后更新 length 計(jì)數(shù)器。

據(jù)此拘荡,我們給出鏈?zhǔn)綏?push 操作接口的實(shí)現(xiàn):

bool push(PLStack pstack, ELEMTYPE x)
{
    if (pstack == NULL)
    {
        return false;
    }
    
    PNode p = (PNode) malloc (sizeof(struct Node));
    if (p != NULL)
    {
        p->info = x;
        p->link = pstack->top;
        pstack->top = p;
        pstack->length = pstack->length + 1;
        return true;
    }

    return false;
}

注:push 接口中臼节,我們還應(yīng)該考慮判斷棧是否為滿的情況(該情況在順序棧中需要進(jìn)行考慮)。

取棧頂元素-top操作

獲取棧頂元素時(shí)珊皿,需要首先判斷棧是否為空网缝,只有棧不為空時(shí)才可獲取棧頂元素,否則應(yīng)返回操作失敗蟋定。以下是 top 操作的函數(shù)聲明:

bool top(PLStack pstack, ELEMTYPE *x);

需要引起我們注意的是粉臊,top 操作返回值為bool類型,也就是說(shuō)棧頂元素并不通過(guò)函數(shù)返回值獲取驶兜,而是通過(guò)參數(shù) ELEMTYPE 指針類型返回扼仲。這樣設(shè)計(jì)的原因很簡(jiǎn)單,因?yàn)楫?dāng)棧為空時(shí)抄淑,當(dāng)然無(wú)法取得棧頂屠凶,從而通過(guò) top 操作的返回值即可知道操作是否成功。

當(dāng) top 操作返回為true時(shí)肆资,可以直接通過(guò) ELEMTYPE *x獲取到棧頂元素矗愧;但當(dāng) top 操作返回為false時(shí),ELEMTYPE *x指針指向無(wú)意義的內(nèi)存空間郑原。

打印棧當(dāng)前元素-print接口

在完成了鏈?zhǔn)綏5乃泻诵牟僮骱蟀拢覀儊?lái)完成幫助函數(shù) print 接口的實(shí)現(xiàn)夜涕。 print 接口主要用于打印棧當(dāng)前的所有元素,以便我們對(duì)棧的狀態(tài)有所了解属愤。它可以在建棧后女器、元素入棧、元素出棧住诸、清空棧等操作前后進(jìn)行調(diào)用驾胆,以方便我們通過(guò)輸出結(jié)果觀察、判斷這些操作的業(yè)務(wù)邏輯是否正確贱呐。

如何實(shí)現(xiàn) print 接口以及該接口需要輸出什么信息俏拱,取決于你需要觀察的棧狀態(tài)信息。以鏈?zhǔn)綏槔鹁洌页诵枰喇?dāng)前棧中所有元素以及其在棧中的位置外锅必,我還希望知道每個(gè)棧元素的內(nèi)存地址。以下給出 print 接口的實(shí)現(xiàn):

bool print(PLStack pstack)
{
    PNode p;
    size_t i;
    char buffer[255];

    if (pstack == NULL)
    {
        return false;
    }
    
    p = pstack->top;
    i = length(pstack);

    #ifdef DEBUG
    cout << "---------  STACK   ----------" << endl;
    sprintf(buffer, "-------  %ld ELEMENTS ---------", i);
    cout << buffer << endl;
    #endif
    
    while (p != NULL)
    {
        sprintf(buffer, "%ld [%p] : %c", i, p, p->info);
        cout << buffer << endl;
        i--;
        p = p->link;
    }

    #ifdef DEBUG
    cout << endl;
    #endif
    
    return true;
}

print 接口中惕艳,我們通過(guò)一個(gè) while 循環(huán)依次遍歷從棧頂?shù)綏5椎乃性馗阋⒚總€(gè)棧元素在棧中的 節(jié)點(diǎn)序號(hào)節(jié)點(diǎn)結(jié)構(gòu)體內(nèi)存地址远搪、 節(jié)點(diǎn)數(shù)據(jù)域均打印輸出劣纲。

此外,在 print 接口中通過(guò)條件編譯語(yǔ)句#ifdef谁鳍、#endif語(yǔ)句用于在調(diào)試模式下額外輸出更多信息癞季。

測(cè)試鏈?zhǔn)綏8鞑僮鹘涌?/h2>

在講解 createdestroy 兩個(gè)操作接口的過(guò)程中倘潜,我們將鏈?zhǔn)綏5氖S嗖僮鹘涌诘膶?shí)現(xiàn)思路及過(guò)程都做了詳細(xì)的講解绷柒。

與我們之前所說(shuō)的 盡可能早的讓程序跑起來(lái) 不同的事,這次實(shí)驗(yàn)過(guò)程中涮因,我們依據(jù)每個(gè)接口的實(shí)現(xiàn)及嵌套調(diào)用關(guān)系依次實(shí)現(xiàn)了所有的接口废睦。不過(guò)這并不影響我們后續(xù)的測(cè)試工作。

以下我們給出測(cè)試主文件 main.cpp的代碼:

#include <iostream>
#include "mystack.h"

using namespace std;

int main ()
{
    PLStack pstack;
    ELEMTYPE x;

    pstack = create();

    push(pstack, 'a');
    push(pstack, 'b');
    push(pstack, 'c');

    print(pstack);

    while (!isEmpty(pstack))
    {
        top(pstack, &x);
        cout << "stack top element: " << x << endl;
        pop(pstack);
    }

    print(pstack);
    destroy(pstack);

    return 0;
}

main.cpp 中养泡,我們對(duì)鏈?zhǔn)綏5慕^大多數(shù)接口進(jìn)行了測(cè)試嗜湃,且 clear 接口在 destroy 接口中被調(diào)用。我們來(lái)看看編譯后的運(yùn)行結(jié)果:

[localhost@lab02:stack xgqin]$ ls
a.out       main.cpp    mystack.cpp mystack.h
[localhost@lab02:stack xgqin]$ vim mystack.cpp 
[localhost@lab02:stack xgqin]$ g++ -DDEBUG main.cpp mystack.cpp 
[localhost@lab02:stack xgqin]$ ./a.out 
---------  STACK   ----------
-------  3 ELEMENTS ---------
3 [0x7fc6ded00030] : c
2 [0x7fc6ded00020] : b
1 [0x7fc6ded00010] : a

stack top element: c
stack top element: b
stack top element: a
---------  STACK   ----------
-------  0 ELEMENTS ---------

從運(yùn)行結(jié)果結(jié)合 main.cpp 文件源碼來(lái)看澜掩,鏈?zhǔn)綏5母鞑僮鹘涌诰9号@并不能說(shuō)明我們編寫的代碼沒有問(wèn)題,你可以嘗試編寫幾個(gè)額外的測(cè)試用例對(duì)接口進(jìn)行測(cè)試肩榕。

總結(jié)

在本文中刚陡,我們首先給出了鏈?zhǔn)綏=Y(jié)構(gòu)的定義,并給出了需要實(shí)現(xiàn)的接口聲明形式;其次橘荠,在各個(gè)不同接口中,我們通過(guò)嵌套調(diào)用等形式復(fù)用了不少接口郎逃,這需要大家對(duì)棧的邏輯結(jié)構(gòu)保持清晰的概念哥童;最后,我們通過(guò)一段測(cè)試代碼褒翰,對(duì)所編寫的程序進(jìn)行了測(cè)試贮懈。

最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末,一起剝皮案震驚了整個(gè)濱河市优训,隨后出現(xiàn)的幾起案子朵你,更是在濱河造成了極大的恐慌,老刑警劉巖揣非,帶你破解...
    沈念sama閱讀 222,681評(píng)論 6 517
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件抡医,死亡現(xiàn)場(chǎng)離奇詭異,居然都是意外死亡早敬,警方通過(guò)查閱死者的電腦和手機(jī)忌傻,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,205評(píng)論 3 399
  • 文/潘曉璐 我一進(jìn)店門,熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)搞监,“玉大人水孩,你說(shuō)我怎么就攤上這事∷雎浚” “怎么了俘种?”我有些...
    開封第一講書人閱讀 169,421評(píng)論 0 362
  • 文/不壞的土叔 我叫張陵,是天一觀的道長(zhǎng)绝淡。 經(jīng)常有香客問(wèn)我宙刘,道長(zhǎng),這世上最難降的妖魔是什么牢酵? 我笑而不...
    開封第一講書人閱讀 60,114評(píng)論 1 300
  • 正文 為了忘掉前任荐类,我火速辦了婚禮,結(jié)果婚禮上茁帽,老公的妹妹穿的比我還像新娘玉罐。我一直安慰自己,他們只是感情好潘拨,可當(dāng)我...
    茶點(diǎn)故事閱讀 69,116評(píng)論 6 398
  • 文/花漫 我一把揭開白布吊输。 她就那樣靜靜地躺著,像睡著了一般铁追。 火紅的嫁衣襯著肌膚如雪季蚂。 梳的紋絲不亂的頭發(fā)上,一...
    開封第一講書人閱讀 52,713評(píng)論 1 312
  • 那天,我揣著相機(jī)與錄音扭屁,去河邊找鬼算谈。 笑死,一個(gè)胖子當(dāng)著我的面吹牛料滥,可吹牛的內(nèi)容都是我干的然眼。 我是一名探鬼主播,決...
    沈念sama閱讀 41,170評(píng)論 3 422
  • 文/蒼蘭香墨 我猛地睜開眼葵腹,長(zhǎng)吁一口氣:“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼高每!你這毒婦竟也來(lái)了?” 一聲冷哼從身側(cè)響起践宴,我...
    開封第一講書人閱讀 40,116評(píng)論 0 277
  • 序言:老撾萬(wàn)榮一對(duì)情侶失蹤鲸匿,失蹤者是張志新(化名)和其女友劉穎,沒想到半個(gè)月后阻肩,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體带欢,經(jīng)...
    沈念sama閱讀 46,651評(píng)論 1 320
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡,尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 38,714評(píng)論 3 342
  • 正文 我和宋清朗相戀三年烤惊,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了洪囤。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點(diǎn)故事閱讀 40,865評(píng)論 1 353
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡撕氧,死狀恐怖瘤缩,靈堂內(nèi)的尸體忽然破棺而出,到底是詐尸還是另有隱情伦泥,我是刑警寧澤剥啤,帶...
    沈念sama閱讀 36,527評(píng)論 5 351
  • 正文 年R本政府宣布,位于F島的核電站不脯,受9級(jí)特大地震影響府怯,放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜防楷,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 42,211評(píng)論 3 336
  • 文/蒙蒙 一牺丙、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧复局,春花似錦冲簿、人聲如沸。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,699評(píng)論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽(yáng)。三九已至角钩,卻和暖如春吝沫,著一層夾襖步出監(jiān)牢的瞬間呻澜,已是汗流浹背。 一陣腳步聲響...
    開封第一講書人閱讀 33,814評(píng)論 1 274
  • 我被黑心中介騙來(lái)泰國(guó)打工惨险, 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留羹幸,地道東北人。 一個(gè)月前我還...
    沈念sama閱讀 49,299評(píng)論 3 379
  • 正文 我出身青樓辫愉,卻偏偏與公主長(zhǎng)得像栅受,于是被迫代替她去往敵國(guó)和親。 傳聞我的和親對(duì)象是個(gè)殘疾皇子一屋,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,870評(píng)論 2 361

推薦閱讀更多精彩內(nèi)容