AI 助理
备案控制台
开发者社区 云计算 文章 正文

【数据结构】队列的实现

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

时间一直在流逝，貌似所有人都在向前走，只有我一直在原地踏步，说着要向前看要向前看，可总感觉没有完全放开步子大步向前走，2022我们来一次告别仪式吧，告别所有的不好，迎来崭新的2023，已然找不到坚持下去的理由，那就找一个重新开始的理由吧。

9635c87b5eebb5152fdf4c4285c04ddd_d7fd4a3bd0dc43129db2c21208016d79.jpeg

目录


队列 ：


队列的概念及结构：


队列的各功能实现：


结构体：


QueueInit(初始化队列)：


QueueDestroy(销毁队列)：


QueuePush(队尾入队列):


QueuePop(队头出队列):


QueueFront(获取队列头部元素):


QueueBack(获取队列队尾元素):


QueueEmpty(检测队列是否为空):


QueueSize(返回队列大小):


完整代码：


Queue.h:


Queue.c:


Text.c:

队列 ：

队列的概念及结构：

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

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

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

022f0652c81547f5e4a8ba9758364db4_a28958c149574eed82b64cc3957b4900.png

队列的各功能实现：

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

结构体：

// 链式结构：表示队列
typedef struct QueueNode
{
  QDataType data;
  struct Queue* next;
}Qnode;
// 队列的结构
typedef struct Queue
{
  Qnode* head;
  Qnode* tail;
  int size;
}Queue;

QueueInit(初始化队列)：

// 初始化队列
void QueueInit(Queue* pq)
{
  assert(pq);
  pq->head = NULL;
  pq->tail = NULL;
  pq->size = 0;
}

QueueDestroy(销毁队列)：

// 销毁队列
void QueueDestroy(Queue* pq)
{
  assert(pq);
  Qnode* cur = pq->head;
  while (cur)
  {
    Qnode* del = cur;
    cur = cur->next;
    free(del);
    del = NULL;
  }
  pq->head = pq->tail = NULL;
  pq->size = 0;
}

QueuePush(队尾入队列):

// 队尾入队列
void QueuePush(Queue* pq, QDataType x)
{
  assert(pq);
  Qnode* newnode = (Qnode*)malloc(sizeof(Qnode));
  if (newnode == NULL)
  {
    perror("malloc: fail");
    exit(-1);
  }
  else
  {
    newnode->data = x;
    newnode->next = NULL;
  }
  if (pq->tail == NULL)
  {
    pq->head = pq->tail = newnode;
  }
  else
  {
    pq->tail->next = newnode;
    pq->tail = newnode;
  }
  pq->size++;
}

QueuePop(队头出队列):

// 队头出队列
void QueuePop(Queue* pq)
{
  assert(pq);
  assert(!QueueEmpty(pq));
  if (pq->head->next == NULL)
  {
    free(pq->head);
    pq->head = pq->tail = NULL;
  }
  else
  {
    Qnode* del = pq->head;
    pq->head = pq->head->next;
    free(del);
  }
  pq->size--;
}

QueueFront(获取队列头部元素):

// 获取队列头部元素
QDataType QueueFront(Queue* pq)
{
  assert(pq);
  assert(!QueueEmpty(pq));
  return pq->head->data;
}

QueueBack(获取队列队尾元素):

// 获取队列队尾元素
QDataType QueueBack(Queue* pq)
{
  assert(pq);
  assert(!QueueEmpty(pq));
  return pq->tail->data;
}

QueueEmpty(检测队列是否为空):

// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
bool QueueEmpty(Queue* pq)
{
  assert(pq);
  return pq->head == NULL && pq->tail == NULL;
}

QueueSize(返回队列大小):

//返回队列大小
int QueueSize(Queue* pq)
{
  assert(pq);
  return pq->size;
}

完整代码：

Queue.h:

#pragma once
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <stdbool.h>
typedef int QDataType;
// 链式结构：表示队列
typedef struct QueueNode
{
  QDataType data;
  struct Queue* next;
}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);
// 获取队列头部元素
QDataType QueueFront(Queue* pq);
// 获取队列队尾元素
QDataType QueueBack(Queue* pq);
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
bool QueueEmpty(Queue* pq);
//返回队列大小
int QueueSize(Queue* pq);

Queue.c:

#define _CRT_SECURE_NO_WARNINGS 1
#include "Queue.h"
// 初始化队列
void QueueInit(Queue* pq)
{
  assert(pq);
  pq->head = NULL;
  pq->tail = NULL;
  pq->size = 0;
}
// 销毁队列
void QueueDestroy(Queue* pq)
{
  assert(pq);
  Qnode* cur = pq->head;
  while (cur)
  {
    Qnode* del = cur;
    cur = cur->next;
    free(del);
    del = NULL;
  }
  pq->head = pq->tail = NULL;
  pq->size = 0;
}
// 队尾入队列
void QueuePush(Queue* pq, QDataType x)
{
  assert(pq);
  Qnode* newnode = (Qnode*)malloc(sizeof(Qnode));
  if (newnode == NULL)
  {
    perror("malloc: fail");
    exit(-1);
  }
  else
  {
    newnode->data = x;
    newnode->next = NULL;
  }
  if (pq->tail == NULL)
  {
    pq->head = pq->tail = newnode;
  }
  else
  {
    pq->tail->next = newnode;
    pq->tail = newnode;
  }
  pq->size++;
}
// 队头出队列
void QueuePop(Queue* pq)
{
  assert(pq);
  assert(!QueueEmpty(pq));
  if (pq->head->next == NULL)
  {
    free(pq->head);
    pq->head = pq->tail = NULL;
  }
  else
  {
    Qnode* del = pq->head;
    pq->head = pq->head->next;
    free(del);
  }
  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;
}
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
bool QueueEmpty(Queue* pq)
{
  assert(pq);
  return pq->head == NULL && pq->tail == NULL;
}
//返回队列大小
int QueueSize(Queue* pq)
{
  assert(pq);
  return pq->size;
}

Text.c:

#define _CRT_SECURE_NO_WARNINGS 1
#include "Queue.h"
void TestQueue()
{
  //Queue q1;
  //Queue q2;
  //QueueInit(&q1);
  //QueueInit(&q2);
  //QueueDestroy(&q1);
  //QueueDestroy(&q2);
  Queue q;
  QueueInit(&q);
  QueuePush(&q, 1);
  QueuePush(&q, 2);
  QueuePush(&q, 3);
  QueuePush(&q, 4);
  printf("%d\n", QueueSize(&q));
  printf("%d\n", QueueEmpty(&q));
  printf("%d\n", QueueFront(&q));
  printf("%d\n", QueueBack(&q));
  while (!QueueEmpty(&q))
  {
    printf("%d ", QueueFront(&q));
    QueuePop(&q);
  }
  printf("\n");
  printf("%d\n", QueueSize(&q));
  printf("%d\n", QueueEmpty(&q));
  //printf("%d\n", QueueFront(&q));
  //printf("%d\n", QueueBack(&q));
  QueueDestroy(&q);
}
int main()
{
  TestQueue();
  return 0;
}


关键词：
数据结构队列
日出等日落
目录
相关文章
ephemerals__
|
4月前
|
C语言
【数据结构】栈和队列（c语言实现）（附源码）
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表，遵循“先进后出”原则；队列则在一端插入、另一端删除，遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现，并提供了完整的代码示例。栈和队列在实际应用中非常广泛，如二叉树的层序遍历和快速排序的非递归实现等。
ephemerals__
372 9
RossyYan
|
2月前
|
存储 C语言 C++
【C++数据结构——栈与队列】顺序栈的基本运算（头歌实践教学平台习题）【合集】
本关任务：编写一个程序实现顺序栈的基本运算。开始你的任务吧，祝你成功！​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 1.初始化栈 概念：初始化栈是为栈的使用做准备，包括分配内存空间（如果是动态分配）和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈，通常需要定义一个数组来存储栈元素，并设置一个变量来记录栈顶位置；对于链式栈，需要定义节点结构，包含数据域和指针域，同时初始化栈顶指针。 示例（顺序栈）： 以下是一个简单的顺序栈初始化示例，假设用C语言实现，栈中存储
RossyYan
158 77
蓝易云
|
2天前
|
算法 调度 C++
STL——栈和队列和优先队列
通过以上对栈、队列和优先队列的详细解释和示例，希望能帮助读者更好地理解和应用这些重要的数据结构。
蓝易云
15 4
羑悻的小杀马特
|
16天前
|
DataX
☀☀☀☀☀☀☀有关栈和队列应用的oj题讲解☼☼☼☼☼☼☼
### 简介 本文介绍了三种数据结构的实现方法：用两个队列实现栈、用两个栈实现队列以及设计循环队列。具体思路如下： 1. **用两个队列实现栈**： - 插入元素时，选择非空队列进行插入。 - 移除栈顶元素时，将非空队列中的元素依次转移到另一个队列，直到只剩下一个元素，然后弹出该元素。 - 判空条件为两个队列均为空。 2. **用两个栈实现队列**： - 插入元素时，选择非空栈进行插入。 - 移除队首元素时，将非空栈中的元素依次转移到另一个栈，再将这些元素重新放回原栈以保持顺序。 - 判空条件为两个栈均为空。
羑悻的小杀马特
30 14
RossyYan
|
2月前
|
存储 C++ 索引
【C++数据结构——栈与队列】环形队列的基本运算（头歌实践教学平台习题）【合集】
【数据结构——栈与队列】环形队列的基本运算（头歌实践教学平台习题）【合集】初始化队列、销毁队列、判断队列是否为空、进队列、出队列等。本关任务：编写一个程序实现环形队列的基本运算。(6)出队列序列:yzopq2*(5)依次进队列元素:opq2*(6)出队列序列:bcdef。(2)依次进队列元素:abc。(5)依次进队列元素:def。(2)依次进队列元素:xyz。开始你的任务吧，祝你成功！(4)出队一个元素a。(4)出队一个元素x。
RossyYan
50 13
【C++数据结构——栈与队列】环形队列的基本运算（头歌实践教学平台习题）【合集】
RossyYan
|
2月前
|
存储 C语言 C++
【C++数据结构——栈与队列】链栈的基本运算（头歌实践教学平台习题）【合集】
本关任务：编写一个程序实现链栈的基本运算。开始你的任务吧，祝你成功！​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 初始化栈 概念：初始化栈是为栈的使用做准备，包括分配内存空间（如果是动态分配）和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈，通常需要定义一个数组来存储栈元素，并设置一个变量来记录栈顶位置；对于链式栈，需要定义节点结构，包含数据域和指针域，同时初始化栈顶指针。 示例（顺序栈）： 以下是一个简单的顺序栈初始化示例，假设用C语言实现，栈中存储整数，最大
RossyYan
51 9
RossyYan
|
2月前
|
C++
【C++数据结构——栈和队列】括号配对（头歌实践教学平台习题）【合集】
【数据结构——栈和队列】括号配对（头歌实践教学平台习题）【合集】（1）遇到左括号：进栈Push()（2）遇到右括号：若栈顶元素为左括号，则出栈Pop()；否则返回false。（3）当遍历表达式结束，且栈为空时，则返回true，否则返回false。本关任务：编写一个程序利用栈判断左、右圆括号是否配对。为了完成本关任务，你需要掌握：栈对括号的处理。（1）遇到左括号：进栈Push()开始你的任务吧，祝你成功！测试输入：(()))
RossyYan
43 7
龙大吉
|
4月前
|
存储 缓存 算法
在C语言中，数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中，数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式，强调了合理选择数据结构的重要性，并通过案例分析展示了其在实际项目中的应用，旨在帮助读者提升编程能力。
龙大吉
104 5
肾透侧视攻城狮
|
4月前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之栈和队列精题汇总（10）【无论是王道考研人还是IKUN都能包会的；不然别给我家鸽鸽丢脸好嘛？】
数据结构王道第3章之IKUN和I原达人之数据结构与算法系列学习栈与队列精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子；这都学不会；能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛？！！！
肾透侧视攻城狮
48 1
禁默
|
5月前
初步认识栈和队列
初步认识栈和队列
禁默
75 10

热门文章

最新文章

  • 1
    C 408—《数据结构》易错考点200题（含解析）
  • 2
    C 408—《数据结构》算法题基础篇—链表（上）
  • 3
    C 408—《数据结构》算法题基础篇—链表（下）
  • 4
    C 408—《数据结构》图、查找、排序专题考点（含解析）
  • 5
    C 408—《数据结构》算法题基础篇—数组（通俗易懂）
  • 6
    c语言及数据结构实现简单贪吃蛇小游戏
  • 7
    Redis原理—1.Redis数据结构
  • 8
    ☀☀☀☀☀☀☀有关栈和队列应用的oj题讲解☼☼☼☼☼☼☼
  • 9
    【C++数据结构——栈与队列】顺序栈的基本运算（头歌实践教学平台习题）【合集】
  • 10
    【C++数据结构——查找】二分查找（头歌实践教学平台习题）【合集】
  • 1
    STL——栈和队列和优先队列
    15
  • 2
    Redis原理—1.Redis数据结构
    40
  • 3
    c语言及数据结构实现简单贪吃蛇小游戏
    49
  • 4
    ☀☀☀☀☀☀☀有关栈和队列应用的oj题讲解☼☼☼☼☼☼☼
    30
  • 5
    C 408—《数据结构》算法题基础篇—链表（下）
    86
  • 6
    C 408—《数据结构》算法题基础篇—链表（上）
    94
  • 7
    C 408—《数据结构》算法题基础篇—数组（通俗易懂）
    72
  • 8
    C 408—《数据结构》图、查找、排序专题考点（含解析）
    74
  • 9
    C 408—《数据结构》易错考点200题（含解析）
    130
  • 10
    数据结构（C语言）之对归并排序的介绍与理解
    36

    • 相关课程

    更多
  • Go语言核心编程 - 数据结构和算法

    • 相关电子书

    更多
  • 如何使用Tair增强数据结构构建丰富在线实时场景
  • Apache Flink 流式应用中状态的数据结构定义升级
  • 低代码开发师（初级）实战教程
    • 下一篇
    通义万相：视觉生成大模型再进化