柚子快報(bào)邀請(qǐng)碼778899分享：學(xué)習(xí) c語言 數(shù)據(jù)結(jié)構(gòu)之《?！?/p>

http://yzkb.51969.com/

在之前我們已經(jīng)學(xué)習(xí)了數(shù)據(jù)結(jié)構(gòu)中線性表里面的順序表與鏈表，了解了如何實(shí)現(xiàn)順序表與鏈表增、刪、查、該等功能。其實(shí)在線性表中除了順序表和鏈表還有其他的類別，在本篇中我們就將學(xué)習(xí)另外一種線性表——棧，在通過本篇的學(xué)習(xí)后，你將會(huì)對(duì)棧的結(jié)構(gòu)有充足的了解，在了解完結(jié)構(gòu)后我們還將進(jìn)行棧的實(shí)現(xiàn)。一起加油吧?。?！

1.棧的概念與結(jié)構(gòu)

棧：一種特殊的線性表，其只允許在固定的一端進(jìn)行插入和刪除元素操作。進(jìn)行數(shù)據(jù)插入和刪除操作的?端稱為棧頂，另一端稱為棧底。棧中的數(shù)據(jù)元素遵守后進(jìn)先出（先進(jìn)后出）LIFO（Last In First Out的原則。

壓棧：棧的插入操作叫做進(jìn)棧/壓棧/入棧，入數(shù)據(jù)在棧頂。 出棧：棧的刪除操作叫做出棧。出數(shù)據(jù)也在棧頂。

那么棧的底層結(jié)構(gòu)是基于什么的呢？其實(shí)基于數(shù)組還是基于單鏈表或者是雙鏈表都是可以的，那么哪一種是最優(yōu)解呢？接下來我們就來分析基于不同底層結(jié)構(gòu)的利與弊

若底層結(jié)構(gòu)基于數(shù)組，則可以讓數(shù)組的低地址處表示棧底，數(shù)組的高地址處表示棧頂，使用一個(gè)size變量來表示數(shù)組有效數(shù)據(jù)個(gè)數(shù)，這樣就可以要入棧時(shí)直接在size位置插入數(shù)據(jù)，之后size加一；出棧時(shí)就可以直接讓size減一，這樣就可以讓數(shù)組的有效個(gè)數(shù)減一。以上使用數(shù)組來作為棧的底層結(jié)構(gòu)時(shí)間復(fù)雜度為O(1)

在數(shù)組當(dāng)中雖然每次在空間不足時(shí)都會(huì)以之前二倍的方式申請(qǐng)新空間，這時(shí)可能會(huì)存在內(nèi)存的浪費(fèi)，當(dāng)時(shí)由于數(shù)組在內(nèi)存中是連續(xù)存放的，這就使得在入棧和出棧不需要再每次都申請(qǐng)空間，而且數(shù)組在取數(shù)據(jù)的時(shí)候可能緩存中就有不一定要在主存中取。

若棧的底層結(jié)構(gòu)為單鏈表，如果是在單鏈表尾部表示棧頂，頭部表示棧底這樣在無論是在入棧還是在出棧時(shí)因?yàn)槎夹枰ㄟ^遍歷來找到單鏈表的尾節(jié)點(diǎn)，所以時(shí)間復(fù)雜度都為O(N)。所以這時(shí)就要改變棧頂為單鏈表的頭部，棧底為單鏈表的尾部，這時(shí)在入棧和出棧時(shí)就不需要遍歷單鏈表，時(shí)間復(fù)雜度就都為O(1)。

但是單鏈表每次在入棧和出棧時(shí)都要申請(qǐng)節(jié)點(diǎn)和銷毀節(jié)點(diǎn)，并且由于單鏈表每個(gè)節(jié)點(diǎn)空間在內(nèi)存當(dāng)中不一定是連續(xù)的，所以每次訪問數(shù)據(jù)都需要區(qū)主存取。

而在雙鏈表中無論是讓頭部作為棧頂，尾部作為棧底還是讓尾部作為棧頂，頭部作為棧底，由于雙鏈表每個(gè)節(jié)點(diǎn)內(nèi)部都有指向前一個(gè)節(jié)點(diǎn)和下一個(gè)節(jié)點(diǎn)的指針，所以在入棧和出棧時(shí)都不需要遍歷鏈表，所以入棧和出棧時(shí)的時(shí)間復(fù)雜度都為O(1)。

但是雙鏈表在每個(gè)節(jié)點(diǎn)內(nèi)部相比單鏈表都多一個(gè)指針變量，在32位環(huán)境下每個(gè)節(jié)點(diǎn)大小就會(huì)多4個(gè)字節(jié)；在64位環(huán)境下每個(gè)節(jié)點(diǎn)大小就會(huì)多8字節(jié)。因此使用雙鏈表就會(huì)造成更多的內(nèi)存損耗。

通過以上的分析可以發(fā)現(xiàn)無論棧的底層結(jié)構(gòu)是基于數(shù)組還是單鏈表還是雙鏈表在入棧和出棧時(shí)的時(shí)間復(fù)雜度都為O(1)，但是綜合其他因素使用數(shù)組是最優(yōu)解?

?

2.棧的實(shí)現(xiàn)

在實(shí)現(xiàn)棧的代碼內(nèi)在Stack.h頭文件內(nèi)定義棧的結(jié)構(gòu)以及對(duì)各種功能函數(shù)進(jìn)行聲明，在Stack.c文件內(nèi)實(shí)現(xiàn)各個(gè)函數(shù)，在test.c文件內(nèi)對(duì)實(shí)現(xiàn)的各函數(shù)進(jìn)行測(cè)試

2.1棧結(jié)構(gòu)的定義

在Stack.h中創(chuàng)建一個(gè)結(jié)構(gòu)體來定義棧的結(jié)構(gòu)，在該結(jié)構(gòu)體中的成員變量和順序表中基本是相同的，只不過將順序表中表示有效元素個(gè)數(shù)的size改名位top，讓top來表示棧頂

//定義棧的結(jié)構(gòu)

typedef int STDataType;

typedef struct stack

{

STDataType* a;

int capacity;//棧空間大小

int top;//棧頂

}stack;

2.2棧的初始化

要完成棧的初始化函數(shù)首先要在Stack.h完成初始化函數(shù)的聲明

//初始化棧

void stackInit(stack* ps);

將該函數(shù)命名為stackInit,函數(shù)的參數(shù)就為指向結(jié)構(gòu)體的指針

接下來就是在stack.c內(nèi)完成初始化函數(shù)的實(shí)現(xiàn) 由于ps指針是指向結(jié)構(gòu)體的指針，所以該指針不能為空，所以要對(duì)ps進(jìn)行assert斷言

//初始化棧

void stackInit(stack* ps)

{

assert(ps);

ps->a = NULL;

ps->top = ps->capacity = 0;

}

2.3檢測(cè)棧是否為空

要完成檢測(cè)棧是否為空函數(shù)首先要在Stack.h完成該函數(shù)函數(shù)的聲明

//檢測(cè)棧是否為空

bool stackEmpty(stack* ps);

將該函數(shù)命名為stackEmpty,函數(shù)的參數(shù)就為指向結(jié)構(gòu)體的指針，函數(shù)的返回類型為布爾類型

接下來就是在stack.c內(nèi)完成檢測(cè)棧是否為空函數(shù)的實(shí)現(xiàn) 由于ps指針是指向結(jié)構(gòu)體的指針，所以該指針不能為空，所以要對(duì)ps進(jìn)行assert斷言 在該函數(shù)中若數(shù)組內(nèi)的有效個(gè)數(shù)top為0函數(shù)就會(huì)返回true，不為0就返回false

//檢測(cè)棧是否為空

bool stackEmpty(stack* ps)

{

assert(ps);

return ps->top==0;

}

2.4入棧

要完成入棧函數(shù)首先要在Stack.h完成初始化函數(shù)的聲明

void stackPush(stack* ps,STDataType x);

將該函數(shù)命名為stackPush,函數(shù)的參數(shù)有兩個(gè)，第一個(gè)為指向結(jié)構(gòu)體的指針，第二個(gè)為要進(jìn)入棧的數(shù)據(jù)

接下來就是在stack.c內(nèi)完成入棧函數(shù)的實(shí)現(xiàn) 由于在入棧時(shí)數(shù)組的空間可以已經(jīng)滿了，因此在進(jìn)行插入數(shù)據(jù)之前要判斷數(shù)組的有效個(gè)數(shù)是否與數(shù)組的空間大小相同，如果相同就需要進(jìn)行增容。增容的代碼就和之前的順序表檢測(cè)數(shù)組空間大小函數(shù)一樣。 在調(diào)整完空間大小之后的入棧就和順序表中得尾插一樣，ps->a[ps->top++] = x一句代碼就可以實(shí)現(xiàn)

//入棧

void stackPush(stack* ps,STDataType x)

{

assert(ps);

if (ps->top == ps->capacity)

{

int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;

STDataType* tmp = (STDataType*)realloc(ps->a, newcapacity * sizeof(STDataType));

if (tmp == NULL)

{

perror("realloc fail!");

exit(1);

}

ps->a=tmp;

ps->capacity = newcapacity;

}

ps->a[ps->top++] = x;

}

2.5出棧?

要完成出棧函數(shù)首先要在Stack.h完成出棧函數(shù)的聲明

//出棧

void stackPop(stack* ps);

將該函數(shù)命名為stackPop,函數(shù)的參數(shù)為指向結(jié)構(gòu)體的指針

接下來就是在stack.c內(nèi)完成出棧函數(shù)的實(shí)現(xiàn) 由于ps指針是指向結(jié)構(gòu)體的指針，所以該指針不能為空，所以要對(duì)ps進(jìn)行assert斷言 同時(shí)在出棧時(shí)棧不能為空，所以要對(duì)satckEmpt(ps)進(jìn)行assert斷言在出棧就和順序表中得尾刪一樣將top減一就可

//出棧

void stackPop(stack* ps)

{

assert(ps);

assert(!stackEmpty(ps));

--ps->top;

}

2.6取棧頂元素

要完成取棧頂元素函數(shù)首先要在Stack.h完成取棧頂元素函數(shù)的聲明

//獲取棧頂元素

STDataType stackTop(stack* ps);

將該函數(shù)命名為stackTop,函數(shù)的參數(shù)為指向結(jié)構(gòu)體的指針，函數(shù)的返回值就為棧頂?shù)脑?/p>

接下來就是在stack.c內(nèi)完成取棧頂原始函數(shù)的實(shí)現(xiàn) 由于ps指針是指向結(jié)構(gòu)體的指針，所以該指針不能為空，所以要對(duì)ps進(jìn)行assert斷言 同時(shí)在出棧時(shí)棧不能為空，所以要對(duì)satckEmpt(ps)進(jìn)行assert斷言 由于top指向數(shù)組的尾元素的后一位，所以只要將size-1就可以得到棧頂元素

//獲取棧頂元素

STDataType stackTop(stack* ps)

{

assert(ps);

assert(!stackEmpty(ps));

return ps->a[ps->top - 1];

}

2.7獲取棧中有效元素個(gè)數(shù)

要完成獲取棧中有效元素個(gè)數(shù)函數(shù)首先要在Stack.h完成獲取棧中有效元素個(gè)數(shù)函數(shù)的聲明

//獲取棧中有效元素個(gè)數(shù)

int stackSize(stack* ps);

將該函數(shù)命名為stackSize,函數(shù)的參數(shù)為指向結(jié)構(gòu)體的指針，函數(shù)的返回值就為棧的元素個(gè)數(shù)

接下來就是在stack.c內(nèi)完成獲取棧中有效元素個(gè)數(shù)函數(shù)的實(shí)現(xiàn) 由于ps指針是指向結(jié)構(gòu)體的指針，所以該指針不能為空，所以要對(duì)ps進(jìn)行assert斷言 因?yàn)樵诮Y(jié)構(gòu)體中的top就為數(shù)組的有效元素個(gè)數(shù)，所以在該函數(shù)中返回ps->top即可

//獲取棧中有效元素個(gè)數(shù)

int stackSize(stack* ps)

{

assert(ps);

return ps->top;

}

2.8銷毀棧

要完成銷毀棧函數(shù)首先要在Stack.h完成銷毀棧函數(shù)的聲明

//銷毀棧

void stackDestory(stack* ps);

將該函數(shù)命名為stackDestory,函數(shù)的參數(shù)為指向結(jié)構(gòu)體的指針

接下來就是在stack.c內(nèi)完成銷毀棧函數(shù)的實(shí)現(xiàn) 由于ps指針是指向結(jié)構(gòu)體的指針，所以該指針不能為空，所以要對(duì)ps進(jìn)行assert斷言 在銷毀時(shí)，由于棧的空間是由realloc申請(qǐng)來的，所以在使用完后要用free來釋放內(nèi)存空間，并且在釋放后將指針ps->a置為NULL，且將top和capacity都賦值為0

//銷毀棧

void stackDestory(stack* ps)

{

assert(ps);

if (ps->a)

{

free(ps->a);

}

ps->a = NULL;

ps->top = ps->capacity = 0;

}

2.9棧的打印

因?yàn)樵跅：晚樞虮硪约版湵聿煌?，由于棧只能在一端進(jìn)和出所以棧是不能遍歷，所以我們不能通過創(chuàng)建一個(gè)函數(shù)來遍歷棧

所以要打印棧就只能在test.c內(nèi)調(diào)用相關(guān)函數(shù)來實(shí)現(xiàn)例如以下棧先依次入棧1，2，3，4，之后要打印就通過以下循環(huán)來實(shí)現(xiàn)

#include"stack.h"

void test()

{

stack ps;

stackInit(&ps);

stackPush(&ps, 1);

stackPush(&ps, 2);

stackPush(&ps, 3);

stackPush(&ps, 4);

while (!stackEmpty(&ps))

{

STDataType p = stackTop(&ps);

printf("%d ", p);

stackPop(&ps);

}

stackDestory(&ps);

}

int main()

{

test();

return 0;

}

3.棧的實(shí)現(xiàn)完整代碼?

stack.h

#define _CRT_SECURE_NO_WARNINGS 1

#include

#include

#include

#include

//定義棧的結(jié)構(gòu)

typedef int STDataType;

typedef struct stack

{

STDataType* a;

int capacity;//?？臻g大小

int top;//棧頂

}stack;

//初始化棧

void stackInit(stack* ps);

//銷毀棧

void stackDestory(stack* ps);

//檢測(cè)棧是否為空

bool stackEmpty(stack* ps);

//入棧

void stackPush(stack* ps,STDataType x);

//出棧

void stackPop(stack* ps);

//獲取棧頂元素

STDataType stackTop(stack* ps);

//獲取棧中有效元素個(gè)數(shù)

int stackSize(stack* ps);

stack.c

#include"stack.h"

//初始化棧

void stackInit(stack* ps)

{

assert(ps);

ps->a = NULL;

ps->top = ps->capacity = 0;

}

//銷毀棧

void stackDestory(stack* ps)

{

assert(ps);

if (ps->a)

{

free(ps->a);

}

ps->a = NULL;

ps->top = ps->capacity = 0;

}

//檢測(cè)棧是否為空

bool stackEmpty(stack* ps)

{

assert(ps);

return ps->top==0;

}

//入棧

void stackPush(stack* ps,STDataType x)

{

assert(ps);

if (ps->top == ps->capacity)

{

int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;

STDataType* tmp = (STDataType*)realloc(ps->a, newcapacity * sizeof(STDataType));

if (tmp == NULL)

{

perror("realloc fail!");

exit(1);

}

ps->a=tmp;

ps->capacity = newcapacity;

}

ps->a[ps->top++] = x;

}

//出棧

void stackPop(stack* ps)

{

assert(ps);

assert(!stackEmpty(ps));

--ps->top;

}

//獲取棧頂元素

STDataType stackTop(stack* ps)

{

assert(ps);

assert(!stackEmpty(ps));

return ps->a[ps->top - 1];

}

//獲取棧中有效元素個(gè)數(shù)

int stackSize(stack* ps)

{

assert(ps);

return ps->top;

}

柚子快報(bào)邀請(qǐng)碼778899分享：學(xué)習(xí) c語言 數(shù)據(jù)結(jié)構(gòu)之《棧》

http://yzkb.51969.com/

精彩文章