数据结构之循环队列C语言实现(详细)[通俗易懂]

数据结构之循环队列C语言实现(详细)[通俗易懂]队列的一些说明队列的定义队列,一种特殊的线性表特点:只允许在一端输入,在另一端输出。输入端称为队尾,输出端称为队头因此,队列,又称为先进先出表(FIFO),类似于生活中的排队,先来的排在前头,后来的排在后头,一个一个办理业务。队列有两种,一种叫做循环队列(顺序队列),另一种叫做链式队列。这一篇讲的是循环队列,链式队列在另外一篇文章中循环数组循环队列使用的是数组,但是这个数组比较特别,为循环数组。为什么要使用循环数组呢?可以想象一下,假如我们使用通常的数组。那么在使用过程中,我们是从后面加

大家好,又见面了,我是你们的朋友全栈君。

队列的一些说明

队列的定义

队列,一种特殊的线性表

特点:只允许在一端输入,在另一端输出。输入端称为队尾,输出端称为队头

因此,队列,又称为先进先出表(FIFO),类似于生活中的排队,先来的排在前头,后来的排在后头,一个一个办理业务。

队列有两种,一种叫做循环队列(顺序队列),另一种叫做链式队列。

这一篇讲的是循环队列,链式队列在另外一篇文章中

链式队列讲解与C++实现

循环数组

循环队列使用的是数组,但是这个数组比较特别,为循环数组。为什么要使用循环数组呢?

可以想象一下,假如我们使用通常的数组。

那么在使用过程中,我们是从后面加入数据,从前面移除数据。那么随着出队和入队的进行,数组会整体向右平移,因为数组前面的元素因为出队变成了空白,变得不可使用。造成空间的浪费。

如果每出队一次,都将数组向左平移一次,又会很麻烦,造成时间上的浪费。综上,我们使用循环队列,就是将队首和队尾黏在一起。类似于一个⚪;
循环数据
那么知道了循环数组后,我们应该考虑下,队首和队尾怎么放置,才能使我们循环队列能够使用。

不同的队首和队尾的初始化,将导致我们判断队列是否已满以及队列是否为空的方法的不同

(1)front(队首)和rear(队尾)初始化均为0。那么,在这种情况下,front会永远指向队首元素,而rear会指向队尾元素的下一格。
(2)front(队首)和rear(队尾)错开。比如 front 初始为0,rear初始为5。在这种情况下front会永远指向队首元素,rear会永远指向队尾元素。

因此,在判断队列是否已满与非空时,初始化不同,判断方式不同。或者干脆就不用front与rear的位置来判断队列是否已满与非空。多加一个参数Size,表示队列的现有容积也行。

另外,如何在代码实现过程中将正常数组变成循环数组呢?

很简单,取余即可

C语言实现循环队列

定义结构体

struct Queue{ 
    //结构体 
 int *data;   
 int capacity; //最大容积 
 int front;  //表头 
 int rear;  //表尾 
 //int size; //size表示队列的现有容量, 
};

队列的初始化

void init(struct Queue *pq,int capacity){ 
    //队列的初始化 
 pq->capacity=capacity;
 pq->data=(int*)malloc(sizeof(int)*(capacity+1));
 pq->front = 0;  //初始化的不同,会导致后面判断队列是否为空以及是否已满的不同 
 pq->rear = 0;
}

判断队列是否已满

int isFull(const struct Queue *pq){ 
     //判断队列是否已满
 if((pq->rear + 1)%(pq->capacity+1) == pq->front) return 1;
 else return 0;
}

判断队列是否为空

int isEmpty(const struct Queue *pq){ 
    //判断是否为空 
 return pq->front == pq->rear;
}

入队操作,x表示插入的元素

int enQueue(struct Queue *pq,int x){ 
    //入队操作 
 if(isFull(pq)) return 0;
 else{ 
   
  pq->data[pq->rear] = x;
  pq->rear = (pq->rear+1) % (pq->capacity+1);
  return 1;  //成功返回1,失败返回0 
 } 
}

出队操作,同时返回出队的值给px

int deQueue(struct Queue *pq,int *px){ 
     //出队操作 
 if(isEmpty(pq)) return 0;
 else { 
   
  *px = pq->data[pq->front];
  pq->front = (pq->front+1) % (pq->capacity+1);
  return 1;  //成功返回1,失败返回0 
 }
}

完整代码

#include<stdio.h>
#include<stdlib.h>
using namespace std;
//循环队列 
struct Queue{ 
    //结构体 
 int *data;   
 int capacity; //最大容积 
 int front;  //表头 
 int rear;  //表尾 
 //int size; //size表示队列的现有容量, 
};

void init(struct Queue *pq,int capacity){ 
    //队列的初始化 
 pq->capacity=capacity;
 pq->data=(int*)malloc(sizeof(int)*(capacity+1));
 pq->front = 0;  //初始化的不同,会导致后面判断队列是否为空以及是否已满的不同 
 pq->rear = 0;
}

int isFull(const struct Queue *pq){ 
     //判断队列是否已满
 if((pq->rear + 1)%(pq->capacity+1) == pq->front) return 1;
 else return 0;
}

int isEmpty(const struct Queue *pq){ 
    //判断是否为空 
 return pq->front == pq->rear;
}

int enQueue(struct Queue *pq,int x){ 
    //入队操作 
 if(isFull(pq)) return 0;
 else{ 
   
  pq->data[pq->rear] = x;
  pq->rear = (pq->rear+1) % (pq->capacity+1);
  return 1;  //成功返回1,失败返回0 
 } 
}

int deQueue(struct Queue *pq,int *px){ 
     //出队操作 
 if(isEmpty(pq)) return 0;
 else { 
   
  *px = pq->data[pq->front];
  pq->front = (pq->front+1) % (pq->capacity+1);
  return 1;  //成功返回1,失败返回0 
 }
}

int main()
{ 
   
 struct Queue q; 
 init(&q,4);
 enQueue(&q,11);
 enQueue(&q,22);
 enQueue(&q,33);
 enQueue(&q,44);
 enQueue(&q,55);
 
 int x;
 deQueue(&q,&x);
 printf("%d\n",x);
  deQueue(&q,&x);
 printf("%d\n",x);
  deQueue(&q,&x);
 printf("%d\n",x);
  deQueue(&q,&x);
 printf("%d\n",x);
  deQueue(&q,&x);
 printf("%d\n",x);
} 
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/140889.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • vue(21)初识Vuex[通俗易懂]

    vue(21)初识Vuex[通俗易懂]Vuex是做什么的?官方解释:Vuex是一个专为Vue.js应用程序开发的状态管理模式。它采用集中式存储管理应用的所有组件的状态,并以相应的规则保证状态以一种可预测的方式发生变化。Vuex

  • random函数的用法

    random函数的用法用法:1、random.random()随机生成(0,1)之间的浮点数2、random.randint(上限,下限)随机生成在范围之内的整数,两个参数分别表示上限和下限3、random.randrange(,,)在指定范围内,按指定基数递增的集合中获得一个随机数,有三个参数,前两个参数代表范围上限和下限,第三个参数是递增增量,不包括下限,包括上限使用方式如下:random.r…

  • java 单例模式实现的5种方式[通俗易懂]

    java 单例模式实现的5种方式[通俗易懂]第一种:饿汉式/***CreatedwithIntelliJIDEA.**@author:宸濯*Date:2021/08/188:21*Description:单例模式的设计(饿汉式)*1.构造方法私有化*2.在静态语句块实例化*3.提供调用实例对象的方法*4.空间换时间,不管有没有调用方法,实例都创建了*Version:V1.0*/publicclassSingletonOne{privatestatic

  • preference用法for_interference用法

    preference用法for_interference用法文章目录PreferenceFragment简介PreferenceFragment使用PreferenceFragment扩展PreferenceFragment简介在我们写一个项目的时候,基本都有选项设置界面,这类设置界面的原理基本都是本地的一些个性化设置,通过读取本地设置来改变某些差异显示(例如字体大小,主题颜色,WIFI自动下载等)。这些设置一般都会使用Preference来保存,…

  • JMH是什么?

    JMH是什么?一、JMH是什么?JMH是Java性能测试工具,主要是对工程中一些方法进行一些基准测试,支持的时间单位为:nano/micro/milli/macro二、JMH使用案例-代码:1P

  • php集成环境和自己配置的区别,php集成环境、php绿色集成环境、php独立安装版环境这三者的区别

    php集成环境和自己配置的区别,php集成环境、php绿色集成环境、php独立安装版环境这三者的区别php集成环境和自己配置的区别?PHP绿色集成环境和自己安装的有什么区别吗?PHP集成环境与安装版的区别?php集成环境、php绿色集成环境、php独立安装版环境这三者的区别

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号