前言

堆疊

堆疊的實作

介面展示

堆疊結構創建

堆疊的初始化

堆疊的銷毀

入堆疊

出堆疊

空堆疊判斷

堆疊頂資料獲取

堆疊存入資料個數

堆疊測驗

佇列

佇列的實作

介面展示

佇列型別創建

佇列初始化

佇列銷毀

入隊

出隊

佇列頭結點資料

佇列尾結點資料

佇列存入資料個數

判斷空佇列

佇列測驗

前言

本章主要講解：

資料結構中的堆疊和佇列的知識以及如何實作

堆疊

概念及結構

堆疊，一種特殊的線性表，其只允許在固定的一端進行插入和洗掉元素操作

進行資料插入和洗掉操作的一端 稱為堆疊頂，另一端稱為堆疊底

堆疊中的資料元素遵守后進先出 LIFO （ Last In First Out ）的原則

資料處理方式：

壓堆疊：堆疊的插入操作叫做進堆疊 / 壓堆疊 / 入堆疊， 入資料在堆疊頂

出堆疊：堆疊的洗掉操作叫做出堆疊， 出資料也在堆疊頂

圖示：

堆疊的實作

堆疊的實作一般可以使用 陣列或者鏈表實作

相對而言陣列的結構實作更優一些（陣列在尾上插入資料的代價比較小）

圖示：陣列堆疊

介面展示

注：定長的靜態堆疊實際中不實用，所以我們主要實作支持動態增長的陣列堆疊

// 支持動態增長的堆疊
typedef int STDataType;
typedef struct Stack
{
 STDataType* _a;
 int _top; // 堆疊頂
 int _capacity; // 容量
}Stack;
// 初始化堆疊
void StackInit(Stack* ps); 
// 入堆疊
void StackPush(Stack* ps, STDataType data); 
// 出堆疊
void StackPop(Stack* ps); 
// 獲取堆疊頂元素
STDataType StackTop(Stack* ps); 
// 獲取堆疊中有效元素個數
int StackSize(Stack* ps); 
// 檢測堆疊是否為空，如果為慷訓傳非零結果，如果不為慷訓傳0 
int StackEmpty(Stack* ps); 
// 銷毀堆疊
void StackDestroy(Stack* ps);

堆疊結構創建

動態陣列堆疊具有三個元素：陣列指標（指向開辟的空間），堆疊頂位置，堆疊的長度

參考代碼：

//堆疊型別結構
typedef struct Stack
{
	//陣列堆疊（指向陣列的指標）
	STDataType* a;
	//堆疊頂位置
	int top;
	//堆疊容量（陣列長度）
	int capacity;
}ST;

堆疊的初始化

注意：

堆疊頂的表示的位置需要考慮好

參考代碼：

//堆疊初始化
void StackInit(ST* ps)
{
	//避免傳入空指標
	assert(ps);
	ps->a = NULL;
	ps->top = 0;//定義top為堆疊最后資料的后一個位置
	//也可以選擇讓top為當前最后資料的位置 則初始化top=-1;
	ps->capacity = 0;
	return;
}

堆疊的銷毀

注：動態開辟的空間結束時也需要進行銷毀（避免記憶體泄漏）

參考代碼：

//堆疊銷毀
void StackDestroy(ST* ps)
{
	//避免傳入空指標
	assert(ps);
	free(ps->a);//釋放開辟的陣列堆疊空間
	ps->a = NULL;//置空，避免造成野指標
}

入堆疊

注意：

入堆疊考慮是否堆疊滿，堆疊滿則進行擴展堆疊長度
入堆疊成功更新堆疊頂位置

參考代碼：

//入堆疊
void StackPush(ST* ps, STDataType x)
{
	assert(ps);
	if (ps->top == ps->capacity)//堆疊滿的情況
	{
		//如果原來容量為0則讓新容量為4，否則為兩倍
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		//調整陣列堆疊大小（特別的：當陣列指標為NULL時，realloc的作用和malloc的作用一樣）
		STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(ST) * newcapacity);
		if (tmp == NULL)//tmp為NULL時則表示調整陣列空間失敗，那么就列印錯誤并結束行程
		{
			perror("realloc fail:");
			exit(-1);
		}
		ps->a = tmp;
		ps->capacity = newcapacity;
	}
	ps->a[ps->top] = x;//存入資料
	ps->top++;//top位置更新
	return;
}

出堆疊

注意：

對于空堆疊不能再進行出堆疊
堆疊頂位置減減實作出堆疊的效果

參考代碼：

//出堆疊
void StackPop(ST* ps)
{
	//避免傳入空指標
	assert(ps);
	//出堆疊到資料個數為0結束
	if (StackEmpty(ps))
		return;
	ps->top--;//讓top減減得到出堆疊的效果
	return;
}

注：這里我們封裝了一個判斷空堆疊的函式便于呼叫

空堆疊判斷

注：C語言沒有定義bool型別（C99之前），要在C里面使用需要包含頭檔案 <stdbool.h>

參考代碼：

//是否為空堆疊
bool StackEmpty(ST* ps)
{
	//避免傳入空指標
	assert(ps);

	return ps->top == 0;
}

堆疊頂資料獲取

注意：

空堆疊時無法獲取資料

注：這采用比較暴力的方式（斷言），當然也可以選擇if條件判斷（比較溫柔）

參考代碼：

//獲取堆疊頂資料
STDataType StackTop(ST* ps)
{
	//避免傳入空指標
	assert(ps);
	//空堆疊（top-1會越界訪問）
	assert(!StackEmpty(ps));//暴力斷言不為空堆疊
	return ps->a[ps->top - 1];//這里top-1才是堆疊頂資料的下標
}

堆疊存入資料個數

參考代碼：

//堆疊使用大小（存入資料個數）
int StackSize(ST* ps)
{
	//避免傳入空指標
	assert(ps);

	return ps->top;
}

堆疊測驗

示例代碼：

void test()
{
	ST st;
	StackInit(&st);

	StackPush(&st, 1);
	StackPush(&st, 2);
	StackPush(&st, 3);
	StackPush(&st, 4);

	printf("%d ", StackTop(&st));
	StackPop(&st);
	printf("%d ", StackTop(&st));
	StackPop(&st);

	StackPush(&st, 5);
	StackPush(&st, 6);

	while (!StackEmpty(&st))
	{
		printf("%d ", StackTop(&st));
		StackPop(&st);
	}
	StackDestroy(&st);
}

結果示圖：

佇列

概念及結構

佇列，只允許在一端進行插入資料操作，在另一端進行洗掉資料操作的特殊線性表，佇列具有先進先出FIFO(First In First Out)

資料處理方式

入佇列：進行插入操作的一端稱為隊尾

出佇列：進行洗掉操作的一端稱為隊頭

圖示：

佇列的實作

佇列也可以陣列和鏈表的結構實作，使用鏈表的結構實作更優一些（出佇列效率低）

圖示：鏈表佇列

介面展示

//默認佇列資料型別
typedef int QDataType;

//佇列節點型別（鏈表佇列）
typedef struct QueueNode
{
	//址域
	struct QueueNode* next;
	//值域
	QDataType data;
}QueueNode;
//佇列型別(記錄隊頭和隊尾)
typedef struct Queue
{
	QueueNode* head;//記錄佇列頭結點地址
	QueueNode* tail;//記錄佇列尾結點地址
	// size_t _size;//記錄佇列資料個數（可有可無，自己選擇）
}Queue;

//佇列初始化
void QueueInit(Queue* pq);
//void QueueInit(QueueNode** pphead, QueueNode** pptail);
//佇列銷毀
void QueueDestroy(Queue* pq);
//入佇列
void QueuePush(Queue* pq, QDataType x);
//出佇列
void QueuePop(Queue* pq);
//佇列頭結點資料
QDataType QueueFront(Queue* pq);
//佇列尾節點資料
QDataType QueueBack(Queue* pq);
//佇列存入資料個數
int QueueSize(Queue* pq);
//判斷空佇列
bool QueueEmpty(Queue* pq);

佇列型別創建

首先我們是個鏈表佇列，即需要創建節點型別

然后在佇列常用到入堆疊和出堆疊操作（與頭刪和尾插相關），為了便于找到頭結點和尾節點，這里創建一個佇列結構體，型別成員為兩個結點指標，用來記錄頭結點和尾節點地址

參考代碼：

//默認佇列資料型別
typedef int QDataType;

//佇列節點型別（鏈表佇列）
typedef struct QueueNode
{
	//址域
	struct QueueNode* next;
	//值域
	QDataType data;
}QueueNode;
//佇列型別(記錄隊頭和隊尾)
typedef struct Queue
{
	QueueNode* head;//記錄佇列頭結點地址
	QueueNode* tail;//記錄佇列尾結點地址
	// size_t _size;//記錄佇列資料個數（可有可無，自己選擇）
}Queue;

佇列初始化

最開始沒有資料，即頭指標和尾指標都為NULL

參考代碼：

//佇列初始化
void QueueInit(Queue* pq)
{
	//避免傳入引數錯誤
	assert(pq);
	//初始化
	pq->head = pq->tail = NULL;
	return;
}

佇列銷毀

注意：

結點時一個個開辟的，需要一個個進行釋放
釋放前記得保存下個節點地址，避免地址丟失

參考代碼：

//佇列銷毀
void QueueDestroy(Queue* pq)
{
	//避免傳入引數錯誤
	assert(pq);
	//創建尋址指標
	QueueNode* cur = pq->head;
	while (cur)
	{
		//保存下個結點地址
		QueueNode* next = cur->next;
		//釋放當前結點
		free(cur);
		//找到下一個結點
		cur = next;
	}
	return;
}

入隊

注意：

入隊開辟新結點并初始化
尾插考慮空佇列的情況

參考代碼：

//入佇列
void QueuePush(Queue* pq, QDataType x)
{
	//避免傳入引數錯誤
	assert(pq);
	//創建結點并初始化
	QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
	newnode->data = x;
	newnode->next = NULL;
	//放入隊尾
	if (pq->head == NULL)//為空堆疊的特殊情況
	{
		pq->head = pq->tail = newnode;
	}
	else
	{
		pq->tail->next = newnode;//尾插
		pq->tail = newnode;//記錄新尾節點
	}
	return;
}

出隊

注意：

空佇列無法再進行出隊
出隊需要對出隊結點釋放并更新頭指標位置

參考代碼：

//出佇列
void QueuePop(Queue* pq)
{
	//避免傳入引數錯誤
	assert(pq);
	//為空佇列無法出佇列
	assert(!QueueEmpty(pq));
	//保存下一個結點
	QueueNode* next = pq->head->next;
	//釋放佇列頭
	free(pq->head);
	//隊頭更新
	pq->head = next;
	return;
}

佇列頭結點資料

注意：

空佇列沒有資料

參考代碼：

//佇列頭結點資料
QDataType QueueFront(Queue* pq)
{
	//避免傳入引數錯誤
	assert(pq);
	//為空佇列沒有資料
	assert(!QueueEmpty(pq));

	return pq->head->data;
}

佇列尾結點資料

注意：

空佇列沒有資料

參考代碼：

//佇列尾節點資料
QDataType QueueBack(Queue* pq)
{
	//避免傳入引數錯誤
	assert(pq);
	//為空佇列沒有資料
	assert(!QueueEmpty(pq));

	return pq->tail->data;
}

佇列存入資料個數

參考代碼：

//佇列存入資料個數
int QueueSize(Queue* pq)
{
	//避免傳入引數錯誤
	assert(pq);
	int size = 0;
	//遍歷佇列
	QueueNode* cur = pq->head;
	while (cur)
	{
		size++;
		cur = cur->next;
	}
	return size;
}

判斷空佇列

注：同樣的對于C語言使用布爾型別需要包含<stdbool.h>頭檔案

參考代碼：

//判斷空佇列
bool QueueEmpty(Queue* pq)
{
	//避免傳入引數錯誤
	assert(pq);

	return pq->head == NULL;
}

佇列測驗

測驗代碼：

void test()
{
	Queue q;
	QueueInit(&q);
	QueuePush(&q, 1);
	QueuePush(&q, 2);
	QDataType front = QueueFront(&q);
	printf("%d ", front);
	QueuePop(&q);

	QueuePush(&q, 3);
	QueuePush(&q, 4);

	while (!QueueEmpty(&q))
	{
		QDataType front = QueueFront(&q);
		printf("%d ", front);
		QueuePop(&q);
	}
	printf("\n");
}

結果示圖：

對上述內容有什么問題記得留言呦~可以的話記得留下你的三連哈！~

轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/344306.html

標籤：其他

上一篇：Matlab+Qt開發筆記（一）：matlab搭建Qt開發matlib環境以及Demo測驗

下一篇：演算法開啟小碼農佇列血脈

開卷資料結構~堆疊和佇列詳解

前言

堆疊

堆疊的實作

介面展示

堆疊結構創建

堆疊的初始化

堆疊的銷毀

入堆疊

出堆疊

空堆疊判斷

堆疊頂資料獲取

堆疊存入資料個數

堆疊測驗

佇列

佇列的實作

介面展示

佇列型別創建

佇列初始化

佇列銷毀

入隊

出隊

佇列頭結點資料

佇列尾結點資料

佇列存入資料個數

判斷空佇列

佇列測驗