专栏首页huiC语言实现循环队列

C语言实现循环队列

文章目录
  • 顺序队列的假溢出
    • 解决上溢的方法
    • 引入循环队列
  • 循环队列判空、判满冲突
  • 循环队列常规操作
  • 定义循环队列结构体
  • 初始化循环队列
  • 循环队列判满
  • 循环队列判空
  • 计算循环队列的长度
  • 循环队列 入队(EnQueue)
  • 循环队列 出队(DeQueue)
  • 循环队列各操作测试
  • 源代码

顺序队列的假溢出

1️⃣:初始化空队列,q -> front = q -> rear = 0

2️⃣:入队a1、a2、a3,q -> front = 0, q -> rear = 3

3️⃣:出队a1、a2,q -> front = 2, q -> rear = 3

4️⃣:入队a4、a5、a6,q -> front = 2, q -> rear = 6

执行 4️⃣ 操作后队列的"尾指针"已经超出对队列的最大范围了,之后无法再进行入队操作,而队列实际空间并未占满,就造成了假溢出。

解决上溢的方法

1、将队中元素依次向队头方向移动。

  • 缺点:浪费时间。每移动一次, 队中元素都要移动

2、将队列空间设想成一个循环的表,即分配给队列的 m 个存储单元可以循环使用,当 rearMAXSIZE 时,若队列的开始端空着,又可从头使用空着的空间。当 frontMAXSIZE 时也是一样。

我们采用第2种方法

5️⃣:入队a7,q -> front = 2, q -> rear = 0

引入循环队列

base[0] 接在 base[MAXSIZE -1] 之后,若 rear + 1 == M,则令 rear = 0

实现方法: 利用 模(mod,C语言中: %)运算

插入元素:

// 队尾入队
q -> base[q -> rear] = data;
// 更新队尾指针
q -> rear = (q -> rear + 1) % MAXSIZE;

删除元素:

// 队头元素出队
data = q -> base[q -> front];
// 更新队头指针
q -> front = (q -> front + 1) % MAXSIZE;

循环队列判空、判满冲突

解决方案:

1.另外设一个标致以区别队空、队满

2.另设一个变量,记录元素个数

3.少用一个元素空间

本文实现的方法就是第三种。

循环队列常规操作

/********************* 循环队列的常规操作 **************************/

Queue    InitQueue();             	// 初始化循环队列
int      QueueFull();               // 循环队列判满
int      QueueEmpty();              // 循环队列判空
int      QueueLength();             // 求循环队列长度(元素个数)
int      EnQueue();                 // 循环队列 入队
int      DeQueue();                 // 循环队列 出队

void     QueueStatus();             // 打印队满、队空、队长状态
/****************************************************************/

定义循环队列结构体

#include "stdio.h"
#include "malloc.h"

#define TRUE  1
#define FALSE 0
#define MAXSIZE 10

typedef int ElemType;


// 定义循环队列结构体
typedef struct Queue{

	int *base;	// 队列首地址
	int front;	// 队列头下标
	int rear;	// 队列尾下标

}*Queue;

初始化循环队列

/*
 * 初始化循环队列 
*/
Queue InitQueue(){
    Queue q;
    // 分配循环队列空间
    q -> base = (ElemType *)malloc(sizeof(ElemType) * MAXSIZE);
    q -> front = q -> rear = 0;
    return q;
}

循环队列判满

/*
 *  循环队列判满
 *  q 循环队列
*/
int QueueFull(Queue q){
    if(q == NULL){
        return FALSE;
    }
    return (q -> rear + 1) % MAXSIZE == q -> front;
}

循环队列判空

/*
 *  循环队列判空
 *  q 循环队列
*/
int QueueEmpty(Queue q){
    if(q == NULL){
        return FALSE;
    }
    return q -> front == q -> rear;
}

计算循环队列的长度

/*
 *  计算循环队列长度
 *  q 循环队列
*/
int QueueLength(Queue q){
    if(q == NULL){
        return FALSE;
    }
    return (q -> rear - q -> front + MAXSIZE) % MAXSIZE;
}

循环队列 入队(EnQueue)

/*
 *  循环队列 入队
 *  q 循环队列
 *  data 入队元素
*/
int EnQueue(Queue q, ElemType data){
    if(QueueFull(q)){
        return FALSE;
    }
    // 队尾入队
    q -> base[q -> rear] = data;
    // 更新队尾指针
    q -> rear = (q -> rear + 1) % MAXSIZE;
    return TRUE;
}

循环队列 出队(DeQueue)

/*
 *  循环队列 出队
 *  q 循环队列
 *  *val 用来存出队元素的数据 
*/
int DeQueue(Queue q, ElemType *val){
    if(QueueEmpty(q)){
        return FALSE;
    }
    // 队头元素出队
    *val = q -> base[q -> front];
    // 更新队头指针
    q -> front = (q -> front + 1) % MAXSIZE;
    return TRUE;
}

循环队列各操作测试

/*
 * 打印队满、队空、队长状态
 * q 循环队列
*/
void QueueStatus(Queue q){
    printf("QueueFull():%d\n", QueueFull(q));
    printf("QueueEmpty():%d\n", QueueEmpty(q));
    printf("QueueLength():%d\n\n", QueueLength(q));
}

// 程序主入口
int main(int argc, char const *argv[])
{   
    Queue q = InitQueue();
    printf("QueueMaxSize: %d\n\n", MAXSIZE);
    QueueStatus(q); // 打印队满、队空、队长状态

    // 入队
    printf("EnQueue():");
    for(int i = 1; i < MAXSIZE * 2; i+=2){
        printf("%d\t", i);
        EnQueue(q, i);
    }

    printf("\n");
    QueueStatus(q);

    // 出队
    int val;
    printf("DeQueue():");
    while(!QueueEmpty(q)){
        DeQueue(q, &val);
        printf("%d\t", val);
    }
    printf("\n");
    QueueStatus(q);

    // 测试循环队列是否会假溢出
    int num = 20;
    printf("EnQueue(%d): %d\t(0 Failed, 1 Success)\n", num, EnQueue(q, num));
    QueueStatus(q);
    return 0;
}

结果如下:

QueueMaxSize: 10

QueueFull():0
QueueEmpty():1
QueueLength():0

EnQueue():1     3       5       7       9       11      13      15      17      19
QueueFull():1
QueueEmpty():0
QueueLength():9

DeQueue():1     3       5       7       9       11      13      15      17
QueueFull():0
QueueEmpty():1
QueueLength():0

EnQueue(20): 1(0 Failed, 1 Success)
QueueFull():0
QueueEmpty():0
QueueLength():1

源代码

源代码已上传到 GitHub Data-Structure-of-C,欢迎大家下载 C语言实现数据结构

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 数据结构 - 栈和队列

    栈(stack) 是一个特殊的线性表,是限定仅在一端(通常是表尾)进行插入和删除操作的线性表。表尾的一端有其特殊含义,称为 栈顶(top) ,相应地,表头称为 ...

    忆想不到的晖
  • C语言实现顺序队列

    顺序队列和顺序栈相类似,在队列的顺序存储结构中,除了用一组地址连续的存储单元依次存放从队列头到队列尾的元素之外,尚需附设两个 “指针” front 和 rear...

    忆想不到的晖
  • 树和二叉树

    ​ 2. 当 n > 1 时,其余结点可分为 m(m > 0)个互不相交的有限集T1、T2,… ,Tm,其中每一个集合本身又是一颗树,并且称为根的 子树(Sub...

    忆想不到的晖
  • 使用JavaScript创建队列结构

    队列和栈是两种相似的结构,区别主要在于栈是先进后出,队列是先进先出(FIFO)。队列插入元素是在队尾插入,在队列头弹出,形象的描述为排队,先到的先办事,后到的后...

    无邪Z
  • 《WCF服务编程》关于“队列服务”一个值得商榷的地方

    今天写《WCF技术剖析(卷2)》关于“队列服务”部分,看了《WCF服务编程》相关的内容。里面介绍一个关于“终结点不能共享相同的消息队列”说法,个人觉得这值得商榷...

    蒋金楠
  • RabbitMQ消息通信

    ---- 概述 RabbitMQ是一个开源的消息代理和队列服务器,用来通过普通协议在完全不同的应用之间共享数据或者将作业排队以便让分布式服务器进行处理。应用程序...

    BrianLv
  • IBM WebSphere MQ 系列(一)基础知识

    Java学习123
  • 消息队列常见的 5 个应用场景

    原文链接:https://segmentfault.com/a/1190000017130224

    业余草
  • 分布式架构实记——消息队列(一)

    消息队列中间件是分布式系统中重要的组件,主要解决应用耦合,异步消息,流量削锋等问题。实现高性能,高可用,可伸缩和最终一致性架构。是大型分布式系统不可缺少的中间件...

    慕容千语
  • Cypress web自动化17-fixture加载json文件数据

    面试时间经常被问到:你的测试数据放哪?有没有做到测试数据和代码的分离? Cypress 使用cypress/fixture 目录存放 json 文件数据, cy...

    上海-悠悠

扫码关注云+社区

领取腾讯云代金券