柚子快報(bào)激活碼778899分享：【數(shù)據(jù)結(jié)構(gòu)】棧和隊(duì)列

http://yzkb.51969.com/

Hi~！這里是奮斗的小羊，很榮幸您能閱讀我的文章，誠(chéng)請(qǐng)?jiān)u論指點(diǎn)，歡迎歡迎 ~~ ??個(gè)人主頁(yè)：奮斗的小羊 ??所屬專(zhuān)欄：C語(yǔ)言

?本系列文章為個(gè)人學(xué)習(xí)筆記，在這里撰寫(xiě)成文一為鞏固知識(shí)，二為展示我的學(xué)習(xí)過(guò)程及理解。文筆、排版拙劣，望見(jiàn)諒。

目錄

前言一、棧1、棧的結(jié)構(gòu)和概念2、實(shí)現(xiàn)棧的方法選擇3、棧的實(shí)現(xiàn)3.1完整代碼3.2特殊的接口3.3訪(fǎng)問(wèn)棧的所有元素

4、用棧解決括號(hào)匹配的問(wèn)題

二、隊(duì)列1、隊(duì)列的概念和結(jié)構(gòu)2、隊(duì)列的實(shí)現(xiàn)3、隊(duì)列完整代碼

總結(jié)

前言

棧作為一種比較特殊的存儲(chǔ)結(jié)構(gòu)，可以使用數(shù)組、單鏈表、雙向鏈表等多種方法來(lái)實(shí)現(xiàn)，其在函數(shù)調(diào)用和遞歸、表達(dá)式求值、瀏覽器的歷史記錄、撤銷(xiāo)操作、系統(tǒng)調(diào)用等多個(gè)場(chǎng)景中被廣泛使用。

一、棧

1、棧的結(jié)構(gòu)和概念

棧是一種特殊的線(xiàn)性表，其只允許在固定的一端進(jìn)行插入和刪除元素的操作。 進(jìn)行元素的插入和刪除的一端稱(chēng)為棧頂，另一端稱(chēng)為棧底，棧中的數(shù)據(jù)遵循后進(jìn)先出的原則。 壓棧：棧的插入操作叫做進(jìn)棧、壓棧、入棧 出棧：棧的刪除操作叫做出棧

棧的結(jié)構(gòu)類(lèi)似于桶，只能從上面進(jìn)，只能從上面出，因此我們一般只關(guān)心棧頂。

2、實(shí)現(xiàn)棧的方法選擇

了解的棧的結(jié)構(gòu)，接下來(lái)就要考慮如何實(shí)現(xiàn)棧。 在這之前我們學(xué)習(xí)了順序表（底層就是數(shù)組）和鏈表，鏈表又分單鏈表和雙向鏈表，用哪個(gè)方法實(shí)現(xiàn)效果最好呢？

上篇文章中我們簡(jiǎn)單地列舉的順序表和鏈表的比較，如下：

順序表鏈表（雙向鏈表）存儲(chǔ)空間上邏輯、物理上都連續(xù)邏輯上連續(xù)、物理上不一定連續(xù)隨機(jī)訪(fǎng)問(wèn)復(fù)雜度O(1)復(fù)雜度O(N)任意位置插入或刪除數(shù)據(jù)需要挪動(dòng)數(shù)據(jù)，復(fù)雜度O(N)只需要改變指針指向插入動(dòng)態(tài)順序表，空間不夠時(shí)擴(kuò)容，擴(kuò)容本身就有消耗，還容易空間浪費(fèi)沒(méi)有容量的概念應(yīng)用場(chǎng)景數(shù)據(jù)高效存儲(chǔ)+頻繁訪(fǎng)問(wèn)任意位置頻繁插入、刪除數(shù)據(jù)緩存利用率高低

其中我們關(guān)鍵看緩存利用率，簡(jiǎn)單地說(shuō)緩存利用率是指計(jì)算機(jī)系統(tǒng)中緩存（如CPU緩存、內(nèi)存緩存等）被有效利用的程度。 CPU執(zhí)行指令運(yùn)算要訪(fǎng)問(wèn)數(shù)據(jù)，會(huì)先去緩存中找有沒(méi)有這個(gè)數(shù)據(jù)，如果有，說(shuō)明緩存命中了；如果沒(méi)有，說(shuō)明緩存未命中，就從主存中讀取一段連續(xù)內(nèi)存空間的數(shù)據(jù)到緩存，繼續(xù)找。 而我們知道在物理結(jié)構(gòu)上順序表是連續(xù)的，鏈表不連續(xù)。那從主存中讀取一段連續(xù)內(nèi)存空間的數(shù)據(jù)到緩存時(shí)鏈表讀取到的很可能不是我們想要的數(shù)據(jù)，從而造成緩存污染。 雖然順序表在擴(kuò)容的時(shí)候時(shí)間和空間都有消耗，而且還容易存在空間浪費(fèi)，但是動(dòng)態(tài)擴(kuò)容也不是說(shuō)很頻繁，只有在空間不夠時(shí)才擴(kuò)容。 其實(shí)在實(shí)現(xiàn)棧上順序表和鏈表只是五十步和百步的區(qū)別，只是相對(duì)而言順序表更好一點(diǎn)。

3、棧的實(shí)現(xiàn)

3.1完整代碼

用順序表的方法實(shí)現(xiàn)棧，和我們之前實(shí)現(xiàn)的順序表沒(méi)多大區(qū)別，只是棧中的元素只能從棧頂進(jìn)從棧頂出，遵循后進(jìn)先出的原則。 這里我們就先展示用順序表的方法實(shí)現(xiàn)的棧的完整代碼，其中的細(xì)節(jié)再一一介紹。 stack.h:

#pragma once

#include

#include

#include

#include

typedef int st_data_type;

typedef struct stack

{

st_data_type* arr;

int top;

int capacity;

}stack;

//初始化和銷(xiāo)毀

void stack_init(stack* pst);

void stack_destroy(stack* pst);

//入棧和出棧

void stack_push(stack* pst, st_data_type x);

void stack_pop(stack* pst);

//取出棧頂元素

st_data_type stack_top(stack* pst);

//判空

bool stack_empty(stack* pst);

//獲取數(shù)據(jù)個(gè)數(shù)

int stack_size(stack* pst);

stack.c:

#include "stack.h"

//初始化

void stack_init(stack* pst)

{

assert(pst);

pst->arr = NULL;

pst->top = pst->capacity = 0;

}

//入棧

void stack_push(stack* pst, st_data_type x)

{

assert(pst);

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

{

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

st_data_type* tmp = (st_data_type*)realloc(pst->arr, newcapacity * sizeof(st_data_type));

if (tmp == NULL)

{

perror("realloc fail!");

return 1;

}

pst->arr = tmp;

tmp = NULL;

pst->capacity = newcapacity;

}

pst->arr[pst->top] = x;

pst->top++;

}

//出棧

void stack_pop(stack* pst)

{

assert(pst);

assert(pst->top > 0);

pst->top--;

}

//取出棧頂元素

st_data_type stack_top(stack* pst)

{

assert(pst);

assert(pst->top > 0);

return pst->arr[pst->top-1];

}

//銷(xiāo)毀

void stack_destroy(stack* pst)

{

assert(pst);

free(pst->arr);

pst->arr = NULL;

pst->capacity = pst->top = 0;

}

//判空

bool stack_empty(stack* pst)

{

assert(pst);

return pst->top == 0;

}

//獲取元素個(gè)數(shù)

int stack_size(stack* pst)

{

assert(pst);

return pst->top;

}

test.c:

#define _CRT_SECURE_NO_WARNINGS

#include "stack.h"

void test()

{

stack st;

stack_init(&st);

//...

stack_push(&st, 1);

stack_push(&st, 2);

stack_push(&st, 3);

stack_push(&st, 4);

stack_destroy(&st);

}

int main()

{

test();

return 0;

}

可以看到因?yàn)闂＝Y(jié)構(gòu)的特殊，棧的實(shí)現(xiàn)比之前的順序表簡(jiǎn)單多了，少了很多接口（函數(shù)）。 其中初始化、入棧、銷(xiāo)毀函數(shù)跟之前實(shí)現(xiàn)的順序表是一樣的，這里就不再贅述。

3.2特殊的接口

出棧：

//出棧

void stack_pop(stack* pst)

{

assert(pst);

assert(pst->top > 0);

pst->top--;

}

因?yàn)槌鰲＞褪莿h除棧頂?shù)囊粋€(gè)元素?cái)?shù)據(jù)，所以出棧的實(shí)現(xiàn)只需要將top--就行了。

取出棧頂元素?cái)?shù)據(jù)：

//取出棧頂元素

st_data_type stack_top(stack* pst)

{

assert(pst);

assert(pst->top > 0);

return pst->arr[pst->top-1];

}

在取棧頂元素的時(shí)候，極其容易寫(xiě)出：return pst->arr[pst->top]; 這條代碼，因?yàn)槲覀兿乱庾R(shí)思維會(huì)認(rèn)為最后一個(gè)元素?cái)?shù)據(jù)的下標(biāo)為top，其實(shí)不是的，這里跟順序表中的size一樣表示的是棧中元素的個(gè)數(shù)，所以棧中最后一個(gè)元素的下標(biāo)是top-1。

判空、獲取數(shù)據(jù)個(gè)數(shù)：

//判空

bool stack_empty(stack* pst)

{

assert(pst);

return pst->top == 0;

}

//獲取元素個(gè)數(shù)

int stack_size(stack* pst)

{

assert(pst);

return pst->top;

}

如果棧中沒(méi)有數(shù)據(jù)，則pst->top == 0;為真，返回ture，反之則返回false。

3.3訪(fǎng)問(wèn)棧的所有元素

由于棧后進(jìn)先出的特殊結(jié)構(gòu)，訪(fǎng)問(wèn)棧的所有元素我們不能像順序表那樣利用下標(biāo)循環(huán)打印，應(yīng)該使用下面這種方式：

while (!stack_empty(&pst))

{

printf("%d ", stack_top(&pst));

stack_pop(&pst);

}

拿到棧頂?shù)脑睾笤倌孟乱粋€(gè)元素前需要先將棧頂?shù)脑貜棾觯ㄒ簿褪莿h除），才能訪(fǎng)問(wèn)到下一個(gè)元素。 但是這也導(dǎo)致了一個(gè)問(wèn)題，就是我們?cè)L問(wèn)完棧中的所有元素后棧也就空了，不過(guò)不用擔(dān)心這是正常現(xiàn)象。

這里有個(gè)問(wèn)題: 棧的原則是后進(jìn)先出，如果我們?nèi)霔５捻樞蚴?、2、3、4，那出棧的順序一定是4、3、2、1嗎？ 其實(shí)不是的，因?yàn)槲覀兛梢赃呥M(jìn)邊出。

#define _CRT_SECURE_NO_WARNINGS

#include "stack.h"

void test()

{

stack st;

stack_init(&st);

stack_push(&st, 1);

printf("%d ", stack_top(&st));

stack_pop(&st);

stack_push(&st, 2);

printf("%d ", stack_top(&st));

stack_pop(&st);

stack_push(&st, 3);

stack_push(&st, 4);

while (!stack_empty(&st))

{

printf("%d ", stack_top(&st));

stack_pop(&st);

}

stack_destroy(&st);

}

int main()

{

test();

return 0;

}

也就是說(shuō)，出棧的順序可以有多種。

4、用棧解決括號(hào)匹配的問(wèn)題

題目：有效的括號(hào)—leetcode

題目描述：

我們?cè)趺词褂脳５奶攸c(diǎn)來(lái)解決這個(gè)問(wèn)題呢？

解題思路： 返回false的情況有兩種，一種是數(shù)量不匹配，一種是順序不匹配。 棧有后進(jìn)先出的特點(diǎn)，而括號(hào)匹配的問(wèn)題首先需要找到若干個(gè)左括號(hào)，然后再找右括號(hào)進(jìn)行一一配對(duì)，如果全部配對(duì)成功則返回true，否則返回false。 也就是說(shuō)當(dāng)我們拿到字符串中的第一個(gè)字符，如果是左括號(hào)則壓棧，如果是右括號(hào)則出棧與右括號(hào)配對(duì)，只要有一次配對(duì)不上就返回false。

有幾個(gè)需要注意的點(diǎn)或特殊情況：

如果拿到的第一個(gè)字符就是右括號(hào)（也就是棧為空時(shí)），這時(shí)則直接返回false當(dāng)在字符串中取到‘\0’退出循環(huán)后，還要再判斷一下棧是否為空，因?yàn)橛锌赡軛?nèi)還剩有壓進(jìn)去的左括號(hào)在每次返回前都要先銷(xiāo)毀棧，避免內(nèi)存泄漏

解題過(guò)程如下：

bool isValid(char* s) {

//創(chuàng)建棧并初始化

stack st;

stack_init(&st);

while (*s != '\0')

{

//左括號(hào)則壓棧

if (*s == '(' || *s == '[' || *s == '{')

{

stack_push(&st, *s);

}

//右括號(hào)則出棧，配對(duì)

else

{

if (stack_empty(&st))//拿到的第一個(gè)字符就是右括號(hào)

{

stack_destroy(&st);

return false;

}

//取

char top = stack_top(&st);

//刪

stack_pop(&st);

//如果不配對(duì)則直接返回false

if (top == '(' && *s != ')'

|| top == '[' && *s != ']'

|| top == '{' && *s != '}')

{

stack_destroy(&st);//避免內(nèi)存泄漏

return false;

}

}

s++;

}

//判斷棧內(nèi)是否還有未配對(duì)的左括號(hào)

bool ret = stack_empty(&st);

stack_destroy(&st);

return ret;

}

不管是棧后進(jìn)先出的原則，還是棧元素訪(fǎng)問(wèn)后就消失的特點(diǎn)，在這個(gè)題中都能較好的體現(xiàn)出來(lái)。

二、隊(duì)列

1、隊(duì)列的概念和結(jié)構(gòu)

隊(duì)列： 遵循先進(jìn)先出的原則，即最先被加入隊(duì)列的元素最先被取出。 入隊(duì)操作將新元素加入到隊(duì)列的末尾（隊(duì)尾），出隊(duì)操作則移除并返回隊(duì)列的第一個(gè)元素（隊(duì)頭）。

與棧不同的是，隊(duì)列結(jié)構(gòu)不管怎樣，入隊(duì)和出隊(duì)的順序總是一樣的。

隊(duì)列通常應(yīng)用于解耦和異步通信、任務(wù)調(diào)度、請(qǐng)求排隊(duì)、資源分配、數(shù)據(jù)處理流水線(xiàn)、HTTP請(qǐng)求等多種場(chǎng)景。

棧和隊(duì)列比較： 隊(duì)列既可以用鏈表實(shí)現(xiàn)也可以用數(shù)組實(shí)現(xiàn)，但單鏈表結(jié)構(gòu)總體更優(yōu)一些。因?yàn)槿绻褂脭?shù)組實(shí)現(xiàn)，則出隊(duì)列時(shí)剩余所有數(shù)據(jù)都要挪動(dòng)位置，復(fù)雜度O(N)； 而使用鏈表實(shí)現(xiàn)的隊(duì)列在插入和刪除操作上更高效，不涉及元素搬移的操作。

2、隊(duì)列的實(shí)現(xiàn)

將隊(duì)列看作一個(gè)特殊的單鏈表，則此單鏈表只有頭刪和尾插等操作，如果按照之前單鏈表的實(shí)現(xiàn)來(lái)完成隊(duì)列的尾插，只有一個(gè)頭節(jié)點(diǎn)的地址讓尾插效率不是很高，因?yàn)檫€要遍歷鏈表來(lái)找尾節(jié)點(diǎn)。 所以這里不再使用創(chuàng)建一個(gè)結(jié)構(gòu)體指針變量記錄第一個(gè)節(jié)點(diǎn)的方法，我們直接使用兩個(gè)指針?lè)謩e記錄第一個(gè)節(jié)點(diǎn)和最后一個(gè)節(jié)點(diǎn)，這樣入隊(duì)（尾插）和出隊(duì)（頭刪）效率更高。

typedef int QDataType;

//隊(duì)列節(jié)點(diǎn)結(jié)構(gòu)

typedef struct QueueNode

{

QDataType data;

struct QueueNode* next;

}QNode;

//隊(duì)尾插入

void QNodePush(QNode** pphead, QNode** pptail, QDataType x);

//隊(duì)頭刪除

void QNodePop(QNode** pphead, QNode** pptail);

但是這樣既要傳兩個(gè)指針還要傳二級(jí)指針，為了簡(jiǎn)化代碼我們用結(jié)構(gòu)體變量分裝起來(lái)，并且再添加一個(gè)整型值來(lái)記錄隊(duì)列元素個(gè)數(shù)。

//隊(duì)列結(jié)構(gòu)

typedef struct Queue

{

QNode* phead;

QNode* ptail;

int size;

}Que;

//初始化隊(duì)列結(jié)構(gòu)

void QueueInit(Que* pq);

//隊(duì)尾插入

void QNodePush(Que* pq, QDataType x);

//隊(duì)頭刪除

void QNodePop(Que* pq);

//隊(duì)列元素個(gè)數(shù)

int QNodeSize(Que* pq);

//取隊(duì)頭

QDataType QNodeFront(Que* pq);

//取隊(duì)尾

QDataType QNodeBack(Que* pq);

//判空

bool QNodeEmpty(Que* pq);

//銷(xiāo)毀隊(duì)列

void QNodeDestroy(Que* pq);

這樣一來(lái)我們只需要傳遞結(jié)構(gòu)體指針，就能改變頭指針和尾指針的指向，但是這個(gè)結(jié)構(gòu)體開(kāi)始需要初始化一下：

//初始化隊(duì)列結(jié)構(gòu)

void QueueInit(Que* pq)

{

assert(pq);

pq->phead = pq->ptail = NULL;

pq->size = 0;

}

隊(duì)尾插入：

//隊(duì)尾插入

void QNodePush(Que* pq, QDataType x)

{

assert(pq);

QNode* newnode = (QNode*)malloc(sizeof(QNode));

if (newnode == NULL)

{

perror("malloc fail");

return;

}

newnode->data = x;

newnode->next = NULL;

//沒(méi)有節(jié)點(diǎn)

if (pq->phead == NULL)

{

pq->phead = pq->ptail = newnode;

}

else//有節(jié)點(diǎn)

{

pq->ptail->next = newnode;

pq->ptail = newnode;

}

pq->size++;

}

入隊(duì)（尾插）需要注意的是，如果當(dāng)前隊(duì)列沒(méi)有節(jié)點(diǎn)，則頭指針和尾指針都要指向新節(jié)點(diǎn)。

隊(duì)頭刪除：

//隊(duì)頭刪除

void QNodePop(Que* pq)

{

assert(pq);

assert(pq->phead);//沒(méi)有節(jié)點(diǎn)

//一個(gè)節(jié)點(diǎn)

if (pq->phead == pq->ptail)

{

free(pq->phead);

pq->phead = pq->ptail = NULL;

}

//多個(gè)節(jié)點(diǎn)

else

{

QNode* next = pq->phead->next;

free(pq->phead);

pq->phead = next;

}

pq->size--;

}

出隊(duì)（頭刪）分為三種情況，沒(méi)有節(jié)點(diǎn)、一個(gè)節(jié)點(diǎn)和多個(gè)節(jié)點(diǎn)。 如果只有一個(gè)節(jié)點(diǎn)（頭指針和尾指針指向同一節(jié)點(diǎn)），則在釋放掉這個(gè)節(jié)點(diǎn)后頭指針和尾指針都要置NULL。

取隊(duì)頭、取隊(duì)尾：

//取隊(duì)頭

QDataType QNodeFront(Que* pq)

{

assert(pq);

assert(pq->phead);

return pq->phead->data;

}

//取隊(duì)尾

QDataType QNodeBack(Que* pq)

{

assert(pq);

assert(pq->ptail);

return pq->ptail->data;

}

while (!QNodeEmpty(&q))

{

printf("%d ", QNodeFront(&q));

//元素取完要?jiǎng)h除

QNodePop(&q);

}

取出隊(duì)列中的元素后需要彈出此元素才能取到下一個(gè)元素，這點(diǎn)與棧相同。

3、隊(duì)列完整代碼

queue.h:

#pragma once

#include

#include

#include

#include

typedef int QDataType;

//隊(duì)列節(jié)點(diǎn)結(jié)構(gòu)

typedef struct QueueNode

{

QDataType data;

struct QueueNode* next;

}QNode;

//隊(duì)列結(jié)構(gòu)

typedef struct Queue

{

QNode* phead;

QNode* ptail;

int size;

}Que;

//初始化隊(duì)列結(jié)構(gòu)

void QueueInit(Que* pq);

//隊(duì)尾插入

void QNodePush(Que* pq, QDataType x);

//隊(duì)頭刪除

void QNodePop(Que* pq);

//隊(duì)列元素個(gè)數(shù)

int QNodeSize(Que* pq);

//取隊(duì)頭

QDataType QNodeFront(Que* pq);

//取隊(duì)尾

QDataType QNodeBack(Que* pq);

//判空

bool QNodeEmpty(Que* pq);

//銷(xiāo)毀隊(duì)列

void QNodeDestroy(Que* pq);

queue.c:

#define _CRT_SECURE_NO_WARNINGS

#include "queue.h"

//初始化隊(duì)列結(jié)構(gòu)

void QueueInit(Que* pq)

{

assert(pq);

pq->phead = pq->ptail = NULL;

pq->size = 0;

}

//隊(duì)尾插入

void QNodePush(Que* pq, QDataType x)

{

assert(pq);

QNode* newnode = (QNode*)malloc(sizeof(QNode));

if (newnode == NULL)

{

perror("malloc fail");

return;

}

newnode->data = x;

newnode->next = NULL;

//沒(méi)有節(jié)點(diǎn)

if (pq->phead == NULL)

{

pq->phead = pq->ptail = newnode;

}

else//多個(gè)節(jié)點(diǎn)

{

pq->ptail->next = newnode;

pq->ptail = newnode;

}

pq->size++;

}

//隊(duì)頭刪除

void QNodePop(Que* pq)

{

assert(pq);

assert(pq->phead);//沒(méi)有節(jié)點(diǎn)

//一個(gè)節(jié)點(diǎn)

if (pq->phead == pq->ptail)

{

free(pq->phead);

pq->phead = pq->ptail = NULL;

}

//多個(gè)節(jié)點(diǎn)

else

{

QNode* next = pq->phead->next;

free(pq->phead);

pq->phead = next;

}

pq->size--;

}

//隊(duì)列元素個(gè)數(shù)

int QNodeSize(Que* pq)

{

assert(pq);

return pq->size;

}

//取隊(duì)頭

QDataType QNodeFront(Que* pq)

{

assert(pq);

assert(pq->phead);

return pq->phead->data;

}

//取隊(duì)尾

QDataType QNodeBack(Que* pq)

{

assert(pq);

assert(pq->ptail);

return pq->ptail->data;

}

//判空

bool QNodeEmpty(Que* pq)

{

assert(pq);

return pq->phead == NULL;

}

//銷(xiāo)毀隊(duì)列

void QNodeDestroy(Que* pq)

{

assert(pq);

while (pq->phead)

{

QNode* next = pq->phead->next;

free(pq->phead);

pq->phead = next;

}

pq->ptail = NULL;

pq->size = 0;

}

test.c:

#define _CRT_SECURE_NO_WARNINGS

#include "queue.h"

void test()

{

Que q;

QueueInit(&q);

QNodePush(&q, 1);

QNodePush(&q, 2);

QNodePush(&q, 3);

QNodePush(&q, 4);

QNodePop(&q);

while (!QNodeEmpty(&q))

{

printf("%d ", QNodeFront(&q));

//元素取完要?jiǎng)h除

QNodePop(&q);

}

printf("\n");

QNodeDestroy(&q);

}

int main()

{

test();

return 0;

}

總結(jié)

棧適合在需要臨時(shí)存儲(chǔ)、后進(jìn)先出的場(chǎng)景下使用，特別在處理遞歸、嵌套、層次結(jié)構(gòu)等問(wèn)題時(shí)非常有用棧的操作受限于其后進(jìn)先出的特性，在處理大量數(shù)據(jù)、需要隨機(jī)操作等情況下，不太適合使用棧隊(duì)列通常有一個(gè)固定的容量，一旦隊(duì)列達(dá)到最大容量，后續(xù)元素?zé)o法入隊(duì)，可能導(dǎo)致數(shù)據(jù)丟失或系統(tǒng)阻塞

柚子快報(bào)激活碼778899分享：【數(shù)據(jù)結(jié)構(gòu)】棧和隊(duì)列

http://yzkb.51969.com/

參考閱讀