【数据结构】【版本1.4】【线性时代】——公平队列-阿里云开发者社区

【数据结构】【版本1.4】【线性时代】——公平队列

2024-03-27 34

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 【数据结构】【版本1.4】【线性时代】——公平队列

引言

数据结构世界遇到栈后，就迎来了与栈联系紧密的兄弟——队列（Queue）

逐渐地，在线性大陆上，出现了许许多多的空间通道，它们通向随机与未知，有可能只通向几米远，也有可能跨越整个世界，但是它们有一个共同的特性——先进先出

一、队列的概念与结构

队列： 只允许在一端进行插入数据操作，在另一端进行删除数据操作 的特殊线性表，队列具有 先进先出 FIFO(First In First Out)

入队列： 进行插入操作的一端称为队尾

出队列： 进行删除操作的一端称为队头

二、队列的实现

队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低。

2.1 定义

队列的实现，需要定义两个结构体，一个代表节点的信息，另一个代表队列的信息，因为队列的特性要在一端入，另一端出，所以要记录头尾指针（要不然找尾效率太低了），而size代表当前队列元素个数（可加可不加，加上更好）

2.2 初始化

头尾指针置为NULL，size置为0

2.3 销毁

队列的销毁，本质上就是链表的销毁 ，创建cur变量，循环释放每一个节点，直到cur为空，最后再将头尾指针置为NULL，size置为0

2.4 入队

入队时，先生成新节点（因为这里只有入队用到生成新节点，所以不用抽离成函数），再要分空链表和非空链表进行讨论

空链表判断时，加入assert断言，防止外部操作错误，造成头指针不为空，尾指针为空

链表为空时，则头尾指针都指向新节点；链表不为空时，则正常尾插

2.5 判断队列是否为空

专门写一个函数判断，增强复用性和可读性 。如果size为0，则队列为空，返回真；反之，则不为空，返回假

2.6 出队

出队时，先判断队列是否为空（保证phead不为NULL，防止为空指针的解引用），再分单个节点和多个节点来讨论

单个节点，则释放头指针指向的节点后，头尾指针置为NULL；多个节点，则正常头删

2.7 获取队头元素

2.8 获取队尾元素

2.9 检测队列中有效元素个数

2.10 元素访问

队列中元素访问（打印），不是用函数实现。因为它的特殊结构，决定了它的元素不能从任意位置访问 ，必须符合先进先出原则才可以。所以，我们通常用循环的方式进行访问，同时每访问一个元素，就将它弹出队列，再进行下一个元素的访问。

运行结果

队列与栈有所不同，因为它先进先出的特性，导致顺序只能是1 2 3 4

这样我们就实现了队列的增删等功能

三、队列oj题

仅仅了解队列的知识是不够的，让我们来刷刷题吧！

225.用队列实现栈（LeetCode）-CSDN博客

232.用栈实现队列（LeetCode）-CSDN博客

622.设计循环队列（LeetCode）-CSDN博客

看到这里了还不给博主扣个：
⛳️ 点赞☀️收藏 ⭐️ 关注！

💛 💙 💜 ❤️ 💚💓 💗 💕 💞 💘 💖

拜托拜托这个真的很重要！

你们的点赞就是博主更新最大的动力！

有问题可以评论或者私信呢秒回哦。

源代码

queue.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
 
typedef int QDataType;
typedef struct QueueNode
{
  QDataType data;
  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);
//检测队列中有效元素个数
int QueueSize(Queue* pq);
//检测队列是否为空
bool QueueEmpty(Queue* pq);

queue.c

#define _CRT_SECURE_NO_WARNINGS 1
#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 = pq->ptail = NULL;
  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->ptail == NULL)
  {
    assert(pq->phead == NULL);
    pq->phead = pq->ptail = newnode;
  }
  else
  {
    pq->ptail->next = newnode;
    pq->ptail = newnode;
  }
 
  pq->size++;
}
 
void QueuePop(Queue* pq)
{
  assert(pq);
  assert(!QueueEmpty(pq));
 
  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);
 
  return pq->phead->data;
}
 
QDataType QueueBack(Queue* pq)
{
  assert(pq);
 
  return pq->ptail->data;
}
 
int QueueSize(Queue* pq)
{
  assert(pq);
 
  return pq->size;
}
 
bool QueueEmpty(Queue* pq)
{
  assert(pq);
 
  return pq->size == 0;
}

test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"queue.h"
 
void TestQueue1()
{
  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);
  }
  //销毁
  QueueDestroy(&q);
}
 
int main()
{
  TestQueue1();
  return 0;
}