当前位置： 首页 > article >正文

数据结构（顺序队列——c语言实现）

article 2024/11/25 22:06:10

队列的概念：

       队列是限制在两端进行插入和删除操作的线性表，允许进行存入的一端称为“队尾”，允许进行删除操作的一端称为“队头”。当线性表中没有元素时，称为“空队”。特点：先进先出（FIFO）。

规定一：front指向队头元素的前一个位置；rear指向队尾元素所在位置。

规定二：front指向队头元素的位置；rear指向队尾元素的下一个位置。

        在队列操作过程中，为了提高效率，以调整指针代替队列元素的移动，并将数组作为循环队列的操作空间。

       为了区别空队和满队，满队元素个数比数组元素个数少一个。

两个规定二选其一遵守，要么遵守一，要么遵守二。

顺序队列的优缺点：

优点

  1. 存储效率高：

           顺序队列使用连续的内存空间，内存利用率较高，不会有像链表那样的指针开销。

  2. 访问速度快：

           由于元素在内存中是连续存储的，顺序队列在访问元素时具有较高的缓存命中率，因此访问速度较快。

  3. 实现简单：

           顺序队列的实现相对简单，通常只需要一个数组和两个指针（front 和 rear）来管理队列的头和尾。

  4. 空间预分配：

           可以在创建队列时预先分配一个固定大小的数组，避免了在队列动态增长时频繁的内存分配和释放操作。

缺点

  1. 固定大小：

           顺序队列的大小在创建时是固定的，如果队列满了，就不能再插入新元素，除非进行额外的扩容操作。扩容操作通常涉及复制整个数组到新的内存空间，这可能导致性能下降。

  2. 假溢出：

           在顺序队列中，即使数组还有空闲空间，如果所有的空间都在队列的前面（已经被已删除的元素占用），但后面的空间还未使用，也会导致队列无法插入新元素，这就是所谓的“假溢出”问题。

  3. 内存碎片：

           在频繁的插入和删除操作后，顺序队列可能会产生内存碎片，导致内存使用效率下降。虽然这通常不是主要问题，但在某些情况下需要考虑。

  4. 扩展性较差：

           如果队列的大小需要频繁变化，顺序队列的扩展性较差。相比之下，链表实现的队列（如链式队列）在动态扩展方面更具优势。

顺序队列

下面以遵守规则二为例来编写代码：

#ifndef _SEQQUEUE_H
#define _SEQQUEUE_H

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

typedef char Type;
#define LEN 10
//约定1：LEN-1号下标的下一个为0号下标
//约定2：数组少存一个数据，最多只存LEN-1个元素
typedef struct{
    Type data[LEN];   //队列空间
    int front;        //队头的下标
    int rear;         //队尾下标+1
}queue;

//创建
queue *create_queue();
//判空 空为0非空为1
int empty_queue(queue *q);
//判满 满为0不满为1
int full_queue(queue *q);
//入队enqueue
void enter_queue(queue *q,Type data);
//出队dequeue
Type delete_queue(queue *q);
//初始化
void init_queue(queue *q);
//回收
void free_queue(queue **q);

#endif

       顺序队列同样是使用数组来存储队列中的元素，结构体里有三个成员，一个是存放队列元素的数组，另外两个是队列数组两个下标；数组的长度用一个宏定义的LEN来代表，之后要修改队列长度直接修改宏定义即可。

#include "seqqueue.h"

//创建
queue *create_queue()
{
    queue *q = (queue *)malloc(sizeof(queue));
    if(NULL == q)
    {
        perror("create queue malloc");
        return NULL;
    }
    q->front = q->rear = 0;
    return q;
}
//判空 空为0,非空为1
int empty_queue(queue *q)
{
    if(NULL == q)
    {
        puts("queue is NULL");
        return -1;
    }
    if(q->front == q->rear)
    {
        puts("queue is empty");
        return 0;
    }
    else
        return 1;
}
//判满 满为0,不满为1
int full_queue(queue *q)
{
    if(NULL == q)
    {
        puts("queue is NULL");
        return -1;
    }
    if(q->front == (q->rear+1)%LEN)
    {
        puts("queue is full");
        return 0;
    }
    else
        return 1;
}
//入队enqueue
void enter_queue(queue *q,Type data)
{
    if(1 == full_queue(q))
    {
#if 1
        q->rear = q->rear%LEN; //让10变为0
        q->data[q->rear] = data;
        q->rear++;
#else
        q->data[q->rear] = data;
        q->rear = (q->rear+1)%LEN;
#endif
    }
}
//出队dequeue
Type delete_queue(queue *q)
{
    if(1 == empty_queue(q))
    {
        Type t = q->data[q->front];
        q->front = (q->front+1)%LEN;
        return t;
    }
}
//初始化
void init_queue(queue *q)
{
    if(NULL == q)
    {
        puts("queue is NULL");
        return;
    }
    q->rear = q->front;
}
//回收
void free_queue(queue **q)
{
    if(NULL == *q)
    {
        puts("queue is NULL");
        return;
    }
    free(*q);
    *q = NULL;
}

创建： queue *create_queue()

       在创建顺序队列的时候也是在堆区开辟空间，在这里一开始队列为空，所以这时候尾的下标应该为-1，头的下标为0，但是我们规定rear为尾+1，因此在创建完结构体之后，给front和rear都赋值为0即可。

判空：int empty_queue(queue *q)

       在前面的分析中我们已经知道了队列为空的时候front和rear的值应该相同，因此在这里只需要判断结构体里的front和rear是否相等就能判断队列是否为空，空函数返回0，非空函数返回1。

判满：int full_queue(queue *q)

       在判满这里分析中也提到了，为了避免判空和判满发生冲突，所以数组最多存储LEN-1个元素，但是除此之外，为了提高利用率，我们把数组作为循环队列来操作；在这里就会出现一个问题，那就是当队列放满，数据存储刚好到数组倒数第二位时，rear指向的就是数组最后一个元素的位置，这时rear+1就会超出数组下标的范围，此时front为数组第一个元素的下标，所以为了让rear+1与front相等，我们对rear+1进行除以LEN取余操作，这样当rear+1=LEN时，取余正好为0，就是第一个元素的下标；故判满的条件就为(q->front == (q->rear+1)%LEN。

入队：void enter_queue(queue *q,Type data)

       入队是在队尾的位置进行操作，也就是下标为rear的位置，但是在入队操作之前我们需要做一个判断，如果队列是满的那就不能再进行入队操作，只有队列不满才能进行入队操作；在入队之前我们需要保证rear的值不超过LEN-1，也就是当数组最后一个位置放满尾就应该移动到数组开头，所以在这里就先让rear取余LEN，再把data放入队列，最后让rear往后移动一位即可。

出队：Type delete_queue(queue *q)

       出队我们需要拿到出队的这个成员的值，因此函数返回值为Type类型，出队之前同样也需要进行一个判断，如果队列是空的，那就不能进行出队操作；当队列非空时，操作队头进行出队操作，将要出队的元素用一个变量t保存，然后让队头下标front往后移动一位，在这里为了防止超出数组操作范围，也需要对front进行取余，保证它在0~9之间；最后再将t返回即可。

初始化：void init_queue(queue *q)

       初始化的意思也就是将队列恢复到最开始空的时候，对于顺序队列，它为空的时候是front=rear，因为是数组，因此赋值可以覆盖，所以初始化我们只需要让结构体里的队头下标front和rear相等即可，这样队列相当于就是空队列，后续赋值会直接覆盖，不会造成别的影响。

回收：void free_queue(queue **q)

       在这里传参同样需要传指针的地址，因为存数据的数组在结构体里面，故在回收的时候不需要进行初始化，直接将结构体空间回收，再将指针指向NULL即可。

测试（主函数）

#include "seqqueue.h"
int main(int agrc,char *agrv[])
{
    queue *q = create_queue();
    printf("空为0：%d\n",empty_queue(q));
    puts("A，B，C，D入队");
    enter_queue(q,'A');
    enter_queue(q,'B');
    enter_queue(q,'C');
    enter_queue(q,'D');

    puts("出队");
    printf("%c\n",delete_queue(q));
    printf("%c\n",delete_queue(q));

    printf("判空：%d\n",empty_queue(q));

    puts("初始化");
    init_queue(q);
    printf("判空：%d\n",empty_queue(q));

    puts("回收");
    free_queue(&q);
    printf("%p\n",q);
    return 0;
}


http://www.kler.cn/a/409164.html

相关文章：

  • 【Spiffo】环境配置：VScode+Windows开发环境
  • JS精进之Hoisting（提升）
  • HTML5好看的音乐播放器多种风格(附源码)
  • 微机原理与接口技术——可编定时器，计数芯片8253.8254
  • 2024强网拟态决赛-eBeepf
  • 【Ubuntu24.04】服务部署（Docker）
  • pytorch torch.sign() 方法介绍
  • CTF之密码学（培根密码）
  • SpringBoot集成多个rabbitmq
  • 安宝特方案 | AR助力紧急救援，科技守卫生命每一刻！
  • C++结构型设计模式之桥接模式
  • C# 数据结构之【树】C#树
  • 显示类控件
  • 深度学习中的长短期记忆网络（LSTM）与自然语言处理
  • [AutoSar]BSW_Diagnostic_007 BootLoader 跳转及APP OR boot response 实现
  • 数据结构 ——— 直接选择排序算法的实现
  • springboot 使用笔记
  • selinux及防火墙
  • 力扣11.22
  • 【SSMS】【数据库】还原数据库
  • Scala的Array和ArrayBuffer集合及多维数组
  • 数据库、数据仓库、数据湖、数据中台、湖仓一体的概念和区别
  • Mac下的vscode远程ssh免密码登录
  • 【CVE-2024-9413】SCP-Firmware漏洞：安全通告
  • 【LLM训练】从零训练一个大模型有哪几个核心步骤？
  • 重装系统后ip地址错误，网络无法接通怎么办