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

1、棧的介紹：

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

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

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

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

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

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

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

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

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

?? 棧的初始化：

 ? 入棧操作：

 ?? 出棧操作：

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

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

 ?? 取棧頂元素操作：

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

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

??  求棧的節(jié)點個數(shù)：

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

?? 判斷棧是否為空：

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

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

 ?? 銷毀棧操作：

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

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

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

3、隊列的介紹

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

隊列也可以數(shù)組和鏈表的結(jié)構(gòu)實現(xiàn)，使用鏈表的結(jié)構(gòu)實現(xiàn)更優(yōu)一些，因為如果使用數(shù)組的結(jié)構(gòu)， 出隊列在數(shù)組頭上出數(shù)據(jù)，效率會比較低。

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

?? 隊列的結(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;

?? 隊列的初始化：

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

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

?? 隊尾入節(jié)點：

 ?? 隊頭出節(jié)點：

??  取隊頭節(jié)點數(shù)據(jù)：

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

?? 取隊尾節(jié)點數(shù)據(jù)：

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

??  求隊列節(jié)點個數(shù)：

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

?? 判斷隊列是否為空：

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

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

?? 銷毀隊列操作：

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;
}

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

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

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

最新評論