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

學無先后，達者為師

網站首頁 編程語言 正文

C語言分別實現棧和隊列詳解流程_C 語言

作者：風＆646 ? 更新時間： 2022-06-21 編程語言

什么是棧

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

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

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

棧的結構圖示

棧的實現

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

創建棧的結構體

我們用棧來存儲數據，首先需要實現一個動態增長的棧。所以我們先創建一個棧的結構體。

typedef int STDataType;
typedef struct Stack
{
	STDataType* a;  
	int top;       //棧頂
	int capacity;  //容量
}Stack;

初始化棧

初始化棧的方式有很多種，我們可以根據不同的需求來選擇。這里寫一種常規的。

void StackInit(Stack* ps)
{
	assert(ps);//檢測傳過來的ps是否為空
	ps->a = NULL;//把a標識的這塊空間先置為空
	ps->top = ps->capacity = 0;
}

入棧

一開始top為0標識棧頂的位置，所以我們要先將數據放入棧頂，在讓top向后走一位。

void StackPush(Stack* ps, STDataType x)
{
	assert(ps);//檢測ps是否為空

	//如果空間滿了，我們需要擴容
	if (ps->capacity == ps->top)//判斷空間是否滿了的條件
	{
		int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;//指定新空間的大小
		ps->a = (STDataType*)realloc(ps->a, newCapacity*sizeof(STDataType));//進行擴容
		if (ps->a == NULL)//擴容失敗
		{
			printf("realloc fail\n");
			exit(-1);//終止程序
		}
		ps->capacity = newCapacity;//讓其標識新的空間的大小
	}
	ps->a[ps->top] = x;//將數據放入棧
	ps->top++;//top向后走一步
}

出棧

void StackPop(Stack* ps)
{
	assert(ps);
	if (ps->top > 0)//避免棧里面數據已經刪除完了，top依舊向下減為負數
	{
		--ps->top;
	}
}

獲取棧頂元素

STDataType StackTop(Stack* ps)
{
	assert(ps);
	assert(ps->top > 0);//保證下標為正
	return ps->a[ps->top - 1];//返回棧頂元素
}

獲取棧中有效元素個數

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

檢測棧是否為空

檢測棧是否為空，如果為空返回非零結果，如果不為空則返回0.

bool StackEmpty(Stack* ps)
{
	assert(ps);
	return ps->top == 0;//如果條件成立就返回真，否則就為假（不為空）
}

棧的銷毀

void StackDestroy(Stack* ps)
{
	assert(ps);
	free(ps->a);//釋放開辟的這一塊空間
	ps->a = NULL;
	ps->top = ps->capacity = 0;
}

什么是隊列？

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

隊列的實現

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

創建隊列結構體

我們使用鏈表來實現隊列，我們需要創建一個存儲隊列信息的結構體。

typedef int QDataType;
//鏈式結構：表示隊列
typedef struct QueueNode
{
	QDataType data;           //存儲數據
	struct QueueNode* next;   //指針域
}QNode;
//隊列的結構
typedef struct Queue
{
	QNode* head;//標識隊頭的位置
	QNode* tail;//標識隊尾的位置
}Queue;

初始化隊列

void QueueInit(Queue* pq)
{
	assert(pq);
	pq->head = pq->tail = NULL;//將兩個指針置為空
}

隊尾入隊列

讓一個數據進入隊列，我們只需要用鏈表結構來實現隊列，在隊尾進行尾插數據就可以了。

如果隊列為空，需要單獨處理一下。

void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));//申請一個新的結點
	assert(newnode);//檢測結點是否申請成功
	newnode->data = x;//
	newnode->next = NULL;
	if (pq->tail == NULL)//如果隊列為空的情況
	{
		assert(pq->head==NULL);
		pq->tail = pq->head = newnode;
	}
	else//隊列不為空的情況
	{
		pq->tail->next = newnode;//尾插一個新結點
		pq->tail = newnode;//更新尾的位置
	}
}

隊頭出隊列

當隊列為空，沒有存儲數據時，我們就不能夠出數據。如果隊列中只有一個結點，那么我們需要對其單獨處理，否則就會出現錯誤。

void QueuePop(Queue* pq)
{
	assert(pq);
	assert(pq->head && pq->tail);//保證隊列中有數據在往下走
	if (pq->head->next == NULL)//如果隊列里面只有一個數據的情況
	{
		free(pq->head);//釋放隊頭數據
		pq->head = pq->tail = NULL;//將隊列的頭指針和尾指針均置為空
	}
	else
	{
		QNode* next = pq->head->next;//讓next指向隊頭結點的下一個結點
		free(pq->head);//釋放隊頭結點
		pq->head = next;//讓head指向next結點
	}
}

獲取隊列頭部元素

檢測隊列是否為空，如果不為空則直接返回隊列頭指針指向的元素。

QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(pq->head);//檢測隊列是否為空
	return pq->head->data;//返回隊列頭部元素
}

獲取隊列尾部元素

檢測隊列是否為空，如果不為空則直接返回隊列尾指針指向的元素。

//獲取隊列隊尾元素
QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(pq->tail);//檢測隊列是否為空
	return pq->tail->data;//返回隊列尾部元素
}

獲取隊列中元素個數

可以對隊列進行遍歷，統計元素個數，如果隊列比較長那么這個方法效率就比較低。如果想要效率比較高，那么我們可以在定義隊列結構體的時候加上一個size變量，每往隊列里面入一個數據就統計一下，那么我們需要隊列中元素個數的時候就可以直接返回。

int QueueSize(Queue* pq)
{
	assert(pq);
	QNode* cur = pq->head;//讓cur指向隊頭的元素
	size_t size = 0;//定義一個無符號的size變量用來計數
	while (cur)//cur不為空則進入循環繼續執行
	{
		size++;//size=size+1
		cur = cur->next;//繼續向后遍歷
	}
	return size;//返回有效元素個數
}

檢測隊列是否為空

檢測隊列是否為空，如果為空返回非零結果，如果非空返回0

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

銷毀隊列

在使用完隊列之后，我們應該對其進行銷毀，防止造成內存泄漏。

void QueueDestroy(Queue* pq)
{
	assert(pq);
	QNode* cur = pq->head;
	while (cur)
	{
		QNode* next = cur->next;//定義一個next指向cur的下一個結點
		free(cur);//釋放cur
		cur = next;
	}
	pq->head = pq->tail = NULL;//將頭尾指針均置為空
}

?

原文鏈接：https://blog.csdn.net/qq_61939403/article/details/123894799

欄目分類
最近更新