日本免费高清视频-国产福利视频导航-黄色在线播放国产-天天操天天操天天操天天操|www.shdianci.com

學無先后，達者為師

網站首頁 編程語言 正文

C++?棧和隊列的實現超詳細解析_C 語言

作者：程序猿教你打籃球 ? 更新時間： 2022-05-26 編程語言

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

1、棧的介紹：

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

壓棧：棧的插入操作叫做進棧/壓棧/入棧，入數據在棧頂。

出棧：棧的刪除操作叫做出棧。出數據也在棧頂。

棧的實現一般可以使用數組或者鏈表實現，相對而言數組的結構實現更優一些。因為數組在尾上 插入數據的代價比較小。

本次我們是用動態數組來實現棧！靜態棧在實際中一般不實用！

2、棧的常用接口實現?

??? 首先是我們動態棧的結構：

?有了順序表和鏈表的基礎我就直接上代碼了！

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

?? 棧的初始化：

?? 入棧操作：

??? 出棧操作：

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

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

??? 取棧頂元素操作：

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

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

??? 求棧的節點個數：

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

?? 判斷棧是否為空：

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

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

??? 銷毀棧操作：

?記得養成釋放動態內存的習慣哦！

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

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

3、隊列的介紹

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

隊列也可以數組和鏈表的結構實現，使用鏈表的結構實現更優一些，因為如果使用數組的結構， 出隊列在數組頭上出數據，效率會比較低。

4、隊列的常用接口實現?

?? 隊列的結構：?

?結構搭建這里我們就不多說了，直接走代碼！

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

?? 隊尾入節點：

??? 隊頭出節點：

??? 取隊頭節點數據：

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

?? 取隊尾節點數據：

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

??? 求隊列節點個數：

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

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

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

原文鏈接：https://blog.csdn.net/m0_61784621/article/details/123501908

欄目分類
最近更新