C语言数据结构算法基础之循环队列示例

目录
  • 说明
  • 示例代码
    • 1. 首先定义结构体：
    • 2. 定义各种算法：
    • 3. 测试：
    • 4. 最后的结果：

说明

循环队列是一种先进先出的，首尾相连的队列。

大致的结构如下图：

用数组来抽象的表示一下的话，如下图：

循环队列有两个指针指向数据，上图中的start和end就是那两个指针，它们指向相同的位置，表示的是空，即队列是空的。

随着数据的放入，队列一般有下面的两种形式：

需要注意第二种形式，从图上看end在start的前面了，但是因为循环关系，前后并不重要。

另外需要考虑的是队列满的情况：

但这种情况存在一个问题，即空队列和满队列没有办法区分了，end和start都指向了相同的位置。

为了解决这个问题，一个方法是空出一个位置不放数据，当end再加一个数据就等于start的时候就认为队列是满的：

这时实际的数据长度就会比分配的少1。

下面是队列中空和满的判断：

1. 队列为空时：end == start

2. 队列为满时：(end + 1) % size == start

这里的size是指分配的空间大小，而不是队列长度，队列的实际长度为(end - start + size) % size，最大长度是size-1

这也是因为要考虑循环的关系，所以要加上%size这个操作。

示例代码

1. 首先定义结构体：

//定义循环队列
typedef struct _LoopQueue {
	int data[8];		//存放数据
	int start;		//头指针
	int end;		//尾指针
} LoopQueue;

2. 定义各种算法：

#define TRUE	1
#define FALSE	0
#define SIZE	8
//初始化队列
int init(LoopQueue *lq) {
	lq->start = 0;
	lq->end = 0;
	return TRUE;
}
//判断队列是否为空
int isEmpty(LoopQueue *lq) {
	if (lq->start == lq->end) {
		return TRUE;
	}
	return FALSE;
}
//判断队列是否为满
int isFull(LoopQueue *lq) {
	if ((lq->end + 1) % SIZE == lq->start) {
		return TRUE;
	}
	return FALSE;
}
//获取队列的长度
int getLength(LoopQueue *lq) {
	return (lq->end - lq->start + SIZE) % SIZE;
}
//插入数据
int pushQueue(LoopQueue *lq, int data) {
	if(isFull(lq)) {
		printf("Queue is full.\n");
		return FALSE;
	}
	lq->data[lq->end] = data;
	lq->end = (lq->end + 1) % SIZE;
	return TRUE;
}
//弹出数据
int popQueue(LoopQueue *lq, int *data) {
	if (isEmpty(lq)) {
		printf("Queue is empty.\n");
		return FALSE;
	}
	*data = lq->data[lq->start];
	lq->start = (lq->start + 1) % SIZE;
	return TRUE;
}
//显示队列中的数据
void printQueue(LoopQueue *lq) {
	int index;
	int count;
	count = getLength(lq);
	if (0 == count) {
		printf("No data.\n");
		return;
	}
	for (index = 0; index < count; index++) {
		printf("%d ", lq->data[index]);
	}
	printf("\n");
	return;
}

3. 测试：

int main()
{
	int index;
	int num;
	//队列测试代码
	LoopQueue *lq = (LoopQueue *)malloc(sizeof(LoopQueue));
	init(lq);
	printQueue(lq);
	for (index = 0; index < SIZE; index ++) {	//注意这里要放8个数据，但是实际上只能放7个，所以最后一个会报错
		pushQueue(lq, index);
	}
	printQueue(lq);
	for (index = 0; index < SIZE; index ++) {	//同上，会打印一个错误
		if (popQueue(lq, &num)) {
			printf("%d\n", num);
		}
	}
	printQueue(lq);
	return 0;
}

4. 最后的结果：

以上就是C语言数据结构算法基础之循环队列的详细内容，更多关于C语言数据结构算法循环队列的资料请关注我们其它相关文章！

赞 (0)

相关推荐

  • C语言详解链式队列与循环队列的实现

    C语言详解链式队列与循环队列的实现

    目录 队列的实现 链式队列 链式队列的定义 链式队列的实现 循环队列 循环队列的定义 循环队列的实现 队列的实现 队列是一种先进先出(First in First Out)的线性表,简称FIFO.与栈不同,栈是一种后进先出(先进后出)的线性表.在队列中,允许插入的一端称为队尾,允许删除的一端称为队头.假设队列是q=(a1,a2,…,an),那么a1就是队头元素,而an是队尾元素.这样我们就可以删除时,总是从a1开始,而插入时,列在最后.这也比较符合我们通常生活中的习惯,排在第一个的优先出列,最后

  • C语言实现循环队列

    本文实例为大家分享了C语言实现循环队列的具体代码,供大家参考,具体内容如下 注意事项: 1.循环队列,是队列的顺序表示和实现.因为是尾进头出,所以和顺序栈不同的是需要将顺序队列臆造成一个环状的空间,以便在尾部添加满之后从头部空位开始插入. 2.也可以使用数组队列,也就是不能动态增长的顺序队列,这样不需要每次取模最大值来构成环形空间.每次插入新的队列尾元素时,尾指针增1,每当删除队列头元素时,头指针增1. 3.尾指针会出现在头指针之前,由此特性,循环队列在无法预估使用大小时,不宜使用. 4.在每一

  • C语言循环队列与用队列实现栈问题解析

    C语言循环队列与用队列实现栈问题解析

    目录 “莫听穿林打叶声,何妨吟啸且徐行” 这里是目录 循环队列题目描述题目链接思路分析代码实现 用队列实现栈题目描述题目链接思路分析代码实现 循环队列 循环队列: 循环队列是一种线性数据结构,其操作表现基于 FIFO(先进先出)原则并且队尾被连接在队首之后以形成一个循环循环队列的好处:可以重新利用队列的空间.我们可以利用这个队列之前用过的空间.在一个普通队列里,一旦一个队列满了,我们就不能插入下一个元素,即使在队列前面仍有空间.但是使用循环队列,我们能使用这些空间去存储新的值. 题目描述 设计你

  • C语言实现循环队列基本操作

    C语言实现循环队列基本操作

    循环队列依靠取模运算,实现队列中数据元素的逻辑成环操作.其相比队列的顺序存储实现,可以避免"假溢出"的问题. 头文件声明 #include <stdio.h> #include <stdlib.h> /* * 循环队列实现 */ //数据元素上限 #define MaxSize 50 //定义数据类型 typedef int ElemType; /*结构体定义*/ typedef struct SqQueue { ElemType data[MaxSize];/

  • C语言实现顺序循环队列实例

    C语言实现顺序循环队列实例

    目录 一.队列和循环队列基本概念 二.代码实操 总结 一.队列和循环队列基本概念 队列: 和栈相反,队列是一种先进先出(FIFO)的线性表.只允许在一端插入,在另一端删除. 允许插入的叫"队尾"(rear),允许删除的叫"队头"(front). 入队操作:L->rear++;   L->data[L->rear]=x;(需要入队的元素) 出队操作:L->front++;  x=L->data[L->front]; 求队长:队长=(

  • C语言数据结构算法基础之循环队列示例

    C语言数据结构算法基础之循环队列示例

    目录 说明 示例代码 1. 首先定义结构体: 2. 定义各种算法: 3. 测试: 4. 最后的结果: 说明 循环队列是一种先进先出的,首尾相连的队列. 大致的结构如下图: 用数组来抽象的表示一下的话,如下图: 循环队列有两个指针指向数据,上图中的start和end就是那两个指针,它们指向相同的位置,表示的是空,即队列是空的. 随着数据的放入,队列一般有下面的两种形式: 需要注意第二种形式,从图上看end在start的前面了,但是因为循环关系,前后并不重要. 另外需要考虑的是队列满的情况: 但这种

  • java数据结构与算法之双向循环队列的数组实现方法

    本文实例讲述了java数据结构与算法之双向循环队列的数组实现方法.分享给大家供大家参考,具体如下: 需要说明的是此算法我并没有测试过,这里给出的相当于伪代码的算法思想,所以只能用来作为参考! package source; public class Deque { private int maxSize; private int left; private int right; private int nItems; private long[] myDeque; //constructor p

  • JavaScript数据结构之优先队列与循环队列实例详解

    JavaScript数据结构之优先队列与循环队列实例详解

    本文实例讲述了JavaScript数据结构之优先队列与循环队列.分享给大家供大家参考,具体如下: 优先队列 实现一个优先队列:设置优先级,然后在正确的位置添加元素. 我们这里实现的是最小优先队列,优先级的值小(优先级高)的元素被放置在队列前面. //创建一个类来表示优先队列 function Priorityqueue(){ var items=[];//保存队列里的元素 function QueueEle(e,p){//元素节点,有两个属性 this.element=e;//值 this.pr

  • C语言数据结构算法之实现快速傅立叶变换

    C语言数据结构算法之实现快速傅立叶变换 本实例将实现二维快速傅立叶变换,同时也将借此实例学习用c语言实现矩阵的基本操作.复数的基本掾作,复习所学过的动态内存分配.文件操作.结构指针的函数调用等内容. 很久以来,傅立叶变换一直是许多领域,如线性系统.光学.概率论.量子物理.天线.数字图像处理和信号分析等的一个基本分析工具,但是即便使用计算速度惊人的计算机计算离散傅立叶变换所花费的时间也常常是难以接受的,因此导致了快速傅立叶变换(FFT)的产生. 本实例将对一个二维数组进行正.反快速傅立叶变换.正傅

  • C语言数据结构进阶之栈和队列的实现

    C语言数据结构进阶之栈和队列的实现

    目录 栈的实现: 一.栈的概念和性质 二.栈的实现思路 三.栈的相关变量内存布局图 四.栈的初始化和销毁 五.栈的接口实现: 1.入栈 2.出栈 3.获取栈顶的数据 4.获取栈的元素个数 5.判断栈是否为空 队列的实现: 一.队列的概念和性质 二.队列的实现思路 三.队列相关变量的内存布局图 四.队列的初始化和销毁 五.队列的接口实现: 1. 入数据 2.出数据 3.取队头数据 4.取队尾数据 5.获取队列元素个数 6.判断队列是否为空 总结 栈的实现: 一.栈的概念和性质 栈(stack)又名

  • java数组实现循环队列示例介绍

    java数组实现循环队列示例介绍

    从顶部进去数据,从底部出来数据,用数组实现队列,但是下面这个队列,只能进行一次存数值,取数值,不够完善. import java.util.Scanner; public class ArrayQueueDemo { public static void main(String[]args){ //定义队列大小maxsize ArrayQueue arrayQueue=new ArrayQueue(3); Scanner scanner=new Scanner(System.in); char

  • Java数据结构与算法之循环队列的实现

    Java数据结构与算法之循环队列的实现

    目录 概述 循环队列 循环队列实现 改变队列大小 enqueue 方法 dequeue 方法 main 完整代码  概述 从今天开始, 小白我将带大家开启 Jave 数据结构 & 算法的新篇章. 循环队列 循环队列 (Circular Queue) 是一种特殊的队列. 循环队列解决了队列出队时需要将所有数据前移一位 (复杂度为 O(n)) 的问题. 循环队列的底层依然是数组, 不过增加了指向头和尾的指针. 循环队列实现 判断队列是否为空: 当头指针 Q.front == 尾指针 Q.rear,

  • 详解数据结构C语言实现之循环队列

    详解数据结构C语言实现之循环队列

    本文讲的是循环队列,首先我们必须明白下面几个问题 循环队列的基础知识 1.循环队列需要几个参数来确定 循环队列需要2个参数,front和rear 2.循环队列各个参数的含义 (1)队列初始化时,front和rear值都为零: (2)当队列不为空时,front指向队列的第一个元素,rear指向队列最后一个元素的下一个位置: (3)当队列为空时,front与rear的值相等,但不一定为零: 3.循环队列入队的伪算法 (1)把值存在rear所在的位置: (2)rear=(rear+1)%maxsize

  • C语言数据结构与算法时间空间复杂度基础实践

    C语言数据结构与算法时间空间复杂度基础实践

    目录 小感想 时间复杂度 空间复杂度 小感想 今天去看了看许多人今年去各个大厂面试的面经,确实如大体所说,各大公司越来越注重性能迭代,时代需要数据结构与算法这样的考试. 一个公司的成本主要来自于人力成本,但是上了规模写核心代码的人少了,成本就会来自于机器,资源,时间,抢占到这些就相当于无时无刻在减少客户流失.所以同样一段代码给两个人写,甲拿 8000,乙拿 25000,但是后者效率提高了50%,而这50%带来的收益远远超过了(25000-8000),这就是为什么许多大厂要给出如此吸引人的高薪资来

  • C语言算法积累加tag的循环队列

    题目: 若希望循环队列中的元素都能得到利用,则需设置一个标志域tag,并以tag的值为0或1来区分队头指针front和队尾指针rear相同时的队列状态是“空”还是“满”. 试编写与此结构相应的入队和出队算法. 关键字: 循环队列+tag的使用 思路 : 循环队列: 需要变量:队头指针front,队尾指针rear,增减元素的开关:tag 1)入队算法 尾插法:Q.data[Q.rear]=x;Q.rear=(Q.rear+1)%Maxsize;Q.tag=1 队空条件:Q.front== Q.re

随机推荐