C語言分別實(shí)現(xiàn)棧和隊(duì)列詳解流程

更新時(shí)間：2022年04月23日 11:36:45 作者：風(fēng)＆646

棧和隊(duì)列，嚴(yán)格意義上來說，也屬于線性表，因?yàn)樗鼈円捕加糜诖鎯?chǔ)邏輯關(guān)系為 "一對(duì)一" 的數(shù)據(jù)，但由于它們比較特殊，因此將其單獨(dú)作為一章，做重點(diǎn)講解

什么是棧

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

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

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

棧的結(jié)構(gòu)圖示

棧的實(shí)現(xiàn)

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

創(chuàng)建棧的結(jié)構(gòu)體

我們用棧來存儲(chǔ)數(shù)據(jù)，首先需要實(shí)現(xiàn)一個(gè)動(dòng)態(tài)增長(zhǎng)的棧。所以我們先創(chuàng)建一個(gè)棧的結(jié)構(gòu)體。

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

初始化棧

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

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

入棧

一開始top為0標(biāo)識(shí)棧頂?shù)奈恢?，所以我們要先將?shù)據(jù)放入棧頂，在讓top向后走一位。

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

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

出棧

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

獲取棧頂元素

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

獲取棧中有效元素個(gè)數(shù)

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

檢測(cè)棧是否為空

檢測(cè)棧是否為空，如果為空返回非零結(jié)果，如果不為空則返回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;
}

什么是隊(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í)現(xiàn)

隊(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ì)比較低。

創(chuàng)建隊(duì)列結(jié)構(gòu)體

我們使用鏈表來實(shí)現(xiàn)隊(duì)列，我們需要?jiǎng)?chuàng)建一個(gè)存儲(chǔ)隊(duì)列信息的結(jié)構(gòu)體。

typedef int QDataType;
//鏈?zhǔn)浇Y(jié)構(gòu)：表示隊(duì)列
typedef struct QueueNode
{
	QDataType data;           //存儲(chǔ)數(shù)據(jù)
	struct QueueNode* next;   //指針域
}QNode;
//隊(duì)列的結(jié)構(gòu)
typedef struct Queue
{
	QNode* head;//標(biāo)識(shí)隊(duì)頭的位置
	QNode* tail;//標(biāo)識(shí)隊(duì)尾的位置
}Queue;

初始化隊(duì)列

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

隊(duì)尾入隊(duì)列

讓一個(gè)數(shù)據(jù)進(jìn)入隊(duì)列，我們只需要用鏈表結(jié)構(gòu)來實(shí)現(xiàn)隊(duì)列，在隊(duì)尾進(jìn)行尾插數(shù)據(jù)就可以了。

如果隊(duì)列為空，需要單獨(dú)處理一下。

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

隊(duì)頭出隊(duì)列

當(dāng)隊(duì)列為空，沒有存儲(chǔ)數(shù)據(jù)時(shí)，我們就不能夠出數(shù)據(jù)。如果隊(duì)列中只有一個(gè)結(jié)點(diǎn)，那么我們需要對(duì)其單獨(dú)處理，否則就會(huì)出現(xiàn)錯(cuò)誤。

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

獲取隊(duì)列頭部元素

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

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

獲取隊(duì)列尾部元素

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

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

獲取隊(duì)列中元素個(gè)數(shù)

可以對(duì)隊(duì)列進(jìn)行遍歷，統(tǒng)計(jì)元素個(gè)數(shù)，如果隊(duì)列比較長(zhǎng)那么這個(gè)方法效率就比較低。如果想要效率比較高，那么我們可以在定義隊(duì)列結(jié)構(gòu)體的時(shí)候加上一個(gè)size變量，每往隊(duì)列里面入一個(gè)數(shù)據(jù)就統(tǒng)計(jì)一下，那么我們需要隊(duì)列中元素個(gè)數(shù)的時(shí)候就可以直接返回。

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

檢測(cè)隊(duì)列是否為空

檢測(cè)隊(duì)列是否為空，如果為空返回非零結(jié)果，如果非空返回0

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

銷毀隊(duì)列

在使用完隊(duì)列之后，我們應(yīng)該對(duì)其進(jìn)行銷毀，防止造成內(nèi)存泄漏。

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

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

您可能感興趣的文章: