可算是把鏈表給結(jié)束了，很多小伙伴已經(jīng)迫不及待想看到棧和隊(duì)列了，那么它來了！相信有了順序表和鏈表的基礎(chǔ)，棧和隊(duì)列對(duì)于你們來講也是輕輕松松，那我就廢話不多說，直接進(jìn)入今天的重點(diǎn)：

1、棧的介紹：

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

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

出棧：棧的刪除操作叫做出棧。出數(shù)據(jù)也在棧頂。

棧的實(shí)現(xiàn)一般可以使用數(shù)組或者鏈表實(shí)現(xiàn)，相對(duì)而言數(shù)組的結(jié)構(gòu)實(shí)現(xiàn)更優(yōu)一些。因?yàn)閿?shù)組在尾上 插入數(shù)據(jù)的代價(jià)比較小。

本次我們是用動(dòng)態(tài)數(shù)組來實(shí)現(xiàn)棧！靜態(tài)棧在實(shí)際中一般不實(shí)用！

2、棧的常用接口實(shí)現(xiàn) 

 ?? 首先是我們動(dòng)態(tài)棧的結(jié)構(gòu)：

 有了順序表和鏈表的基礎(chǔ)我就直接上代碼了！

typedef int STDataType;
 
typedef struct Stack
{
	STDataType* a;
	int top;
	int capacity;
}ST;

?? 棧的初始化：

 ? 入棧操作：

 ?? 出棧操作：

出棧就很簡單了，我們直接使top--就可以了，因?yàn)槲覀儾迦霐?shù)據(jù)是先在top位置插入，然后再top++，這樣我們下次插入數(shù)據(jù)就會(huì)覆蓋pos位置的數(shù)據(jù)！注意：當(dāng)棧沒有初始化，沒有數(shù)據(jù)的情況下不能進(jìn)行出棧操作！

void StackPop(ST* ps)
{
	assert(ps);
	assert(ps->top > 0);
	ps->top--;
}

 ?? 取棧頂元素操作：

 我們知道top是棧頂元素的后一個(gè)，所以我們直接取top-1下標(biāo)位置的數(shù)據(jù)就可以！

STDataType StackTop(ST* ps)
{
	assert(ps);
	assert(ps->top > 0);
	return ps->a[ps->top - 1];
}

??  求棧的節(jié)點(diǎn)個(gè)數(shù)：

int StackSize(ST* ps)
{
	assert(ps);
	return ps->top;
}

?? 判斷棧是否為空：

 我們使用返回值為bool型的函數(shù)，bool類型只會(huì)返回true或false見下代碼：

bool StackEmpty(ST* ps)
{
	assert(ps);
	return ps->top == 0;
}

 ?? 銷毀棧操作：

 記得養(yǎng)成釋放動(dòng)態(tài)內(nèi)存的習(xí)慣哦！

void StackDestroy(ST* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->top = ps->capacity = 0;
}

 棧相對(duì)來說還是比較簡單了，棧的基本接口就到這里了，下面我們來實(shí)現(xiàn)隊(duì)列的基本接口操作！

3、隊(duì)列的介紹

隊(duì)列：只允許在一端進(jìn)行插入數(shù)據(jù)操作，在另一端進(jìn)行刪除數(shù)據(jù)操作的特殊線性表，隊(duì)列具有先進(jìn)先出FIFO(First In First Out) 入隊(duì)列：進(jìn)行插入操作的一端稱為隊(duì)尾出隊(duì)列，進(jìn)行刪除操作的一 端稱為隊(duì)頭！

隊(duì)列也可以數(shù)組和鏈表的結(jié)構(gòu)實(shí)現(xiàn)，使用鏈表的結(jié)構(gòu)實(shí)現(xiàn)更優(yōu)一些，因?yàn)槿绻褂脭?shù)組的結(jié)構(gòu)， 出隊(duì)列在數(shù)組頭上出數(shù)據(jù)，效率會(huì)比較低。

4、隊(duì)列的常用接口實(shí)現(xiàn) 

?? 隊(duì)列的結(jié)構(gòu)： 

 結(jié)構(gòu)搭建這里我們就不多說了，直接走代碼！

typedef int QDataType;
 
typedef struct QueueNode
{
	struct QueueNode* next;
	QDataType data;
}QNode;
 
typedef struct Queue
{
	QNode* head;
	QNode* tail;
}Queue;

?? 隊(duì)列的初始化：

這里我們只需要初始化隊(duì)頭指針和隊(duì)尾指針就可以了！ 

void QueueInit(Queue* pq)
{
	assert(pq);
	pq->head = pq->tail = NULL;
}

?? 隊(duì)尾入節(jié)點(diǎn)：

 ?? 隊(duì)頭出節(jié)點(diǎn)：

??  取隊(duì)頭節(jié)點(diǎn)數(shù)據(jù)：

QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(pq->head);
	
	return pq->head->data;
}

?? 取隊(duì)尾節(jié)點(diǎn)數(shù)據(jù)：

QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(pq->head);
 
	return pq->tail->data;
}

??  求隊(duì)列節(jié)點(diǎn)個(gè)數(shù)：

int QueueSize(Queue* pq)
{    
    int size = 0;
    QNode* cur = pq->head;
    assert(pq);
    while (cur)
    {
        ++size;
        cur = cur->next;
    }
    return size;
}

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

跟上面棧一樣使用bool型類型

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

?? 銷毀隊(duì)列操作：

void QueueDestory(Queue* pq)
{
	assert(pq);
	QNode* cur = pq->head;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->head = pq->tail = NULL;
}

其實(shí)棧和隊(duì)列這一章算簡單的，如果有前面順序表和鏈表的基礎(chǔ)，這個(gè)就是輕輕松松的事，所以我只在重點(diǎn)的地方畫了圖解，沒畫圖解的地方相信小伙伴們也是看得懂的！

gitee(碼云)：Mercury. (zzwlwp) - Gitee.com       

到此這篇關(guān)于C++ 棧和隊(duì)列的實(shí)現(xiàn)超詳細(xì)解析的文章就介紹到這了,更多相關(guān)C++ 棧和隊(duì)列內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論