一、棧的表示和實(shí)現(xiàn)

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

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

（圖片來(lái)自比特就業(yè)課）

先入后出就類(lèi)似與你裝手槍彈夾，你先放入的子彈會(huì)在彈夾底部，最后放入的子彈是在彈夾頂部，你開(kāi)手槍是先打出彈夾頂端的子彈。
我們這里先定義一個(gè)棧的類(lèi)型：

typedef int STDataType;//方便將來(lái)如果需要其他類(lèi)型的數(shù)據(jù)，可以直接修改int的類(lèi)型
typedef struct Stack
{
	STDataType*a;//棧底指針
	int top;//棧頂標(biāo)號(hào)
	int capacity;//容量
}ST;

本文介紹以順序表（數(shù)組）實(shí)現(xiàn)棧，由此，所謂的入棧壓棧也不過(guò)是順序表的尾插尾刪，如果讀者想以鏈表實(shí)現(xiàn)也是可以的，方法不唯一。

2棧的初始化

關(guān)于棧的初始化：我們這里以容量大小4的棧為例，剛開(kāi)始因?yàn)闂＠餂](méi)有數(shù)據(jù)我們用top=0標(biāo)記，需要注意的是：傳過(guò)來(lái)的棧底指針不能為空，開(kāi)辟空間時(shí)萬(wàn)一沒(méi)有開(kāi)辟成功返回一個(gè)空指針也要丟棄。

#include<assert.h>
#include<stdlib.h>//malloc函數(shù)頭文件
void StackInit(ST*ps)//棧初始化
{
	assert(ps);//防止傳過(guò)來(lái)的指針是空指針
	ps->a = (STDataType)malloc(sizeof(STDataType) * 4);//malloc開(kāi)辟一塊空間出來(lái)，由STDataType類(lèi)型進(jìn)行管理
	//malloc，及后文出現(xiàn)的realloc、free函數(shù)詳情見(jiàn)筆者動(dòng)態(tài)內(nèi)存管理文章
	if (ps->a == NULL)
	{
		printf("realloc fail\n");
		exit(-1);//終止程序
	}
	ps->capacity=4;
	//這里以開(kāi)辟4個(gè)數(shù)據(jù)容量大小的棧為例，你也可以寫(xiě)其他數(shù)字
	//如果壓棧的時(shí)候內(nèi)存不夠，可以在后面提到的壓棧函數(shù)里面進(jìn)行擴(kuò)容
	ps->top = 0;//剛開(kāi)始棧里沒(méi)有值時(shí)，用top=0標(biāo)記，后續(xù)每放入一個(gè)top++
	//關(guān)于top詳細(xì)用法請(qǐng)往下看1.3壓棧部分
}

3壓棧(棧頂插入一個(gè)數(shù)據(jù))

如上圖，我們現(xiàn)在開(kāi)辟了一塊空間，a和top都在棧頂，我們往里面入一個(gè)數(shù)據(jù)1

1進(jìn)入棧之后，1就是棧頂元素了，那如果我想繼續(xù)入棧，就是要在top的位置放入一個(gè)數(shù)據(jù)讓新放入的數(shù)據(jù)成為新的棧頂元素，然后以此類(lèi)推，每次入一個(gè)元素，top++，top不是表示棧頂元素位置，而是棧頂元素下一個(gè)位置。

#include<assert.h>//assert函數(shù)頭文件
#include<stdlib.h>//realloc函數(shù)頭文件
void StackPush(ST*ps, STDataType x)//棧頂插入數(shù)據(jù)（入棧）
{
	assert(ps);
	if (ps->top == ps->capacity)
	{
		STDataType*tmp = realloc(ps->a, ps->capacity * 2 * sizeof(STDataType));
		//realloc是在原先開(kāi)辟的空間上繼續(xù)往后開(kāi)辟一塊空間，詳細(xì)見(jiàn)筆者動(dòng)態(tài)內(nèi)存文章
		//擴(kuò)容一般擴(kuò)2倍
		if (tmp == NULL)//擴(kuò)容失?。ū热鐑?nèi)存已經(jīng)不夠你再開(kāi)辟空間了）會(huì)返回空指針
		{
			printf("realloc fail\n");
			exit(-1);//終止程序
		}
		else
		{
			ps->a = tmp;
			ps->capacity *= 2;
		}
	}
	ps->a[ps->top] = x;//a是一個(gè)指針，a[x]==*(a+x)
	ps->top++;
}

4出棧(棧頂刪除一個(gè)數(shù)據(jù))

出棧非常簡(jiǎn)單，我們以下圖為例：

圖中我們棧里已經(jīng)存放了4個(gè)數(shù)據(jù)1、2、3、4，那我們現(xiàn)在要進(jìn)行出棧操作,也就是刪除4怎么辦？直接top–即可

到這里肯定會(huì)有小伙伴有疑問(wèn)，憑什么你top–一下就是出棧了，你4都沒(méi)刪除啊？解釋如下：我們?cè)?.3壓棧部分就說(shuō)過(guò)“top不是表示棧頂元素位置，而是棧頂元素下一個(gè)位置”，那現(xiàn)在我top在4這里，說(shuō)明3才是真正的棧頂元素，4已經(jīng)不在棧的管轄范圍內(nèi)了。

void StackPop(ST*ps)//棧頂刪除數(shù)據(jù)（出棧）
{
	assert(ps);
	assert(ps->top > 0);//?？樟耍{(diào)用Pop，直接中止程序報(bào)錯(cuò)
	ps->top--;
}

關(guān)于ps->top > 0，是這樣的：假設(shè)你原先棧里沒(méi)有有一個(gè)元素

你top–就是往下訪(fǎng)問(wèn)未知的領(lǐng)域了，這是非常嚴(yán)重的問(wèn)題，所以我們這里用assert斷言一下，防止棧里什么元素也沒(méi)有讓top標(biāo)記到了未知領(lǐng)域。（再次強(qiáng)調(diào)一下：top不是表示棧頂元素位置，而是棧頂元素下一個(gè)位置）

5取棧頂元素

STDataType StackTop(ST*ps)//取棧頂數(shù)據(jù)
{
	assert(ps);
	assert(ps->top > 0);//?？樟?，調(diào)StackTop，直接中止程序報(bào)錯(cuò)
	return ps->a[ps->top - 1];//top是棧頂元素下一個(gè)位置,top-1是棧頂元素
	//a[m]==*(a+m)
}

這里的思路和1.4幾乎一樣，也要防止棧里什么也沒(méi)有的情況，然后正常返回棧頂元素即可，因?yàn)閠op是棧頂元素下一個(gè)位置,top-1是棧頂元素，然后你正常寫(xiě)就行，這里的
a[ps->top - 1]你也可以寫(xiě)成*(a+(ps->top - 1)),這個(gè)寫(xiě)法讀者可參加筆者以前的指針文章，這里不再贅述。

6取棧頂元素

int StackSize(ST*ps)//棧的數(shù)據(jù)個(gè)數(shù)
{
	assert(ps);
	return ps->top;
}

這個(gè)就更簡(jiǎn)單了，直接返回top的值就可以了，為什么呢，我們看兩張圖即可
圖一：

圖二：

圖一是壓棧前，沒(méi)有一個(gè)元素，top=0，圖二是壓棧后，top++，top=1。同樣的以此類(lèi)推，我們每加入1個(gè)元素，top++，每減去一個(gè)元素，top–。元素個(gè)數(shù)永遠(yuǎn)=top值，所以我們這里的函數(shù)直接返回top值即可。

7判斷棧是否為空

int StackEmpty(ST*ps)//判斷棧是不是空
{
	assert(ps);
	return ps->top == 0;
}

由1.6知，我們的top值是和棧里元素個(gè)數(shù)一樣的，所以我們直接return ps->top == 0；即可，如果ps->top == 0這個(gè)表達(dá)式成立表達(dá)式值為1，反之為0。

二、隊(duì)列的表示和實(shí)現(xiàn)

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

隊(duì)列：只允許在一端插入數(shù)據(jù)操作，在另一端進(jìn)行刪除數(shù)據(jù)操作的特殊線(xiàn)性表，隊(duì)列具有先進(jìn)先出的性質(zhì)
入隊(duì)列：進(jìn)行插入操作的一端稱(chēng)為隊(duì)尾
出隊(duì)列：進(jìn)行刪除操作的一端稱(chēng)為隊(duì)頭

（圖片來(lái)自比特就業(yè)課）

類(lèi)似你走人工通道那樣，你排在前面的，你先出去

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

由于隊(duì)列的隊(duì)頭出，隊(duì)尾入，非常類(lèi)似單鏈表的頭刪和尾插，我們這里介紹以單鏈表實(shí)現(xiàn)隊(duì)列，如下圖，現(xiàn)有3個(gè)節(jié)點(diǎn)的單鏈表：

比如現(xiàn)在，我要隊(duì)頭出一個(gè)，也就是把單鏈表節(jié)點(diǎn)第一個(gè)節(jié)點(diǎn)刪掉（頭刪）

或者隊(duì)尾入一個(gè)，也就是單鏈表的尾插

代碼如下（示例）：

typedef int QDataType;
typedef struct QueueNode
{
	struct QueueNode*next;
	QDataType data;
}QNode;//這里和單鏈表定義一樣，有需要的可以看一下筆者之前的單鏈表文章
typedef struct Queue//定義一個(gè)結(jié)構(gòu)體存儲(chǔ)頭節(jié)點(diǎn)地址和尾節(jié)點(diǎn)地址，方便后面頭刪和尾插
{
	QNode*head;
	QNode*tail;
}Queue;

3隊(duì)列初始化

代碼如下（示例）：

void QueueInit(Queue*pq)隊(duì)列初始化,pq是一個(gè)結(jié)構(gòu)體指針
{
	assert(pq);//判斷pq是否是空指針
	pq->head  = NULL;
	pq->tail = NULL;
}

4入隊(duì)（隊(duì)尾插入一個(gè)數(shù)據(jù)）

void QueuePush(Queue*pq, QDataType x)//入隊(duì)（隊(duì)尾入）
{
	assert(pq);
	QNode*newnode = (QNode*)malloc(sizeof(QNode));//開(kāi)辟出一塊空間給newnode
	if (newnode == NULL)//有可能剩余內(nèi)存不夠開(kāi)辟空間，malloc開(kāi)辟失敗會(huì)返回空指針
	{
		printf("開(kāi)辟空間失敗\n");
		exit(-1);//退出程序
	}
	newnode->data = x;
	newnode->next = NULL;
	if (pq->tail == NULL)//原先隊(duì)列里沒(méi)有任何數(shù)據(jù)，頭和尾指針都指向NULL
	{
		pq->head = pq->tail = newnode;
	}
	else
	{
		pq->tail->next = newnode;
		pq->tail = newnode;
	}
}

關(guān)于下面if這段代碼解釋如下：

    if (pq->tail == NULL)
	{
		pq->head = pq->tail = newnode;
	}
	else
	{
		pq->tail->next = newnode;
		pq->tail = newnode;
	}

原先隊(duì)列里沒(méi)有任何數(shù)據(jù)，頭和尾指針都指向NULL

當(dāng)你往隊(duì)列里面放了一個(gè)數(shù)據(jù)，頭和尾指針是指向新的數(shù)據(jù)（頭和尾指針仍指向一個(gè)）

如果你想再加1個(gè)節(jié)點(diǎn)，你首先得把兩節(jié)點(diǎn)連上，也就是pq->tail->next = newnode;（沒(méi)接上之前tail還指向第一個(gè)節(jié)點(diǎn)），接上之后tail指針指向第二節(jié)點(diǎn)

5出隊(duì)（隊(duì)頭刪除一個(gè)數(shù)據(jù)）

void QueuePop(Queue*pq)//出隊(duì)（隊(duì)頭出）
{
	assert(pq);
	assert(pq->head);//要出隊(duì)，隊(duì)里也要有數(shù)據(jù)可以出	
	//原隊(duì)列只有1個(gè)數(shù)據(jù)
	if (pq->head->next == NULL)
	{
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	//原隊(duì)列有多個(gè)數(shù)據(jù)
	else
	{
		QNode*next = pq->head->next;
		free(pq->head);
		pq->head = next;
	}
}

關(guān)于出隊(duì)，這里要分2種情況討論：

1.原隊(duì)列只有1個(gè)數(shù)據(jù)

只有一個(gè)數(shù)據(jù)的時(shí)候，頭和尾指針都指向1節(jié)點(diǎn)，他們的next是空指針，所以我們以這個(gè)條件為判斷。又因?yàn)橐鲫?duì)（隊(duì)頭刪除一個(gè)數(shù)據(jù)），因?yàn)橹挥幸粋€(gè)節(jié)點(diǎn)，也就是把這個(gè)節(jié)點(diǎn)給刪掉，我們用free函數(shù)釋放掉head指向的空間。釋放完，那塊空間已經(jīng)還給內(nèi)存了，這時(shí)你的頭和尾指針就不能指向那塊空間了，我們用空指針賦值。
2.原隊(duì)列有多個(gè)數(shù)據(jù)

我們現(xiàn)在要出隊(duì)（隊(duì)頭刪除一個(gè)數(shù)據(jù)），也就是把1節(jié)點(diǎn)刪掉，我們先創(chuàng)建一個(gè)變量next找到2節(jié)點(diǎn)位置，然后free掉1節(jié)點(diǎn)的空間

1節(jié)點(diǎn)空間free掉之后，把next（指向2節(jié)點(diǎn)）賦給head，讓頭指針指向2節(jié)點(diǎn)。

6取隊(duì)頭數(shù)據(jù)

QDataType QueueFront(Queue*pq)//取隊(duì)頭數(shù)據(jù)
{
	assert(pq);
	assert(pq->head);
	return pq->head->data;
}

7取隊(duì)尾數(shù)據(jù)

QDataType QueueBack(Queue*pq)//取隊(duì)尾數(shù)據(jù)
{
	assert(pq);
	assert(pq->head);
	return pq->tail->data;
}

8計(jì)算隊(duì)列中數(shù)據(jù)個(gè)數(shù)

int QueueSize(Queue*pq)//隊(duì)內(nèi)數(shù)據(jù)個(gè)數(shù)
{
	assert(pq);
	int size = 0;
	QNode*cur = pq->head;
	while (cur)//cur!=NULL進(jìn)行循環(huán),NULL是遍歷完tail之后出現(xiàn)的
	{
		size++;
		cur = cur->next;
	}
	return size;
}

9判斷隊(duì)列是否為空

bool QueueEmpty(Queue*pq)
{
	assert(pq);
	return pq->head == NULL;
}

這一般是作為一個(gè)輔助函數(shù)來(lái)使用，bool 就是用來(lái)判斷真假的數(shù)據(jù)類(lèi)型，如果表達(dá)式：pq->head == NULL成立返回true,反之返回false

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

void QueueDestory(Queue*pq)//隊(duì)列銷(xiāo)毀
{
	assert(pq);
	QNode*cur = pq->head;
	while (cur)//cur!=NULL進(jìn)行循環(huán),NULL是遍歷完tail之后出現(xiàn)的
	{
		QNode*next = cur->next;
		free(cur);//free是釋放指向的空間，指針還是在的
		cur = next;
	}
	pq->head = pq->tail = NULL;
}

如上圖，我們創(chuàng)建一個(gè)變量cur并用head指針賦值。然后找到第二個(gè)節(jié)點(diǎn)，用cur->next標(biāo)記,標(biāo)記完我們釋放掉cur（釋放的第一個(gè)節(jié)點(diǎn)空間,指針還是在的），釋放完，cur開(kāi)始遍歷第二個(gè)節(jié)點(diǎn)，也就是我們先前用next標(biāo)記的空間。。。剩下的以此類(lèi)推。cur!=NULL進(jìn)行循環(huán),NULL是遍歷完tail之后出現(xiàn)的，當(dāng)循環(huán)不進(jìn)行說(shuō)明已經(jīng)遍歷完了尾指針指向的節(jié)點(diǎn)，頭和尾節(jié)點(diǎn)已經(jīng)不需要了，我們用空指針賦值。

總結(jié)

本文介紹了棧和隊(duì)列的相關(guān)原理及各個(gè)接口函數(shù)，內(nèi)容較多，知識(shí)點(diǎn)量大，希望讀者耐心學(xué)習(xí)，相信你一定會(huì)有所收獲，祝讀者學(xué)習(xí)愉快~更多關(guān)于C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)棧與隊(duì)列的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

最新評(píng)論