郑州个人网站开发,中国产品网免费网站,松江品划做网站公司,中小企业库队列 前言一、队列1.1队列的概念及结构1.2队列的实现1.3队列的实现1.4扩展 二、队列面试题三、队列的具体实现代码Queue.hQueue.ctest.c队列的初始化队列的销毁入队列出队列返回队头元素返回队尾元素检测队列是否为空检测元素个数 前言
队列是一种特殊的线性数据结构#xff… 队列 前言一、队列1.1队列的概念及结构1.2队列的实现1.3队列的实现1.4扩展 二、队列面试题三、队列的具体实现代码Queue.hQueue.ctest.c队列的初始化队列的销毁入队列出队列返回队头元素返回队尾元素检测队列是否为空检测元素个数 前言
队列是一种特殊的线性数据结构遵循先入先出FIFO的原则。它只允许在队列的末尾添加元素称为入队操作并从队列的开头移除元素称为出队操作。队列在多种应用中发挥着重要作用如计算机系统的任务调度、打印机作业管理以及多线程编程中的线程同步等。 一、队列
1.1队列的概念及结构
队列只允许在一端进行插入数据操作在另一端进行删除数据操作的特殊线性表队列具有先进先出FIFO(First In First Out)
入队列进行插入操作的一端称为队尾
出队列进行删除操作的一端称为队头
1.2队列的实现
队列也可以数组和链表的结构实现使用链表的结构实现更优一些因为如果使用数组的结构出队列在数组头上出数据效率会比较低。
1.3队列的实现
// 链式结构表示队列
typedef struct QListNode
{ struct QListNode* _pNext; QDataType _data;
}QNode; // 队列的结构
typedef struct Queue
{ QNode* _front; QNode* _rear;
}Queue; // 初始化队列
void QueueInit(Queue* q);
// 队尾入队列
void QueuePush(Queue* q, QDataType data);
// 队头出队列
void QueuePop(Queue* q);
// 获取队列头部元素
QDataType QueueFront(Queue* q);
// 获取队列队尾元素
QDataType QueueBack(Queue* q);
// 获取队列中有效元素个数
int QueueSize(Queue* q);
// 检测队列是否为空如果为空返回非零结果如果非空返回0
int QueueEmpty(Queue* q);
// 销毁队列
void QueueDestroy(Queue* q);1.4扩展
另外扩展了解一下实际中我们有时还会使用一种队列叫循环队列。如操作系统课程讲解生产者消费者模型 时可以就会使用循环队列。环形队列可以使用数组实现也可以使用循环链表实现。 二、队列面试题 用队列实现栈 用栈实现队列 设计循环队列 循环队列的存储空间为 Q(1:100) 初始状态为 frontrear100 。经过一系列正常的入队与退队操作后frontrear99 则循环队列中的元素个数为 A 、1 B 、2 C 、99 D、 0或者100 以下( )不是队列的基本运算 A 、从队尾插入一个新元素 B、 从队列中删除第i个元素 C、 判断一个队列是否为空 D、 读取队头元素的值 现有一循环队列其队头指针为front队尾指针为rear循环队列长度为N。其队内有效长度为(假设 队头不存放数据) A 、(rear - front N) % N 1 B 、(rear - front N) % N C 、(rear - front) % (N 1) D 、(rear - front N) % (N - 1)
答案DBB
三、队列的具体实现代码
Queue.h
#pragma once
#include stdio.h
#include stdlib.h
#include assert.h
#include stdbool.htypedef int QDatatype;
typedef struct QueueNode
{QDatatype val;struct QueueNode* next;
}QNode;typedef struct Queue
{QNode* phead;QNode* ptail;int size;
}Queue;
//队列的初始化
void QueueInit(Queue* pq);
//队列的销毁
void QueueDestroy(Queue* pq);//入队列
void QueuePush(Queue* pq, QDatatype x);
//出队列
void QueuePop(Queue* pq);//队头元素
QDatatype QueueFront(Queue* pq);
//队尾元素
QDatatype QueueBack(Queue* pq);//检测是否为空
bool QueueEmpty(Queue* pq);//检测元素个数
int QueueSize(Queue* pq);
Queue.c
#include Queue.h
void QueueInit(Queue* pq)
{assert(pq);pq-phead NULL;pq-ptail NULL;pq-size 0;
}
void QueueDestroy(Queue* pq)
{assert(pq);QNode* cur pq-phead;while (cur){QNode* next cur-next;free(cur);cur next;}pq-phead NULL;pq-ptail NULL;pq-size 0;
}
void QueuePush(Queue* pq, QDatatype x)
{assert(pq);QNode* newnode (QNode*)malloc(sizeof(QNode));if (newnode NULL){perror(newnode malloc :);return;}newnode-val x;newnode-next NULL;if (pq-ptail){pq-ptail-next newnode;pq-ptail newnode;}else{pq-phead pq-ptail newnode;}pq-size;
}
bool QueueEmpty(Queue* pq)
{assert(pq);return pq-size 0;
}
void QueuePop(Queue* pq)
{assert(pq);//assert(!QueueEmpty(pq));assert(pq-phead ! NULL);if (pq-phead-next NULL){free(pq-phead);pq-phead pq-ptail NULL;}else{QNode* next pq-phead-next;free(pq-phead);pq-phead next;}pq-size--;
}
QDatatype QueueFront(Queue* pq)
{assert(pq);assert(pq-phead ! NULL);return pq-phead-val;
}
QDatatype QueueBack(Queue* pq)
{assert(pq);assert(pq-ptail ! NULL);return pq-ptail-val;
}
int QueueSize(Queue* pq)
{assert(pq);return pq-size;
}test.c
#includeQueue.hint main()
{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);}QueueDestroy(q);return 0;
}队列的初始化
//队列的初始化
void QueueInit(Queue* pq);void QueueInit(Queue* pq)
{assert(pq);pq-phead NULL;pq-ptail NULL;pq-size 0;
}队列的初始化是数据结构学习中不可或缺的一步它标志着队列这一特定数据存储形式的诞生。队列又称先进先出FIFO的数据结构允许我们在一端通常是队尾添加元素而在另一端通常是队头移除元素。这种特性使得队列在多种应用场景中发挥着重要作用如操作系统中的任务调度、网络中的缓冲管理等。
在初始化队列时我们首先需要分配一定的存储空间来存放队列元素。这个存储空间可以是数组、链表或其他适合的数据结构。初始化过程中我们还需设置两个指针分别指向队头和队尾以便进行元素的添加和移除操作。
完成初始化后队列就处于空状态即没有元素可供处理。此时任何尝试从队列中移除元素的操作都会失败因为队列是空的。然而可以向队列中添加元素这些元素将按照添加的顺序依次排列。
随着元素的不断加入队尾指针会向后移动指向队列中最后一个元素。当需要从队列中移除元素时队头指针会向前移动指向下一个待处理的元素。这种指针的移动保证了队列的先进先出特性即最早加入队列的元素将最先被移除。
除了基本的添加和移除操作外队列还支持其他一些有用的操作如检查队列是否为空、判断队列是否已满等。这些操作使得队列在实际应用中更加灵活和高效。
总之队列的初始化是队列生命周期的开始它为队列的后续操作提供了基础。通过对队列的合理初始化和管理我们可以有效地处理各种需要先进先出处理顺序的场景提高程序的效率和稳定性。
队列的销毁
//队列的销毁
void QueueDestroy(Queue* pq);void QueueDestroy(Queue* pq)
{assert(pq);QNode* cur pq-phead;while (cur){QNode* next cur-next;free(cur);cur next;}pq-phead NULL;pq-ptail NULL;pq-size 0;
}队列的销毁涉及清除所有队列元素并释放队列占用的内存空间确保资源得到正确回收。这通常涉及遍历队列逐个删除元素并解除队列与其他数据结构或资源的关联。销毁队列后其不再可用需重新创建才能使用。
入队列
//入队列
void QueuePush(Queue* pq, QDatatype x);void QueuePush(Queue* pq, QDatatype x)
{assert(pq);QNode* newnode (QNode*)malloc(sizeof(QNode));if (newnode NULL){perror(newnode malloc :);return;}newnode-val x;newnode-next NULL;if (pq-ptail){pq-ptail-next newnode;pq-ptail newnode;}else{pq-phead pq-ptail newnode;}pq-size;
}入队列Enqueue是队列操作的一种指的是将一个元素添加到队列的尾部。在队列这种先进先出FIFO的数据结构中新添加的元素将排在所有已有元素的后面等待被处理或移除。入队列操作不会改变队列中已有元素的顺序保证了队列的先进先出特性。在实际应用中入队列常用于实现缓冲、任务调度、消息传递等场景。
出队列
//出队列
void QueuePop(Queue* pq);void QueuePop(Queue* pq)
{assert(pq);//assert(!QueueEmpty(pq));assert(pq-phead ! NULL);if (pq-phead-next NULL){free(pq-phead);pq-phead pq-ptail NULL;}else{QNode* next pq-phead-next;free(pq-phead);pq-phead next;}pq-size--;
}出队列是指从队列中移除并返回队列头部的元素通常用于实现先进先出FIFO的数据结构。在出队列操作中队列头部元素被移除并返回队列中的其他元素则向前移动一位。出队列操作的时间复杂度通常为O(1)因为它只涉及到对队列头部元素的移除和返回不需要遍历整个队列。在实际应用中出队列操作常用于缓存管理、任务调度、网络流量控制等场景。
返回队头元素
//队头元素
QDatatype QueueFront(Queue* pq);QDatatype QueueFront(Queue* pq)
{assert(pq);assert(pq-phead ! NULL);return pq-phead-val;
}队列是一种特殊的线性表只允许在表的前端front进行删除操作而在表的后端rear进行插入操作。队列具有先进先出FIFO的特性。
返回队头元素是对队列进行的一种操作即获取队列前端队头的元素但并不从队列中删除该元素。这通常用于查看队列中的第一个元素但不改变队列的状态。
返回队尾元素
//队尾元素
QDatatype QueueBack(Queue* pq);QDatatype QueueBack(Queue* pq)
{assert(pq);assert(pq-ptail ! NULL);return pq-ptail-val;
}检测队列是否为空
//检测是否为空
bool QueueEmpty(Queue* pq);bool QueueEmpty(Queue* pq)
{assert(pq);return pq-size 0;
}检测队列是否为空可以通过检查队列的头部和尾部指针或索引来实现。如果头部和尾部指针或索引相同说明队列为空否则队列不为空。此外也可以使用队列提供的相关函数或方法如isEmpty()等来检测队列是否为空。在实际应用中检测队列是否为空是常见的操作常用于控制程序的流程。
在C语言中没有相关的库函数检验是否为空在c中会有相关的数据结构的库
检测元素个数
//检测元素个数
int QueueSize(Queue* pq);int QueueSize(Queue* pq)
{assert(pq);return pq-size;
}
