本期带大家一起用C语言实现队列🌈🌈🌈
1、队列的概念
队列是一种线性数据结构,它按照先进先出(FIFO)的原则进行操作。可以把队列想象成排队买票或者排队上公交车的队伍。
顺序队列
由一个连续的内存区域组成,可以存储多个元素。队列有两个指针,分别指向队头(Front)和队尾(Rear)。链式队列
由一系列节点构成,每个节点包含存储的元素值和指向下一个节点的指针
队列的基本操作包括:
- 入队(Enqueue):将新元素插入到队尾,如果队列已满则无法插入。
- 出队(Dequeue):移除队头元素,并返回该元素,如果队列为空则无法执行。
- 获取队头元素(Front):获取队头元素的值,但不对队列进行修改。
- 判断队列是否为空(isEmpty):判断队列中是否没有任何元素。
- 判断队列是否已满(isFull):判断队列是否已经达到了最大容量。
队列的操作遵循先进先出的原则,即先入队的元素先出队。在队列中,新元素被插入到队列的末尾,而出队操作始终从队列的头部进行。
队列常用于需要顺序处理任务或数据的场景,例如处理请求、消息传递、广度优先搜索等算法实现。此外,队列还可以通过循环队列的方式来实现,使得已经出队的元素可以再次被插入到队列的末尾,有效地利用内存空间。
2、队列的操作流程
3 、队列的结构
队列通常使用数组或链表来实现。以下是两种常见的队列结构:
-
基于数组的队列(
顺序队列
):- 使用一个固定大小的数组来保存队列元素。
- 需要维护队头和队尾的索引,分别指向队列的第一个元素和最后一个元素。
- 入队操作将元素添加到队尾,并更新队尾索引。
- 出队操作将队头元素移除,并更新队头索引。
- 注意,入队操作可能导致队列满(队尾索引达到数组末尾)的情况,需要进行特殊处理。
-
基于链表的队列(
链式队列
):- 使用链表来动态存储队列元素。
- 需要维护队头和队尾节点指针,分别指向队列的第一个节点和最后一个节点。
- 入队操作创建一个新节点,并将其链接到链表末尾,更新队尾指针。
- 出队操作移除队头节点,并更新队头指针。
- 注意,链式队列没有固定的大小限制,可以根据需要动态调整。
无论是基于数组还是链表的队列,其核心思想都是维护队头和队尾指针,并通过头部和尾部的插入和删除操作实现先进先出的特性。根据具体的应用场景和需求,选择适合的队列实现方式
在这里我们使用链表
来实现队列,避免了用数组队列更新队头数据的遍历,时间复杂度低
4、队列的实现
4.1 队列的结构设计
Queue结构体,它表示整个队列。该结构体包含两个指针成员head和tail,分别指向队列的头部节点和尾部节点
QNode的结构体,它表示队列中的节点。该结构体包含一个指向下一个节点的指针next,以及一个数据data
typedef int QDataTYpe;
typedef struct QueueNode
{
struct QueueNode* next;
QDataTYpe data;
}QNode;
typedef struct Queue
{
QNode* head;
QNode* tail;
int size;
}Queue;
4.2 队列的初始化
现在主函数当中创建了一个Queue q
然后传入q的地址,进行初始化
将队列的头部指针和尾部指针设为NULL,并将队列的大小初始化为0
void QueueInit(Queue* pq)
{
pq->head = NULL;
pq->tail = NULL;
pq->size = 0;
}
4.3 入队
在函数内部,首先进行断言assert(pq)
来确保指针pq
不为空。
然后,通过动态内存分配malloc
来创建一个新的节点newnode
,并将其类型转换为QNode*
。
接下来,检查是否成功分配内存,如果分配失败,则输出错误信息并返回。
然后,将新节点的数据成员data
赋值为传入的参数x
,同时将新节点的下一个指针next
设置为NULL,新节点表示当前节点是队列的尾部节点。
接着,根据队列是否为空,有两种情况处理:
- 如果队列为空,即头部指针
head
为NULL,表示当前队列没有任何节点,此时将头部指针和尾部指针都指向新节点newnode
。 - 如果队列不为空,即头部指针
head
不为NULL,表示当前队列已存在节点,此时将队列尾部节点的下一个指针next
指向新节点newnode
,然后将尾部指针tail
更新为新节点newnode
- 最后,将队列的大小
size
加1,表示新增了一个节点。
void QueuePush(Queue* pq,QDataTYpe x)
{
assert(pq);
QNode* newnode = (QNode*)malloc(sizeof(QNode));;
if (newnode == NULL)
{
perror("malloc:fail");
return;
}
newnode->data = x;
newnode->next = NULL;
if (pq->head == NULL)
{
pq->head = pq->tail = newnode;
}
else
{
pq->tail->next = newnode;
pq->tail = newnode;
}
pq->size++;
}
4.4 判断队列是否为空
判断队列是否为空的话,相对来说是比较简单的
有两种判断方法
根据队列的头指针是否为空
判断
根据队列当中的数据个数size
判断
bool QueueEmpty(Queue* pq)
{
return pq->head == NULL;
//return pq->size==0;
}
4.5 出队
出队列的话我们需要先判断当前队列是否为空
队列为空的话那我们就直接返回
队列不为空的话又分两种情况
1、队头指针==队尾指针
2、队头指针!=队尾指针
void QueuePop(Queue* pq)
{
assert(pq);
if (QueueEmpty(pq))
{
printf("队列为空\n");
return;
}
if (pq->head == pq->tail)
{
free(pq->head);
pq->head = NULL;
pq->tail = NULL;
}
else
{
QNode* next = pq->head->next;
free(pq->head);
pq->head = next;
}
pq->size--;
}
4.6 获取队头数据
获取队头数据的话,需要先判断队列是否为空,为空的话就直接返回
队列不为空,返回队头数据
QDataTYpe QueueFront(Queue* pq)
{
assert(pq);
if (QueueEmpty(pq))
{
printf("队列为空\n");
return;
}
else
return pq->head->data;
}
4.7 获取队尾数据
获取队尾数据的话,同样需要判断队列是否为空,为空的话也就直接返回
队列不为空的话,返回队尾数据
QDataTYpe QueueBack(Queue* pq)
{
assert(pq);
if (QueueEmpty(pq))
{
printf("队列为空\n");
return;
}
else
return pq->tail->data;
}
4.8 获取队列当中数据的个数
获取队列数据的个数,直接返回pq->size
int QueueSize(Queue* pq)
{
assert(pq);
return pq->size;
}
4.9 队列的销毁
使用循环遍历队列中的所有节点,直到遍历到最后一个节点,即当前节点为NULL
void QueueDestroy(Queue* pq)
{
assert(pq);
QNode* cur = pq->head;
while (cur != NULL)
{
QNode* next = cur->next;
free(cur);
cur = next;
}
pq->head = NULL;
pq->tail = NULL;
pq->size = 0;
}
5、栈和队列OJ题
5.1 队列模拟栈
使用两个队列来实现栈的重点在于以下几点:
- 始终保持一个队列为空,另一个队列非空。
- 入数据时,将元素入队到不为空的队列中。
- 出数据时,将非空队列中的元素转移到空队列中,直到队列中只剩下一个元素。
- 出队原先非空队列的数据,原先非空队列变为空,即可实现栈的后进先出操作。
通过将元素入队到非空队列、转移到空队列以及出队的操作,可以模拟栈的后进先出特性
typedef int QDataTYpe;
typedef struct QueueNode
{
struct QueueNode* next;
QDataTYpe data;
}QNode;
typedef struct Queue
{
QNode* head;
QNode* tail;
int size;
}Queue;
void QueueInit(Queue* pq);
void QueueDestroy(Queue* pq);
void QueuePush(Queue* pq,QDataTYpe x);
void QueuePop(Queue* pq);
bool QueueEmpty(Queue* pq);
QDataTYpe QueueFront(Queue* pq);
QDataTYpe QueueBack(Queue* pq);
int QueueSize(Queue* pq);
void QueueInit(Queue* pq)
{
pq->head = NULL;
pq->tail = NULL;
pq->size = 0;
}
void QueueDestroy(Queue* pq)
{
assert(pq);
QNode* cur = pq->head;
while (cur != NULL)
{
QNode* next = cur->next;
free(cur);
cur = next;
}
pq->head = NULL;
pq->tail = NULL;
pq->size = 0;
}
bool QueueEmpty(Queue* pq)
{
return pq->head == NULL;
//return pq->size==0;
}
void QueuePush(Queue* pq,QDataTYpe x)
{
assert(pq);
QNode* newnode = (QNode*)malloc(sizeof(QNode));;
if (newnode == NULL)
{
perror("malloc:fail");
return;
}
newnode->data = x;
newnode->next = NULL;
if (pq->head == NULL)
{
pq->head = pq->tail = newnode;
}
else
{
pq->tail->next = newnode;
pq->tail = newnode;
}
pq->size++;
}
void QueuePop(Queue* pq)
{
assert(pq);
if (QueueEmpty(pq))
{
printf("队列为空\n");
return;
}
if (pq->head == pq->tail)
{
free(pq->head);
pq->head = NULL;
pq->tail = NULL;
}
else
{
QNode* next = pq->head->next;
free(pq->head);
pq->head = NULL;
pq->head = next;
}
pq->size--;
}
QDataTYpe QueueFront(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->head->data;
}
QDataTYpe QueueBack(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->tail->data;
}
int QueueSize(Queue* pq)
{
assert(pq);
return pq->size;
}
typedef struct {
Queue q;
Queue p;
} MyStack;
MyStack* myStackCreate() {
MyStack*obj=(MyStack*)malloc(sizeof(MyStack));
if(obj==NULL)
{
return NULL;
}
QueueInit(&obj->p);
QueueInit(&obj->q);
return obj;
}
void myStackPush(MyStack* obj, int x) {
if(QueueEmpty(&obj->p))
{
QueuePush(&obj->q,x);
}
else
{
QueuePush(&obj->p,x);
}
}
int myStackPop(MyStack* obj) {
Queue*Empty=&obj->q;
Queue*NoEmpty=&obj->p;
if(QueueEmpty(&obj->p))
{
Empty=&obj->p;
NoEmpty=&obj->q;
}
while(QueueSize(NoEmpty)>1)
{
QueuePush(Empty,QueueFront(NoEmpty));
QueuePop(NoEmpty);
}
int top=QueueFront(NoEmpty);
QueuePop(NoEmpty);
return top;
}
int myStackTop(MyStack* obj) {
if(QueueEmpty(&obj->p))
{
return QueueBack(&obj->q);
}
else
return QueueBack(&obj->p);
}
bool myStackEmpty(MyStack* obj) {
return QueueEmpty(&obj->q)&&QueueEmpty(&obj->p);
}
void myStackFree(MyStack* obj) {
QueueDestroy(&obj->q);
QueueDestroy(&obj->p);
free(obj);
}
5.2 栈模拟队列
栈模拟队列
栈模拟队列的话,可以想象成一个连通器
typedef int STDataType;
typedef struct Stack
{
STDataType* a;
int top;
int capacity;
}ST;
//初始化
void STInit(ST* ps);
//销毁
void STDestroy(ST* ps);
//压栈
void STPush(ST* ps,STDataType x);
//出栈
void STPop(ST* ps);
//判空
bool STEmpty(ST* ps);
//栈顶
STDataType STTop(ST* ps);
//个数
int STSize(ST* ps);
void STInit(ST* ps)
{
assert(ps);
ps->a = NULL;
ps->capacity = 0;
ps->top = 0;
}
void STDestroy(ST* ps)
{
assert(ps);
free(ps->a);
ps->a = NULL;
ps->capacity = 0;
ps->top = 0;
}
void STPush(ST* ps,STDataType x)
{
assert(ps);
if (ps->top == ps->capacity)
{
int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
STDataType* tmp = (STDataType*)realloc(ps->a, newcapacity*sizeof(STDataType));
if (tmp == NULL)
{
perror("realloc :fail");
return;
}
ps->a = tmp;
ps->capacity = newcapacity;
}
ps->a[ps->top++] = x;
}
bool STEmpty(ST* ps)
{
return ps->top == 0;
}
void STPop(ST* ps)
{
assert(ps);
assert(!STEmpty(ps));
ps->top--;
}
STDataType STTop(ST* ps)
{
assert(ps);
return ps->a[ps->top - 1];
}
int STSize(ST* ps)
{
assert(ps);
return ps->top;
}
typedef struct {
ST pushst;
ST popst;
} MyQueue;
MyQueue* myQueueCreate() {
MyQueue*obj=(MyQueue*)malloc(sizeof(MyQueue));
STInit(&obj->pushst);
STInit(&obj->popst);
return obj;
}
void myQueuePush(MyQueue* obj, int x) {
STPush(&obj->pushst,x);
}
int myQueuePop(MyQueue* obj) {
int ret=myQueuePeek(obj);
STPop(&obj->popst);
return ret;
}
int myQueuePeek(MyQueue* obj) {
if(STEmpty(&obj->popst))
{
while(!(STEmpty(&obj->pushst)))
{
STPush(&obj->popst,STTop(&obj->pushst));
STPop(&obj->pushst);
}
}
return STTop(&obj->popst);
}
bool myQueueEmpty(MyQueue* obj) {
return STEmpty(&obj->pushst)&&STEmpty(&obj->popst);
}
void myQueueFree(MyQueue* obj) {
STDestroy(&obj->pushst);
STDestroy(&obj->popst);
free(obj);
}
/**
* Your MyQueue struct will be instantiated and called as such:
* MyQueue* obj = myQueueCreate();
* myQueuePush(obj, x);
* int param_2 = myQueuePop(obj);
* int param_3 = myQueuePeek(obj);
* bool param_4 = myQueueEmpty(obj);
* myQueueFree(obj);
*/
5.3 循环队列
循环队列
解决循环队列问题的话
我们可以先定义固定大小的数组,用来存储元素
例如,我们需要一个可以存储3个数据的数组,我们现在就开辟4个数据的空间,以便于我们操作
typedef struct {
int front;
int rear;
int size;
int *a;
} MyCircularQueue;
bool myCircularQueueIsFull(MyCircularQueue* obj) ;
MyCircularQueue* myCircularQueueCreate(int k) {
MyCircularQueue*obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
obj->a=(int*)malloc(sizeof(int)*(k+1));
obj->size=k+1;
obj->front=0;
obj->rear=0;
return obj;
}
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
if((obj->rear+1)%(obj->size)==obj->front)
return false;
obj->a[obj->rear]=value;
obj->rear++;
obj->rear%=obj->size;
return true;
}
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
if(obj->rear==obj->front)
return false;
(obj->front)++;
obj->front%=obj->size;
return true;
}
int myCircularQueueFront(MyCircularQueue* obj) {
if(obj->rear==obj->front)
return -1;
return obj->a[obj->front];
}
int myCircularQueueRear(MyCircularQueue* obj) {
if(obj->rear==obj->front)
return -1;
return obj->a[(obj->rear-1+obj->size)%obj->size];
}
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
if(obj->rear==obj->front)
return true;
return false;
}
bool myCircularQueueIsFull(MyCircularQueue* obj) {
if((obj->rear+1)%(obj->size)==obj->front)
return true;
return false;
}
void myCircularQueueFree(MyCircularQueue* obj) {
free(obj->a);
obj->a=NULL;
free(obj);
}
/**
* Your MyCircularQueue struct will be instantiated and called as such:
* MyCircularQueue* obj = myCircularQueueCreate(k);
* bool param_1 = myCircularQueueEnQueue(obj, value);
* bool param_2 = myCircularQueueDeQueue(obj);
* int param_3 = myCircularQueueFront(obj);
* int param_4 = myCircularQueueRear(obj);
* bool param_5 = myCircularQueueIsEmpty(obj);
* bool param_6 = myCircularQueueIsFull(obj);
* myCircularQueueFree(obj);
*/
6、感谢与交流✅
🌹🌹🌹如果大家通过本篇博客收获了,对队列有了新的了解的话
那么希望支持一下哦如果还有不明白的,疑惑的话,或者什么比较好的建议的话,可以发到评论区,
我们一起解决,共同进步 ❗️❗️❗️
最后谢谢大家❗️❗️❗️💯💯💯文章来源:https://www.toymoban.com/news/detail-563596.html
文章来源地址https://www.toymoban.com/news/detail-563596.html
到了这里,关于队列--C语言实现数据结构的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!