快捷導(dǎo)航

C語言簡明講解隊(duì)列的實(shí)現(xiàn)方法

更新時(shí)間：2022年04月22日 10:55:06 作者：平凡的人1

隊(duì)列（Queue）與棧一樣，是一種線性存儲(chǔ)結(jié)構(gòu)，它具有如下特點(diǎn)：隊(duì)列中的數(shù)據(jù)元素遵循“先進(jìn)先出”（First?In?First?Out）的原則，簡稱FIFO結(jié)構(gòu)。在隊(duì)尾添加元素，在隊(duì)頭刪除元素

前言

大家好啊，我又雙叒叕來水博客了，道路是曲折的，前途是光明的，事物是呈螺旋式上升的，事物最終的發(fā)展結(jié)果還是我們多多少少能夠決定的，好啦，吹水結(jié)束，這與這篇博客的主題并沒有太多聯(lián)系。關(guān)于棧和隊(duì)列這一板塊本來是想不寫（就是想偷懶），但是想了想，覺得這樣不太好，關(guān)于數(shù)據(jù)結(jié)構(gòu)這一塊可能會(huì)有缺失，所以最終還是決定寫，必須補(bǔ)齊這一塊，恰好最近有時(shí)間寫博客，所以還是寫了，這篇博客將介紹隊(duì)列的知識(shí)點(diǎn)，理解鏈表那一塊的操作后，棧和隊(duì)列的相關(guān)操作還是比較容易去理解的。

隊(duì)列的表示和實(shí)現(xiàn)

隊(duì)列的概念及結(jié)構(gòu)

隊(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ì)頭

敲黑板，開始摸魚：

其實(shí)也沒什么重點(diǎn)啦，都是一些基本的概念性東西，主要有：

1.要理解FIFO代表的意思

2.什么是隊(duì)尾隊(duì)頭，別弄混了

隊(duì)列的實(shí)現(xiàn)有兩種方法：

數(shù)組：不適合，隊(duì)頭出數(shù)據(jù)需要挪動(dòng)數(shù)據(jù)，一般還會(huì)出現(xiàn)假溢出，循環(huán)隊(duì)列啥的

鏈表：單鏈表較合適，頭刪尾插，效率較高

當(dāng)然，并不是說一定要用哪種，由于課本是以數(shù)組為例，這里以單鏈表為例

代碼實(shí)現(xiàn)

還是老樣子，分為三部分，直接上手代碼，來，跟著我一起敲

Queue.h

#pragma once
#include <stdio.h>
#include <stdbool.h>
#include <assert.h>
#include <stdlib.h>
typedef int QDataType;
typedef struct QueueNode
{
	struct QueueNode* next;
	QDataType data;
}QNode;
 typedef struct Queue
{
	QNode* head;
	QNode* tail;
}Queue;
 //初始化
 void QueueInit(Queue* pq);
 //銷毀
 void QueueDestory(Queue* pq);
 //隊(duì)尾入
 void QueuePush(Queue* pq, QDataType x);
 //隊(duì)頭出
 void QueuePop(Queue* pq);
 //取隊(duì)頭數(shù)據(jù)
 QDataType QueueFront(Queue* pq);
 //取隊(duì)尾數(shù)據(jù)
 QDataType QueuBack(Queue* pq);
 //個(gè)數(shù)
 int QueueSize(Queue* pq);
 //判斷是否為空
 bool QueueEmpty(Queue* pq);

Queue.c

#include "Queue.h"
void QueueInit(Queue* pq)
{
	assert(pq);
	pq->head = pq->tail = 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;
}
//隊(duì)尾入
void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	if (pq->tail == NULL)
	{
		pq->head = pq->tail = newnode;
	}
	else
	{
		pq->tail->next = newnode;
		pq->tail = newnode;
	}
}
//隊(duì)頭出
void QueuePop(Queue* pq)
{
	assert(pq);
	assert(pq->head);
	//1.一個(gè)（防止野指針）
	//2.多個(gè)
	if (pq->head->next == NULL)
	{
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	else
	{
		QNode* next = pq->head->next;
		free(pq->head);
		pq->head = next;
	}
}
QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(pq->head);
	return pq->head->data;
}
QDataType QueuBack(Queue* pq)
{
	assert(pq);
	assert(pq->head);
	return pq->tail->data;
}
int QueueSize(Queue* pq)
{
	assert(pq);
	int size = 0;
	QNode* cur = pq->head;
	while (cur)
	{
		++size;
		cur = cur->next;
	}
	return size;
}
bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->head == NULL;
}

Test.c

#include "Queue.h"
void TestQueue()
{
	Queue q;
	QueueInit(&q);
	QueuePush(&q, 1);
	QueuePush(&q, 2);
	printf("%d ", QueueFront(&q));
	QueuePop(&q);
	QueuePush(&q, 3);
	QueuePush(&q, 4);
	while (!QueueEmpty(&q))
	{
		printf("%d ", QueueFront(&q));
		QueuePop(&q);
	}
	printf("\n");
	QueueDestory(&q);
}
int main()
{
	TestQueue();
	return 0;
}