专栏首页huiC语言实现顺序队列

C语言实现顺序队列

文章目录
  • 顺序队列常规操作
  • 定义顺序队列结构体
  • 初始化顺序队列
  • 顺序队列判满
  • 顺序队列判空
  • 计算顺序队列的长度
  • 顺序队列入队(EnQueue)
  • 顺序队列出队(DeQueue)
  • 顺序队列各操作测试
  • 源代码

顺序队列常规操作

/********************* 顺序队列的常规操作 *************************/

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

/****************************************************************/

定义顺序队列结构体

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

#define TRUE  1
#define FALSE 0
#define MAXSIZE 10      // 队列最大的存储量

typedef int ElemType;


// 定义顺序队列结构体
typedef struct SeQueue{
    ElemType *base; // 队列首地址
    int front;      // 队列头下标
    int rear;       // 队列尾下标
}*Queue;

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

为了在C语言中描述方便起见,初始化建空队列时,令 front = rear = 0;

每当插入新的队尾元素时 “尾指针增1”;每当删除队头元素时 “头指针增1”

因此,在非空队列中,头指针始终指向队列头元素,而尾指针始终指向队列尾元素的下一个位置

初始化顺序队列

/*
 *  初始化顺序队列
*/
Queue InitSeQueue(){
    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;
    }
    // 判断队列尾下标是否超过最大容量
    if(q -> rear >= MAXSIZE){
        return TRUE;
    }
    return FALSE;
}

顺序队列判空

/*
 *  顺序队列判空
 *  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;
}

顺序队列入队(EnQueue)

/*
 *  入队
 *  q 顺序队列
 *  data 入队元素
*/
int EnQueue(Queue q, ElemType data){
    // 队列判满
    if(QueueFull(q)){
        return FALSE;
    }
    // 把元素插入队尾
    q -> base[q -> rear] = data;    
    q -> rear++;
    return TRUE;
}

顺序队列出队(DeQueue)

/*
 *  出队  
 *  q 顺序队列
 *  *val 用来存出队元素的数据 
*/
int DeQueue(Queue q, ElemType *val){
    // 队列判空
    if(QueueEmpty(q)){
        return FALSE;
    }
    // 把队头元素取出来并利用指针返回去
    *val = q -> base[q -> front];
    q -> front ++;
    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 = InitSeQueue();
    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));

    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():10

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

EnQueue(20): 0  (0 Failed, 1 Success)

QueueFull():1EnQueue(20): 0 可以看出顺序队列存在假溢出(实际可用空间并未占满,却不能进行入队操作)

例如:

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

循环队列 就可以解决假溢出情况。

源代码

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

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 数据结构 - 栈和队列

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

    忆想不到的晖
  • C语言实现循环队列

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

    忆想不到的晖
  • 顺序表与链表的比较

    结点的数据域a1占8个字节,地址域占4个字节,所以存储密度 = 8 / 12 = 67%

    忆想不到的晖
  • leetcode栈之用队列实现栈

    这里使用了两个LinkedList,在push的时候,offer到a队列,然后再将b队列的元素offer到a队列,再交换a、b队列;pop、top、empty的...

    codecraft
  • 三分钟基础:什么是队列?

    像线程池、异步队列、消息队列等有限的资源容器中,往往存储大量的任务事件,这些大量的任务事件需要进行有条理的进行任务分发以及各种情况处理,为了能够使得资源容器的正...

    帅地
  • 【FreeRTOS】队列管理2

    创建一个队列用于保存类型为xData 的结构体数据单元。结构体成员包括了一个数据值和表示数据含义的编码,两者合为一个消息可以一次性发送到队列。 ? 中央控...

    心跳包
  • 【FreeRTos】队列管理1

    写队列任务在每次循环中都调用taskYIELD()。taskYIELD()通知调度器立即进行任务切换,而不必等到当前任务的时间片耗尽。某个任务调用taskY...

    心跳包
  • CKafka系列学习文章 - 什么是消息队列 ?(一)

    | 导语 在大家的工作当中,是否碰到大量的插入、更新请求同时到达数据库,这会导致行或表被锁住,最后会因为请求堆积过多而触发“连接数过多的异常”(Too Man...

    发哥说消息队列
  • IBM MQ运维使用手册

    操作系统版本:SUSE Linux Enterprise Server 10 SP4    32bit

    loong576
  • Java队列学习第一篇之列介绍

    队列大家都知道,但是在Java中队列分哪几种呢?清楚吗?都有哪些地方用到了队列呢?最常用的场景的就是消息中间件,比如各种MQ都是使用的队列来的。如果没有用过消息...

    凯哥Java

扫码关注云+社区

领取腾讯云代金券