队列(Queue)C语言实现 详解
程序员文章站
2024-03-18 12:39:04
...
前言
你们在用电脑时有没有经历,机器有时会处于疑似死机的状态,鼠标点什么似乎都没用,双击任何快捷方式都不动弹。就当你失去耐心,打算rest时。突然他像酒醒了一样,把你刚才点击的所有操作全部按顺序执行一遍。这其实是因为操作系统中的多个程序因需要通过一个通道输出,而按先后次序排队等待造成的。这里应用了一种数据结构来实现刚才提到的先进先出的排队功能,这就是队列。本文就对算法中的队列进行简单的总结,仅供参考使用。错漏之处,请不吝指正。
一、队列的概念及结构
队列是一种特殊的线性表,特殊之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作。进行插入操作的端称为队尾,进行删除操作的端称为队头。
队列的数据元素又称为队列元素。在队列中插入一个队列元素称为入队,从队列中删除一个队列元素称为出队。因为队列只允许在一端插入,在另一端删除,所以只有最早进入队列的元素才能最先从队列中删除,故队列又称为先进先出(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以此入队然后再打印,结果如下:
总结
队列的作用:
- 先进先出场景,比如要保持序列公平,排队抽好机。
- 广度优先遍历。
以上就是今天要讲的内容,本文仅仅简单介绍了队列的实现。使用队列存储数据,讲究 “先进先出”,即最先进队列的数据,也最先出队列。使用栈结构存储数据,讲究“先进后出”,即最先进栈的数据,最后出栈;不足之处我会多多改进。想了解栈的可以看这篇文章(栈(Stack)C语言实现 详解)。