数据结构——队列-循环队列

发布于：2025-02-10 ⋅ 阅读:(81) ⋅ 点赞:(0)

数据结构——队列-循环队列

一、循环队列的定义

循环队列是顺序队列结构，将顺序存储队列的元素的一维数组首尾相连

可以这么理解：顺序队列的首尾相连=循环队列
数据结构——队列-顺序队列
空的循环队列

1、循环队列的特点

先进先出（First In First Out，FIFO）(前出后进)

二、循环队列的相关术语

1、入队（EmQueue）

在队列中插入元素

2、出队（DeQueue）

在队列中删除元素

3、队头

允许进行删除的一端

队头元素

处于队头位置的数据元素

4、队尾

允许进行插入操作的一端

队尾元素

处于队尾位置的数据元素

5、空队

不含任何数据元素的队列

6、队满

整个队列的数组已被存储相应的元素

三、循环队列的基本操作及代码实现

相关头文件

#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 100
typedef int DataType;

定义循环队列的结构体

队列

循环队列的结构体需要有:

  1. 两个指针——头指针（front指向队头）、尾指针（rear指向队尾）
  2. 一个数组——存储已入队的数据

与顺序列表的结构体代码一样

//结构体
typedef struct
{
  DataType data[MAXSIZE];
  int front;
  int rear;
} Queue;

初始化循环队列（InitQueue）

初始条件：循环队列不存在

做法：设置头指针front、尾指针rear指向数组下标为0的位置；

操作结果：构造一个空的循环队列Q

//初始化循环队列
void InitQueue(Queue *Q)
{
  Q->front = 0;
  Q->rear = 0;
}

判断循环队列空（EmptyQueue）

初始条件：队列Q存在

核心思想：当头指针front、尾指针rear指同时向数组下标为0的位置为空

操作结果：判断是否是空队列，若队列Q为空，则返回1；否则返回0

//判断循环队列空
int EmptyQueue(Queue *Q)
{
  if (Q->front == Q->rear)
    return 1;
  return 0;
}

判断循环队列满（FullQueue）

初始条件：循环队列Q存在

核心思想：
当头指针front、尾指针rear满足：“（rear+1）%MAXSIZE=front ”时，循环队列为满（MAXSIZE是数组可存储的最大值）

操作结果：判断是否已经满，若循环队列Q为满，则返回1；否则返回0

//判断循环队列满
int FullQueue(Queue *Q)
{
  if (Q->front == (Q->rear + 1) % MAXSIZE)
    return 1;
  return 0;
}

入队(EnQueue)

初始条件：循环队列Q已存在且非满
入队操作核心思想

核心思想：

  1. 队尾指针（rear）指向下一个位置
  2. 把要入队的值赋值给尾指针rear指向的数组位置

操作结果：数据入队

//入队
void EnQueue(Queue *Q, DataType x)
{
  if (FullQueue(Q))
  {
    printf("循环队列已满,无法进行入队操作！\n");
    return;
  }
  Q->rear++;
  Q->data[Q->rear] = x;
}

出队（DeQueue）

初始条件：循环队列Q已存在且非空
出队操作核心思想

核心思想：

  1. 更新头指针（头指针front向后指）
  2. 打印输出要出队的元素（头指针front指向的数据）

操作结果：打印队头元素，并从队列Q中删除当前队头元素，而其后继元素称为队头元素

//出队
void DeQueue(Queue *Q)
{
  if (EmptyQueue(Q))
  {
    printf("循环队列为空，无法进行出队操作!\n");
    return;
  }
  Q->front++;
  printf("当前出队元素为：%d\n", Q->data[Q->front]);
}

取队头元素（GetFront）

初始条件：循环队列Q存在且不为空

思想：队头元素就是头指针front所指的下一个位置的元素

操作结果：将队头元素打印，循环队列Q不发生变化

//取队头元素
int GetFront(Queue *Q)
{
  if (EmptyQueue(Q))
    return -1;
  return Q->data[Q->front + 1];
}

取队尾元素（GetRear）

初始条件：循环队列Q存在且不为空

思想：队尾元素就是尾指针rear所指的数据

操作结果：将队尾元素打印，循环队列Q不发生变化

//取队尾元素
int GetRear(Queue *Q)
{
  if (EmptyQueue(Q))
    return -1;
  return Q->data[Q->rear];
}

获取循环队列元素个数（GetQueueCouunt）

初始条件：循环队列Q存在
操作结果：打印循环队列个数，循环队列Q不发生变化

//获取循环队列元素个数
int GetQueueCount(Queue *Q)
{
  return Q->rear - Q->front;
}

显示循环队列元素（ShowQueue）

初始条件：循环队列Q存在且不为空
操作：将循环队列Q中所有元素从队头开始打印

//显示循环队列元素
void ShowQueue(Queue *Q)
{
  if (EmptyQueue(Q))
    return;
  int n = GetQueueCount(Q);
  int j = Q->front;
  for (int i = 1; i <= n; i++)
  {
    j++;
    printf("%d ", Q->data[j]);
  }
  printf("\n");
}

清空循环队列（ClearQueue）

初始条件：循环队列Q存在且不为空

核心思想：头指针front和尾指针rear指向循环队列下标为0的位置

操作：将循环队列Q中所有元素清空

//清空循环队列
void ClearQueue(Queue *Q)
{
  Q->rear = Q->front = 0;
  printf("循环队列已清空！\n");
}

main函数

测试以上代码是否正确

// main函数
int main()
{
  int n, i, number = 0;
  Queue *Q = (Queue *)malloc(sizeof(Queue));
  ; // 在栈上分配内存
  // 初始化队列
  InitQueue(Q);
  //入队
  printf("要入队的元素个数是：");
  scanf("%d", &n);
  printf("请输入你要入队的元素：");
  for (i = 0; i < n; i++)
  {
    scanf("%d", &number);
    EnQueue(Q, number);
  }
  ShowQueue(Q);
  //出队
  DeQueue(Q);
  ShowQueue(Q);
  //取队头元素
  printf("此时队头元素为：%d\n", GetFront(Q));
  ShowQueue(Q);
  //取队尾元素
  printf("此时队尾元素为：%d\n", GetRear(Q));
  ShowQueue(Q);
  //获取元素个数
  printf("此时元素个数为：%d\n", GetQueueCount(Q));
  ShowQueue(Q);
  //清空栈
  ClearQueue(Q);
  ShowQueue(Q);
  return 0;
}

四、循环队列的优缺点

缺点

  1. 判断队空队满复杂:不能简单地通过比较队头和队尾指针是否相等来判断队空或队满。
  2. 数据容量固定:它的最大容量是预先确定的，这在某些动态变化的应用场景中可能会受到限制。可通过扩容操作解决，但扩容操作对于循环队列来说相对复杂，并且可能涉及到数据的重新分配和移动。

优点

  1. 高效利用空间：当队头元素出队后，队头前面的空间可以被重新利用；
    （通过将数组视为一个环形结构，使得队头前面的空间在队列循环使用过程中能够被再次利用）
  2. 便于实现和管理:主要通过调整队头和队尾指针来实现入队和出队操作。操作逻辑与普通队列相似，容易理解和编码实现。

五、完整代码

#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 100
typedef int DataType;
//结构体
typedef struct
{
  DataType data[MAXSIZE];
  int front;
  int rear;
} Queue;
//初始化循环队列
void InitQueue(Queue *Q)
{
  Q->front = 0;
  Q->rear = 0;
}
//判断循环队列空
int EmptyQueue(Queue *Q)
{
  if (Q->front == Q->rear)
    return 1;
  return 0;
}
//判断循环队列满
int FullQueue(Queue *Q)
{
  if (Q->front == (Q->rear + 1) % MAXSIZE)
    return 1;
  return 0;
}
//入队
void EnQueue(Queue *Q, DataType x)
{
  if (FullQueue(Q))
  {
    printf("循环队列已满,无法进行入队操作！\n");
    return;
  }
  Q->rear++;
  Q->data[Q->rear] = x;
}
//出队
void DeQueue(Queue *Q)
{
  if (EmptyQueue(Q))
  {
    printf("循环队列为空，无法进行出队操作!\n");
    return;
  }
  Q->front++;
  printf("当前出队元素为：%d\n", Q->data[Q->front]);
}
//取队头元素
int GetFront(Queue *Q)
{
  if (EmptyQueue(Q))
    return -1;
  return Q->data[Q->front + 1];
}
//取队尾元素
int GetRear(Queue *Q)
{
  if (EmptyQueue(Q))
    return -1;
  return Q->data[Q->rear];
}
//获取循环队列元素个数
int GetQueueCount(Queue *Q)
{
  return Q->rear - Q->front;
}
//显示循环队列元素
void ShowQueue(Queue *Q)
{
  if (EmptyQueue(Q))
    return;
  int n = GetQueueCount(Q);
  int j = Q->front;
  for (int i = 1; i <= n; i++)
  {
    j++;
    printf("%d ", Q->data[j]);
  }
  printf("\n");
}
//清空循环队列
void ClearQueue(Queue *Q)
{
  Q->rear = Q->front = 0;
  printf("循环队列已清空！\n");
}
// main函数
int main()
{
  int n, i, number = 0;
  Queue *Q = (Queue *)malloc(sizeof(Queue));
  ; // 在栈上分配内存
  // 初始化队列
  InitQueue(Q);
  //入队
  printf("要入队的元素个数是：");
  scanf("%d", &n);
  printf("请输入你要入队的元素：");
  for (i = 0; i < n; i++)
  {
    scanf("%d", &number);
    EnQueue(Q, number);
  }
  ShowQueue(Q);
  //出队
  DeQueue(Q);
  ShowQueue(Q);
  //取队头元素
  printf("此时队头元素为：%d\n", GetFront(Q));
  ShowQueue(Q);
  //取队尾元素
  printf("此时队尾元素为：%d\n", GetRear(Q));
  ShowQueue(Q);
  //获取元素个数
  printf("此时元素个数为：%d\n", GetQueueCount(Q));
  ShowQueue(Q);
  //清空栈
  ClearQueue(Q);
  ShowQueue(Q);
  return 0;
}

本章为数据结构——队列-循环队列，后续将继续更新链队列
​

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布