首页 > 其他分享 >循环队列

循环队列

时间：2023-08-14 18:07:20浏览次数：40  
标签：PQ 队列 SQ 循环 front data rear

循环队列_数据

循环队列_循环队列_02

为了避免当只有一个元素时，队头和队尾重合使得处理变得麻烦，所以引入两个指针front和rear。

front即队头指针指向队头元素，rear即队尾指针指向队尾元素的下一个元素。

这样当front等于rear是，不是队列中有一个元素，而是表示空队列。

循环队列_数据_03

假设数组长度为5，空队列即初始状态如图所示，front和rear都指向下标为0的位置。

当队列中有四个元素时，front不变，rear指向下标为4的位置。

循环队列_数据_04

若出队两个元素，front指向下标为2的位置，rear不变，再入队一个元素，front指针不变，但rear指针移动到数组之外。

循环队列_数据结构_05

假设该队列中数据元素总个数不超过5个，但是目前如果接着入队的话，会导致数组越界的问题。

但是队列在下标为0和1的位置是没有元素的。我们把这个现象叫做"假溢出"。

1. 概念

解决假溢出的办法就是后面满了，再从头开始，也就是头尾相接的循环。我们把队列的这种头尾相接的顺序存储结构称为循环队列。

循环队列_循环队列_06

此时如果再入列一个元素，会发现rear和front重合了。重合则无法判断其是满还是空。

解决办法：当队列空时，判断条件就是rear == front，当队列满时，我们修改其判断条件，保留一个元素空闲。也就说，当队列满时，数组中还有一个空闲单元。上面这种情况，我们认为队列已经满了。

为了使得满队和空队能够区分出来，必须牺牲一个数组单元，提前定义满队状态；

假设一个队列有n个元素，则顺序存储的队列需要建立一个大于n的数组。

此时一个满队的条件是rear加一，对循环队列长度取余后，等于front则说明其是满队。

(rear+1)%N == front


  1. 逻辑结构：线性结构
  2. 物理结构：顺序存储结构

2. 接口实现

2.1. 定义操作循环队列的结构体

  1. 定长数组
  2. 队头指针front
  3. 队尾指针rear
// 1. 定义操作循环队列的结构体
#define N 10
typedef int DataType;
typedef struct SeqQueue
{
    DataType data[N];
    int front;
    int rear;
} SQ;

2.2. 创建空的循环队列

循环队列_循环队列_07

// 2. 创建一个空的队列
SQ *SQCreate()
{
    // 2.1 开辟空间存放操作队列的结构体
    SQ *PQ = (SQ *)malloc(sizeof(SQ));
    if (NULL == PQ)
    {
        printf("SQCreate failed, PQ malloc err.\n");
        return NULL;
    }

    // 2.2 初始化结构体成员
    PQ->front = PQ->rear = 0;

    return PQ;
}
#include "SQ.h"

int main(int argc, char const *argv[])
{
    // 2. 创建空的循环队列
    SQ *PQ = SQCreate();
    
    return 0;
}

2.3. 入列

循环队列_数据结构_08

  1. 判满
  2. 数据入列
  3. 移动尾指针
// 3. 数据入列
void SQPush(SQ *PQ, DataType data)
{
    // 3.1 容错判断——判满
    if ((PQ->rear+1)%N == PQ->front)
    {
        printf("SQPush failed, SQ is full.\n");
        return ;
    }

    // 3.2 数据入列
    PQ->data[PQ->rear] = data;

    // 3.3 移动尾指针
    PQ->rear = (PQ->rear + 1) % N;
}
#include "SQ.h"

int main(int argc, char const *argv[])
{
    // 2. 创建空的循环队列
    SQ *PQ = SQCreate();

    SQPush(PQ, 111);
    SQPush(PQ, 222);
    SQPush(PQ, 333);

    return 0;
}

2.4. 出列

循环队列_数据_09

  1. 容错判断——判空
  2. 保存出列数据
  3. 移动队头指针
  4. 返回出列数据
// 4. 数据出列
DataType SQPop(SQ *PQ)
{
    // 4.1 容错判断——判空
    if (PQ->front == PQ->rear)
    {
        printf("SQPop failed, SQ is empty.\n");
        return -1;
    }

    // 4.2 保存出列数据
    DataType data = PQ->data[PQ->front];

    // 4.3 移动队头指针
    PQ->front = (PQ->front+1)%N;

    // 4.4 返回出列数据
    return data;
}
#include "SQ.h"

int main(int argc, char const *argv[])
{
    // 2. 创建空的循环队列
    SQ *PQ = SQCreate();

    SQPush(PQ, 111);
    SQPush(PQ, 222);
    SQPush(PQ, 333);

    DataType data = SQPop(PQ);
    printf("SQPop data is %d\n", data);
    // SQPop data is 111

    return 0;
}
SQPop data is 111

2.5. 列长

// 5. 列长
int SQLength(SQ *PQ)
{
    return (PQ->rear + N - PQ->front) % N;
}
#include "SQ.h"

int main(int argc, char const *argv[])
{
    // 2. 创建空的循环队列
    SQ *PQ = SQCreate();

    SQPush(PQ, 111);
    SQPush(PQ, 222);
    SQPush(PQ, 333);

    DataType data = SQPop(PQ);
    printf("SQPop data is %d\n", data);
    // SQPop data is 111

    int len = SQLength(PQ);
    printf("SQLength is %d\n", len);
    // SQLength is 2


    return 0;
}
SQPop data is 111
SQLength is 2

2.6. 清空

// 6. 清空
void SQClear(SQ *PQ)
{
    PQ->front = PQ->rear = 0;
}
#include "SQ.h"

int main(int argc, char const *argv[])
{
    // 2. 创建空的循环队列
    SQ *PQ = SQCreate();

    SQPush(PQ, 111);
    SQPush(PQ, 222);
    SQPush(PQ, 333);

    DataType data = SQPop(PQ);
    printf("SQPop data is %d\n", data);
    // SQPop data is 111

    int len = SQLength(PQ);
    printf("SQLength is %d\n", len);
    // SQLength is 2

    SQClear(PQ);

    len = SQLength(PQ);
    printf("SQLength is %d\n", len);
    // SQLength is 0

    free(PQ);
    PQ = NULL;

    return 0;
}
SQPop data is 111
SQLength is 2
SQLength is 0

2.7. 总结

#ifndef _SQ_H_
#define _SQ_H_

#include <stdio.h>
#include <stdlib.h>

// 1. 定义操作循环队列的结构体
#define N 10
typedef int DataType;
typedef struct SeqQueue
{
    DataType data[N];
    int front;
    int rear;
} SQ;

// 2. 创建一个空的队列
SQ *SQCreate();

// 3. 数据入列
void SQPush(SQ *PQ, DataType data);

// 4. 数据出列
DataType SQPop(SQ *PQ);

// 5. 列长
int SQLength(SQ *PQ);

// 6. 清空
void SQClear(SQ *PQ);


#endif
#include "SQ.h"

// 2. 创建一个空的队列
SQ *SQCreate()
{
    // 2.1 开辟空间存放操作队列的结构体
    SQ *PQ = (SQ *)malloc(sizeof(SQ));
    if (NULL == PQ)
    {
        printf("SQCreate failed, PQ malloc err.\n");
        return NULL;
    }

    // 2.2 初始化结构体成员
    PQ->front = PQ->rear = 0;

    return PQ;
}

// 3. 数据入列
void SQPush(SQ *PQ, DataType data)
{
    // 3.1 容错判断——判满
    if ((PQ->rear+1)%N == PQ->front)
    {
        printf("SQPush failed, SQ is full.\n");
        return ;
    }

    // 3.2 数据入列
    PQ->data[PQ->rear] = data;

    // 3.3 移动尾指针
    PQ->rear = (PQ->rear + 1) % N;
}

// 4. 数据出列
DataType SQPop(SQ *PQ)
{
    // 4.1 容错判断——判空
    if (PQ->front == PQ->rear)
    {
        printf("SQPop failed, SQ is empty.\n");
        return -1;
    }

    // 4.2 保存出列数据
    DataType data = PQ->data[PQ->front];

    // 4.3 移动队头指针
    PQ->front = (PQ->front+1)%N;

    // 4.4 返回出列数据
    return data;
}

// 5. 列长
int SQLength(SQ *PQ)
{
    return (PQ->rear + N - PQ->front) % N;
}

// 6. 清空
void SQClear(SQ *PQ)
{
	PQ->front = PQ->rear = 0;
}
#include "SQ.h"

int main(int argc, char const *argv[])
{
    // 2. 创建空的循环队列
    SQ *PQ = SQCreate();

    SQPush(PQ, 111);
    SQPush(PQ, 222);
    SQPush(PQ, 333);

    DataType data = SQPop(PQ);
    printf("SQPop data is %d\n", data);
    // SQPop data is 111

    int len = SQLength(PQ);
    printf("SQLength is %d\n", len);
    // SQLength is 2

    SQClear(PQ);

    len = SQLength(PQ);
    printf("SQLength is %d\n", len);
    // SQLength is 0

    free(PQ);
    PQ = NULL;

    return 0;
}

标签：PQ,队列,SQ,循环,front,data,rear
From： https://blog.51cto.com/u_16225617/7079259

相关文章

  • vue-router动态路由无限循环
    //isLogined用来判断用户是否已登录router.beforeEach((to,from,next)=>{if(isLogined){next()}else{console.log('测试')next('login')}})next()表示放行，直接进入to路由，不会再次调用router.beforeEach()next(path:...to,replace:true)拦截......
  • 循环语句
    循环语句For循环基本语法for(循环变量初始值;循环条件;循环变量迭代){​ 代码块；}执行流程注意事项for循环的初始化变量，循环迭代值，可以放在其他地方。但是分号不能省略。例：for(;循环判断条件;)初始值可以定义在循环体之前，迭代值可以写在循环体之内。for(;;)死循环循环......
  • 剑指 Offer 09. 用两个栈实现队列
    用两个栈实现一个队列。队列的声明如下，请实现它的两个函数appendTail和deleteHead，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead操作返回-1)示例1：输入：["CQueue","appendTail","deleteHead","deleteHead","deleteHead"][[],[3],......
  • Linux之shell脚本的循环
    一、循环语句1.1forhelpfor帮助文档foriinabc;doechohello;done[root@localhostdata]#foriinabc;doechohello;donehellohellohelloforiinabc;doecho$i;done[root@localhostdata]#foriinabc;doecho$i;doneabc[root@localhostd......
  • python 实现队列
    官方文档不推荐使用列表因为列表删除第一个元素会把剩余元素向左移一位速度很慢官方推荐的是collections下的deque 记录一下防止忘记 fromcollectionsimportdeque d=deque(‘内容’，maxlength)内容可以是推导式也可以直接写内容内容写在一起比如'123'结果会......
  • 单调队列模板
    好的，这是一个晴朗的夜晚。-苯荏水平不高甚至菜亖，博客仅仅写给自己避免自己忘记学了什么，也仅据我理解写出，不严谨，非常不严谨。单调队列。在原序列基础上，维护一个单调的序列。单调队列中的元素在原序列中的相对位置不变，且在单调队列中的元素是单调的。基本模板题：https://www.lu......
  • 如何在C语言中实现队列和堆栈的动态扩容
    如何在C语言中实现队列和堆栈的动态扩容队列和堆栈是在C语言中常用的数据结构，它们可以帮助我们高效地处理数据。然而，在实际编程中，我们经常会遇到数据量超过容量限制的情况。这时，我们需要实现队列和堆栈的动态扩容，以满足实际需求。6如何在C语言中实现队列和堆栈的动态扩容动态扩......
  • 数据结构与算法 --- 组数、链表、栈和队列（一）
    数组、链表、栈和队列是四种基础数据结构，他们是高级、复杂的数据结构和算法的基础。本篇先来讲述数组，链表，及算法的优化策略。数组定义数组：数组是一种线性表数据结构，它用一组连续的内存空间存储一组具有相同类型的数据。定义中有三个关键词：线性表连续的内存空间相同类型数......
  • 数据结构与算法 --- 组数、链表、栈和队列（二）
    继数据结构与算法---组数、链表、栈和队列（一）讲解完数组，链表及算法的优化策略之后，接下来继续讲解两种特殊的线性表结构，栈和队列。栈对“栈”有一个很形象的比喻，栈就像一摞叠在一起的盘子，放盘子时，只能放在上面，不能将盘子插入到中间的任意位置；取盘子时，只能从最上面取，不能从中间任......
  • JavaScript之循环及其案例
    1循环循环的目的在实际问题中，有许多具有规律性重复性操作，因此在程序中要完成这类操作就需要重复执行某些语句。1.1JS中的循环在JS中，主要有三种类型的循环语句：for循环while循环do...while循环2for循环在程序中，一组被重复执行的语句被称之为循环体，能否继续重复执行，取决于循环的终......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99