數據結構之棧和隊列（C語言版）

    數據結構學習繼續向前推進，之前對線性表進行了學習，現在我們進入棧和隊列的學習。同樣我們先學習一些基本概念以及堆棧的ADT.

棧和隊列是兩種中重要的線性結構。從數據結構角度看，棧和隊列也是線性表，只不過是受限的線性表。因此可以稱為限定性數據結構。但從數據類型來看，他們是和線性表大不相同的兩類重要的抽象數據類型。

棧：（stack）是限定僅在表尾進行相應插入和刪除操作的線性表。因此，對棧來說，表尾有其特殊含義，稱為棧頂，表頭稱為棧底，不含元素的空表稱為空棧。棧一個重要特性就是后進先出.OK,我們來看一下棧的結構：

ADT Stack

{

數據對象：D = {ai| ai屬于ElemSet，i = 1，2，……，n， n >= 0 }

約定an端為棧頂，a1端為棧底。

基本操作：

                Status Init_SeqStack(SeqStack *s)

                    初始化棧，構造一個空棧。

                Status Destory(SeqStack *s)

                    摧毀棧

                Status Clear(SeqStack *s)

                    清空棧                 

                int IsEmpty(SeqStack *s)

                判斷是否為空棧，是空棧返回1，不是空棧返回0

               int IsFull(SeqStack *s )

                判斷棧是否滿，棧滿返回1，沒有滿返回0

                int  GetLength(SeqStack s)

                返回棧中元素的個數

                Status PushStack(SeqStack *s,ElemType x)

                插入元素e為新的棧頂元素

                Status GetTop(SeqStack *s,ElemType *value)

                獲取棧頂元素，用value帶回

                Status  PopStack(SeqStack *s)

                刪除棧頂元素              

                Status Show_Stack(SeqStack s)

                打印輸出棧中元素

}

    以上就是棧的抽象數據類型，好了我們接下來用C語言實現棧結構，既然棧受限的線性表，線性表有鏈式存儲結構和順序存儲結構，那么棧也同樣有兩種，順序棧和鏈棧。依然沿襲過去先弄清結構再通過代碼解釋。開篇已經講了棧是受限的線性表，那么我們就要類比著看棧的操作：順序棧，就類比順序表。鏈棧就類比單鏈表。ok，我們先來看順序棧：

順序棧

    順序棧，即就是棧的順序存儲結構，是利用一組連續的存儲單元一次依次存放自棧底到棧頂的數據元素，同時附設top指示棧頂元素在順序表中的位置，通常的習慣做法以top=0表示空棧，鑒于以C語言作為描述語言時，如此設定會帶來很大不便；另一方面，由于棧在使用過程中所需的最大空間大小無法估計。因此一般來說，先為初始化空棧時不應設定棧的最大空間容量。一個較合理的做法是：先為棧分配一個基本容量，然后在應用過程中，當棧的空間不夠時再逐段擴大。為此，可以設定兩個常 STACK_INIT_SIZE(存儲空間初始分配量)和STACK_INC_SIZE(存儲空間分配增量)

 ok我們先定義順序棧的結構：

#define ElemType char

#define Status    int 

#define FALSE     0

#define TRUE      1

#define STACK_INIT_SIZE  8               存儲空間初始分配量

#define STACK_INC_SIZE   20              存儲空間分配增量

typedef struct  SeqStack

{

ElemType *bace;

int capacity;

int top;

}SeqStack;

//判斷是否為空棧，棧結構中的top也就記錄了順序棧中的狀態，棧空返回1，非空返回0

int  IsEmpty(SeqStack *s)

{

return s->top == 0;

}

//判斷是否棧滿，棧滿返回1，非滿返回0

int  IsFull(SeqStack *s )

{

return s->top >= s->capacity; 

}

//此函數解決，上面提到的，當基空間不夠時，增加空間。增加成功放回TRUE,也就是1，增加失敗返回FALSE

Status IncSize(SeqStack *s)

{

ElemType *newbase = (ElemType *)realloc(s->bace,sizeof(ElemType) * (s->capacity + STACK_INC_SIZE));

if(NULL == newbase)

{

printf("out of memory\n");

return FALSE;

}

s->bace = newbase;

s->capacity += STACK_INC_SIZE;

return TRUE;

}

順序棧的初始化

//初始化棧，就是為棧分配一個基空間，修改結構中top讓其等于0，表示空棧。

//初始化成功返回TRUE，初始化失敗返回FALSE;

Status Init_SeqStack(SeqStack *s)

{

s->bace = (ElemType *)malloc(sizeof(ElemType) * STACK_INIT_SIZE);

if(NULL == s->bace )

{

printf("out of memory,filed Init_SeqStack\n");

return FALSE;

}

s->top = 0;

s->capacity = STACK_INIT_SIZE;

return TRUE;

}

   順序棧的壓棧出棧

    這里一直強調棧是受限的線性表，那么，初始化，等其他的基本類同，主要區別就是在棧中的壓棧和出棧，壓棧出棧，對順序棧就是對順序表的尾插、尾刪，ok我們繼續用圖理一下結構。

//入棧（壓棧）成功返回TRUE,失敗返回FALSE

Status PushStack(SeqStack *s,ElemType x)

{

 /*

    這里就是解決棧的基空間不夠會滿的情況，需要調用前邊定義的函數再次為其增加空間。這里的 

    if條件需要注意，IsFull(s) 函數，當棧已滿是返回1結果為真，IncSize(s)函數返回值，當開辟

    成功后返回1結果為真，所以當開辟成功后取反就為價所以&&操作后為假，if模塊就不執

    行了，就繼續執行后邊的代碼模塊

*/

if(IsFull(s) && !IncSize(s))            

{

printf("棧空間已滿,%d不能入棧\n",x);

return FALSE;

}

s->bace[s->top++] = x;

//s->top++;                         簡化代碼

return TRUE;

}

//出棧

Status  PopStack(SeqStack *s)

{

if(IsEmpty(s))

{

printf("棧已空,不能出棧\n");

return FALSE;

}

s->top--;

return TRUE;

}

    順序棧的獲取棧頂元素

    繼續看上一張圖，中的那段話，在C語言中，由于數組下標是從0開始的，top中保存棧中元素個數，所以base[top]是指向棧頂元素的上一個空間，所以獲取棧頂元素時就需要減去1.

//獲取棧頂元素，

Status GetTop(SeqStack *s,ElemType *value)

{

if(IsEmpty(s))

{

printf("棧空間已空,不能取棧頂元素\n");

return FALSE;

}

*value = s->bace[s->top - 1];

return TRUE;

}

   順序棧的的長度

     top中保存的就是棧中的元素個數，所以獲取棧中元素個數直接返回top的值就可以。

//獲取棧長度

int  GetLength(SeqStack s)

{

return s.top;

}

順序棧的清空棧

//清空棧，清空棧就是讓棧為空，所以只需要把top修改為0即可。

Status Clear(SeqStack *s)

{

s->top = 0;

return TRUE;

}

順序棧的摧毀棧

//摧毀棧，摧毀棧，意味著，不僅要top修改為0，更要釋放掉棧的空間。

Status Destory(SeqStack *s)

{

        free(s->bace);

s->bace = NULL;

s->top = 0;

return TRUE;

}

順序棧的輸出

//輸出棧中的元素，既然棧是從棧頂出，那么全部打印的輸出的時候，就需要從數組的尾輸出。

Status Show_Stack(SeqStack s)

{

if(s.top == 0)

{

printf("棧已空\n");

return FALSE;

}

for(int i = s.top-1; i >= 0; i--)

{

printf("%d",s.bace[i]);

}

printf("\n");

return TRUE;

}

順序棧的操作的基本操作就總結到這里，我們接著看棧的另一種存儲結構——鏈棧。

棧之鏈棧

    鏈棧也是棧,所以就不在介紹它的ADT，我們直接看鏈棧的結構。順序棧我們類比順序表，那么鏈棧我們類比鏈表，鏈表的種類那么多，我們選用那種呢？看棧的定義，我們不難得出是單鏈表，至于是帶頭結點還是不帶頭結點，由于棧操作是從棧頂操作也就是線性表的表尾，所以這里也不用考慮帶頭結點或者不帶頭結點，都一樣，也就不需要用帶頭結點了。

之前說順序棧的時候我們談到，棧會滿，我們采用了一種結構處理這種情況，為其增開辟空間，解決棧滿的情況。那么對于鏈棧，只要內存不滿，就可以一直壓棧存儲元素。（系統內存耗盡除外，當發生這種情況時，系統已經癱瘓，所以程序的崩潰也已經無所謂了。），所以也不需要順序棧中判斷棧是否為滿的情況這個函數。

ok我們繼續先看一下鏈棧的結構和結構定義：

棧的結構

#define ElemType int

#define TRUE     1

#define FALSE    0

#define Status   int

typedef struct StackNode

{

    ElemType data;

    struct StackNode *next;

}StackNode;

typedef StackNode* LinkStack;    // 這里需要注意后邊LinkStack  定義的變量就是指針類型的。

Status InitLinkStack(LinkStack *ls)

{

    *ls = NULL;

    return TRUE;

}

  鏈棧的壓棧出棧

  順序棧時已經說過，壓棧出棧對于棧是最重要的結構，那么其他操作類比一下不帶頭結點單鏈表的操作，OK,壓棧就是對不帶頭結點的頭插，頭插！對就是頭插，不再是順序表中說的尾插，沒有搞錯，我們退回去看鏈棧的結構圖，當插入元素時，指向棧頂的指針指向新的元素，那么當通過指向棧頂的指針訪問鏈表的時候，不就是后進先出，不就是符合棧的定義嗎？其實順序表也一定意義上頭插，我們通過棧頂看，不就是頭插嗎？說順序棧是尾插，是由于順序棧是通過數組實現的，數組名是指向數組的第一個元素的，我們要通過數組名操作存儲數據，所以才說是尾插。我們繼續看結構圖:

   結構弄清了鏈棧的壓棧只是一個沒有不帶頭結點的頭插；ok我們看具體C語言代碼實現：

壓棧

//壓棧，壓棧成功返回TRUE,失敗返回FALSE; 

Status PushStack(LinkStack *ls,ElemType x)

{

StackNode  *s = (StackNode *)malloc(sizeof(StackNode));

if(NULL == s)

{

printf("out of memory\n");

return FALSE;

}

s->data = x; 

if(NULL == *ls)

{

*ls = s;

s->next = NULL;

}

else

{

s->next = *ls;

*ls = s;

}

return TRUE;

}

出棧

    對于鏈棧的出棧要注意釋放結點空間，防止內存泄露

//出棧,出棧成功返回TRUE，失敗返回FALSE

Status PopLinkStack(LinkStack *ls)

{

StackNode *p = *ls;

if(NULL == p)

{

printf("棧已空,出棧失敗\n");

return FALSE;

}

*ls = p->next;

free(p);

p = NULL;

return TRUE;

}   

鏈棧的清空

    這里由于不帶頭結點，所以這里只給出了清空鏈棧的操作，但是，需要強調意義不一樣。

//清空鏈表，清空成功返回TRUE,失敗返回FALSE

Status ClearLinkStack(LinkStack *ls)

{

StackNode *p = *ls;

while(NULL != p)

{

*ls = p->next;

free(p);

p = *ls;

}

*ls = NULL;

return TRUE;

}

鏈棧的獲取棧頂元素

//獲取棧頂元素，即就是棧不空的條件下，獲取棧的首元素。

Status GetTop(LinkStack *ls,ElemType *value)

{

StackNode *p = *ls;

if(NULL == p)

{

printf("棧已空,獲取棧頂元素失敗\n");

return FALSE;

}

*value = p->data;

return TRUE;

}

鏈棧的獲取棧的長度

    鏈棧不像順序棧，通過top可以直接獲得棧中元素個數，需要遍歷所以元素統計棧的元素個數。

//獲取鏈表長度

int  GetLength(LinkStack *ls)

{

StackNode *p = *ls;

int length = 0;

while(NULL != p)

{

length++;

p = p->next;

}

return p;

}

鏈棧的輸出

Status  Show_LinkStack(LinkStack *s)

{

StackNode *p = *s; 

if(NULL == s)

{

printf("棧已空\n");

return FALSE;

}

while(NULL != p->next)

{

printf("%d  ",p->data);

p = p->next;

}

printf("\n");

}

    ok棧的基本操作就總結到這里，寫道這里線性表，棧的基本操作我們都講完了，會有人說，堆，線性表就只能進行這些基本操作嗎？那豈不是很沒有用，下一篇我將對線性表的應用簡單總結一下。