C語言怎么實現(xiàn)棧和隊列

本文小編為大家詳細(xì)介紹“C語言怎么實現(xiàn)棧和隊列”，內(nèi)容詳細(xì)，步驟清晰，細(xì)節(jié)處理妥當(dāng)，希望這篇“C語言怎么實現(xiàn)棧和隊列”文章能幫助大家解決疑惑，下面跟著小編的思路慢慢深入，一起來學(xué)習(xí)新知識吧。

什么是棧

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

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

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

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

棧的實現(xiàn)

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

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

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

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

初始化棧

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

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

入棧

一開始top為0標(biāo)識棧頂?shù)奈恢茫晕覀円葘?shù)據(jù)放入棧頂，在讓top向后走一位。

void StackPush(Stack* ps, STDataType x)
{
	assert(ps);//檢測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)識新的空間的大小
	}
	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];//返回棧頂元素
}

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

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

檢測棧是否為空

檢測棧是否為空，如果為空返回非零結(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;
}

什么是隊列？

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

隊列的實現(xiàn)

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

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

我們使用鏈表來實現(xiàn)隊列，我們需要創(chuàng)建一個存儲隊列信息的結(jié)構(gòu)體。

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

初始化隊列

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

隊尾入隊列

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

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

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

隊頭出隊列

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

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

獲取隊列頭部元素

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

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;//返回隊列尾部元素
}

獲取隊列中元素個數(shù)

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

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

檢測隊列是否為空

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

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

銷毀隊列

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

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

讀到這里，這篇“C語言怎么實現(xiàn)棧和隊列”文章已經(jīng)介紹完畢，想要掌握這篇文章的知識點還需要大家自己動手實踐使用過才能領(lǐng)會，如果想了解更多相關(guān)內(nèi)容的文章，歡迎關(guān)注億速云行業(yè)資訊頻道。