欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

队列(Queue)C语言实现 详解

程序员文章站 2024-03-18 12:39:04
...


前言

你们在用电脑时有没有经历,机器有时会处于疑似死机的状态,鼠标点什么似乎都没用,双击任何快捷方式都不动弹。就当你失去耐心,打算rest时。突然他像酒醒了一样,把你刚才点击的所有操作全部按顺序执行一遍。这其实是因为操作系统中的多个程序因需要通过一个通道输出,而按先后次序排队等待造成的。这里应用了一种数据结构来实现刚才提到的先进先出的排队功能,这就是队列。本文就对算法中的队列进行简单的总结,仅供参考使用。错漏之处,请不吝指正。


一、队列的概念及结构

队列是一种特殊的线性表,特殊之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作。进行插入操作的端称为队尾,进行删除操作的端称为队头。
队列(Queue)C语言实现 详解
队列的数据元素又称为队列元素。在队列中插入一个队列元素称为入队,从队列中删除一个队列元素称为出队。因为队列只允许在一端插入,在另一端删除,所以只有最早进入队列的元素才能最先从队列中删除,故队列又称为先进先出(FIFO—first in first out)线性表。

二、实现队列

1.实现队列建议用什么结构?

数组可以在一头增添数据很方便,但是在另一头删除数据整个数组中的元素都要挪动,效率很低。所以建议用单链表来实现栈。

2.接口的设计

代码如下(示例):

typedef int QDataType;

typedef struct QueueNode
{
	QDataType _data;		//用来存储数据
	struct QueueNode* _next;//用来指向下一个结构体
}QueueNode;

typedef struct Queue
{
	QueueNode* _head; //存放整个队列的队头
	QueueNode* _tail; //存放整个队列的队尾
}Queue;

//初始化
void QueueInit(Queue* pq);

//销毁
void QueueDestory(Queue* pq);

//入队
void QueuePush(Queue* pq, QDataType x);

//出队
void QueuePop(Queue* pq);

//访问队首的元素
QDataType QueueFront(Queue* pq);

//访问对尾的元素
QDataType QueueBack(Queue* pq);

//返回1是空,返回0是非空
int QueueEmpty(Queue* pq);

//获取数据的个数
int QueueSize(Queue* pq);

3.接口的实现

代码如下(示例):


//初始化
void QueueInit(Queue* pq)
{
	assert(pq);					 //判断指针的有效性
	pq->_head = pq->_tail = NULL;//队头和队尾指向空指针
}
//销毁
void QueueDestory(Queue* pq)
{
	assert(pq);
	QueueNode* cur = pq->_head;
	while (cur)
	{
		QueueNode* next = cur->_next;
		free(cur);
		cur = next;
	}
	pq->_head = pq->_tail = NULL;
}
//入队
void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));//为新节点申请内存空间
	if (newnode == NULL)//判断内存空间是否申请成功
	{
		printf("内存不足!\n");
		exit(-1);
	}
	newnode->_data = x;   //新节点储存数据
	newnode->_next = NULL;//新节点的下一个指向NULL,即新节点作为队尾
	if (pq->_head == NULL)//将新节点入队
	{
		pq->_head = pq->_tail = newnode;
	}
	else
	{
		pq->_tail->_next = newnode;
		pq->_tail = newnode;
	}
}
//出队
void QueuePop(Queue* pq)
{
	assert(pq);
	assert(pq->_head);
	QueueNode* next = pq->_head->_next;
	free(pq->_head);
	pq->_head = next;
	if (pq->_head == NULL)
	{
		pq->_tail = NULL;
	}
}
//访问队首的元素
QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(pq->_head);
	return pq->_head->_data;
}
//访问队尾的元素
QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(pq->_head);
	return pq->_head->_data;
}
//返回1是空,返回0是非空
int QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->_head == NULL ? 1 : 0;
}
获取数据的个数
int QueueSize(Queue* pq)
{
	assert(pq);
	QueueNode* cur = pq->_head;
	int size = 0;
	while (cur)
	{
		++size;
		cur = cur->_next;
	}
	return size;
}

三、测试数据

根据不同的需求调用不用的函数:
代码如下(示例):

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

将1,2,3,4以此入队然后再打印,结果如下:
队列(Queue)C语言实现 详解

总结

队列的作用:

  • 先进先出场景,比如要保持序列公平,排队抽好机。
  • 广度优先遍历。
    以上就是今天要讲的内容,本文仅仅简单介绍了队列的实现。使用队列存储数据,讲究 “先进先出”,即最先进队列的数据,也最先出队列。使用栈结构存储数据,讲究“先进后出”,即最先进栈的数据,最后出栈;不足之处我会多多改进。想了解栈的可以看这篇文章(栈(Stack)C语言实现 详解)
相关标签: 笔记 算法