循环队列详解及队列的顺序表示和实现

循环队列——队列的顺序表示和实现

前面分析顺序队的时候,我们知道,顺序队存在”假溢出”的问题,这个问题有时会造成很大的内存浪费,循环队列就是为了解决这个问题而提出地一个很巧妙的办法.循环队列和顺序队列的主要区别在于:循环队列将顺序队列臆造成一个环状空间.在操作上这种异同体现在:

相同点:

在顺序队列和循环队列中,进行出队、入队操作时,队首、队尾指针都要加 1 ,朝前移动。

不同点:

1. 在循环队列中当队首、队尾指针指向向量上界(MAX_QUEUE_SIZE-1) 时,其加1 操作的结果是指向向量的下界 0 。而在顺序队列中,说明队已满,若此时采用的是动态顺序链,可以增加申请内存.若是采用静态顺序链,只能退出程序.

2. 顺序队列中q.front = q.rear 表示队空,q.rear = MAX_QUEUE_SIZE表示队满.而在循环队列中.front=q.rear表示队空,而无法用.rear=MAX_QUEUE_SIZE表示队满.

判断循环队列队满的两种方法(本文采用第二种方法):

1.另设一个标志位以区分队列是空还是满

2.少用一个元素空间,约定以”队列头指针在队列尾指针的下一位置上”,作为队列呈满状态的标志.

第二种方法的实现:

◆ rear 所指的单元始终为空。
◆ 循环队列为空: front=rear 。
◆ 循环队列满: (rear+1)%MAX_QUEUE_SIZE=front 。

循环队列操作及指针变化情况如下图所示:

循环队列虽然可以解决”假溢出”问题,但是它不能通过动态分配的一维数组来实现,所以在实现循环队列之前,一定要为它设定一个最大队列长度.如果无法预估所需的最大队列长度,只能采用来链表实现.

代码实现:

循环队列和顺序队列的头文件是一样的

/* 循环队列的接口定义头文件 */
#define true 1
#define false 0

/* 队的最大长度 */
#define MAX_QUEUE_SIZE 6
/* 队列的数据类型 */
typedef int datatype;

/* 静态链的数据结构 */
typedef struct queue{
  datatype sp_queue_array[MAX_QUEUE_SIZE];
  /* 队头 */
  int front;
  /* 队尾 */
  int rear;
}cir_queue;

/* 静态顺序链的接口定义 */

/* 静态链的初始化 */
cir_queue queue_init();

/* 判断队列是否为空,若为空
 * 返回true
 * 否则返回false
*/
int queue_empty(cir_queue q);

/* 插入元素e为队q的队尾新元素
 * 插入成功返回true
 * 队满返回false
*/
int queue_en(cir_queue *q, datatype e);

/* 队头元素出队
 * 用e返回出队元素,并返回true
 * 若队空返回false
*/
int queue_de(cir_queue *q, datatype *e);

/* 清空队 */
void queue_clear(cir_queue *q);

/* 获得队头元素
 * 队列非空,用e返回队头元素,并返回true
 * 否则返回false
*/
int get_front(cir_queue, datatype *e );

/* 获得队长 */
int queue_len(cir_queue q);

/* 遍历队 */
void queue_traverse(cir_queue q, void(*visit)(cir_queue q));

void visit(cir_queue s);

/* 循环队列的接口实现文件 */
#include<stdio.h>
#include<stdlib.h>
#include"cir_queue.h"

cir_queue queue_init()
{
  cir_queue q;
  q.front = q. rear = 0;
  return q;
}

int queue_empty(cir_queue q)
{
  return q.front == q.rear;
}

int queue_en(cir_queue *q, datatype e)
{
  /* 判断队是否已满 */
  if (q -> front == (q -> rear + 1) % MAX_QUEUE_SIZE)
    return false;
  /* 入队 */
  q -> sp_queue_array[q -> rear] = e;
  q -> rear = (q -> rear + 1) % MAX_QUEUE_SIZE;
  return true;
}

int queue_de(cir_queue *q, datatype *e)
{
  /* 判断队列是否为空 */
  if(q -> front == q -> rear)
    return false;
  /* 用e返回队头元素 */

  *e = q -> sp_queue_array[q -> front];
  q -> front = (q -> front + 1 ) % MAX_QUEUE_SIZE;
  return true;
}

void queue_clear(cir_queue *q)
{
  q -> front = q -> rear = 0;
}

int get_front(cir_queue q, datatype *e)
{
  /* 判断队列是否为空 */
  if (q.front == q.rear)
    return false;
  *e = q.sp_queue_array[q.front];
  return true;
}

int queue_len(cir_queue q)
{
  /* 若front > rear */
  if(q.front > q.rear)
    return (q.rear + MAX_QUEUE_SIZE - q.front);
  else
    return (q.rear - q.front);
}

void queue_traverse(cir_queue q, void(*visit)(cir_queue q))
{
  visit(q);
}

void visit(cir_queue q)
{
  while(q.front != q.rear)
  {
    printf("%d ",q.sp_queue_array[q.front]);
    q.front = (q.front + 1) % MAX_QUEUE_SIZE;
  }
}

int main()
{
   cir_queue q = queue_init();
  queue_en(&q, 1);
  queue_en(&q, 2);
  queue_en(&q, 3);
  queue_en(&q, 4);
  queue_en(&q, 5);
  printf("此时队长:length=%d\n", queue_len(q));
  queue_traverse(q, visit);
  printf("元素6再入队\n");
  queue_en(&q, 6);
  queue_traverse(q, visit);
  datatype *x = (datatype *)malloc(sizeof(*x));
  queue_de(&q,x);
  printf("出队:%d,此时队长=%d\n", *x, queue_len(q));
  printf("元素6再入队\n");
  queue_en(&q, 6);
  printf("length=%d\n", queue_len(q));
  queue_traverse(q,visit);
  datatype *e = (datatype *)malloc(sizeof(*e));
  queue_de(&q,e);
  printf("queue_de(),e=%d length=%d\n", *e,  queue_len(q));
  queue_traverse(q, visit);
  queue_clear(&q);
  queue_traverse(q, visit);
  printf("length:%d\n", queue_len(q));
}

运行截图:

感谢阅读,希望能帮助到大家,谢谢大家对本站的支持!

(0)

相关推荐

  • C语言线性表的顺序表示与实现实例详解

    1.概述 通常来说顺序表是在计算机的内存中以数组的形式保存的线性表,是用一组地址连续的存储单元依次存储数据元素的线性数据结构.线性表采用顺序存储的方式存储就称之为顺序表.顺序表是将表中的结点依次存放在计算机内存中一组地址连续的存储单元中. 将表中元素一个接一个的存入一组连续的存储单元中,这种存储结构就是顺序结构. 采用顺序存储结构的线性表简称为" 顺序表".顺序表的存储特点是:只要确定了起始位置,表中任一元素的地址都通过下列公式得到:LOC(ai)=LOC(a1)+(i-1)*L 1≤

  • 利用C语言实现顺序表的实例操作

    本文实例讲述了C语言实现顺序表(线性表)的方法.分享给大家供大家参考,具体如下: 一:顺序表代码实现 #ifndef _SEQ_LIST_H #define _SEQ_LIST_H #include <stdio.h> #include <stdlib.h> #include <assert.h> #include <string.h> #define ElemType float //以float类型测试算法通用性,而不是以惯用的int #define I

  • 用C语言举例讲解数据结构中的算法复杂度结与顺序表

    数据结构算法复杂度 1.影响算法效率的主要因素 (1)算法采用的策略和方法: (2)问题的输入规模: (3)编译器所产生的代码: (4)计算机执行速度. 2.时间复杂度 // 时间复杂度:2n + 5 long sum1(int n) { long ret = 0; \\1 int* array = (int*)malloc(n * sizeof(int)); \\1 int i = 0; \\1 for(i=0; i<n; i++) \\n { array[i] = i + 1; } for(

  • C语言实现顺序表基本操作汇总

    本文汇总了C语言下实现及操作顺序表的方法,对于学习数据结构的朋友来说是一个不错的参考程序.完整代码如下: #include<stdio.h> #include<stdlib.h> #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define OVERFLOW -2 #define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 typedef int status ;

  • C语言顺序表实现代码排错

    今天本来想写段代码练练手,想法挺好结果,栽了个大跟头,在这个错误上徘徊了4个小时才解决,现在分享出来,给大家提个醒,先贴上代码: 复制代码 代码如下: /******************************************** * 文件名称:sqlist.h * 文件描述:线性表顺序存储演示 * 文件作者:by Wang.J,in 2013.11.16 * 文件版本:1.0 * 修改记录:*********************************************/

  • C++实现顺序表的方法

    废话不多说了,直接给大家上关键代码了. #pragma once #include <assert.h> template<class T> class SeqList { public: SeqList() :_a(NULL) ,_size(1) ,_capacity(1) {} SeqList(T* a, size_t size) :_a(new T[size]) ,_size(size) ,_capacity(size) { for (size_t i = 0; i <

  • C语言实现静态顺序表的实例详解

    C语言实现静态顺序表的实例详解 线性表 定义一张顺序表也就是在内存中开辟一段连续的存储空间,并给它一个名字进行标识.只有定义了一个顺序表,才能利用该顺序表存放数据元素,也才能对该顺序表进行各种操作. 接下来看看静态的顺序表,直接上代码: SeqList.h #define _CRT_SECURE_NO_WARNINGS 1 #ifndef __SEQLIST_H__ #define __SEQLIST_H__ #include <stdio.h> #include <stdlib.h&g

  • 循环队列详解及队列的顺序表示和实现

    循环队列--队列的顺序表示和实现 前面分析顺序队的时候,我们知道,顺序队存在"假溢出"的问题,这个问题有时会造成很大的内存浪费,循环队列就是为了解决这个问题而提出地一个很巧妙的办法.循环队列和顺序队列的主要区别在于:循环队列将顺序队列臆造成一个环状空间.在操作上这种异同体现在: 相同点: 在顺序队列和循环队列中,进行出队.入队操作时,队首.队尾指针都要加 1 ,朝前移动. 不同点: 1. 在循环队列中当队首.队尾指针指向向量上界(MAX_QUEUE_SIZE-1) 时,其加1 操作的结

  • Python数据结构之队列详解

    目录 0. 学习目标 1. 队列的基本概念 1.1 队列的基本概念 1.2 队列抽象数据类型 1.3 队列的应用场景 2. 队列的实现 2.1 顺序队列的实现 2.2 链队列的实现 2.3 队列的不同实现对比 3. 队列应用 3.1 顺序队列的应用 3.2 链队列的应用 3.3 利用队列基本操作实现复杂算法 0. 学习目标 栈和队列是在程序设计中常见的数据类型,从数据结构的角度来讲,栈和队列也是线性表,是操作受限的线性表,它们的基本操作是线性表操作的子集,但从数据类型的角度来讲,它们与线性表又有

  • c语言数据结构之栈和队列详解(Stack&Queue)

    目录 简介 栈 一.栈的基本概念 1.栈的定义 2.栈的常见基本操作 二.栈的顺序存储结构 1.栈的顺序存储 2.顺序栈的基本算法 3.共享栈(两栈共享空间) 三.栈的链式存储结构 1.链栈 2.链栈的基本算法 3.性能分析 四.栈的应用——递归 1.递归的定义 2.斐波那契数列 五.栈的应用——四则运算表达式求值 1.后缀表达式计算结果 2.中缀表达式转后缀表达式 队列 一.队列的基本概念 1.队列的定义 2.队列的常见基本操作 二.队列的顺序存储结构 1.顺序队列 2.循环队列 3.循环队列

  • 详解消息队列及RabbitMQ部署和使用

    目录 什么是消息队列 为什么需要消息队列 常见的消息队列 ActiveMQ RabbitMQ ZeroMQ Kafka RocketMQ RabbitMQ 的部署和使用 Python 编写生产者 Python 编写消费者 最后的话 什么是消息队列 消息队列拆开了看,就是消息 + 队列,消息是什么?其实就是程序之间通讯所用到的数据,消息从生产者那里产生,进入队列后,安装设计好的规则出队,由消费者消费.仅此而已. 为什么需要消息队列 消息队列,最重要的是队列,可以想象一下没有队列的场景,你去银行办业

  • C语言分别实现栈和队列详解流程

    目录 什么是栈 栈的结构图示 栈的实现 创建栈的结构体 初始化栈 入栈 出栈 获取栈顶元素 获取栈中有效元素个数 检测栈是否为空 栈的销毁 什么是队列? 队列的实现 创建队列结构体 初始化队列 队尾入队列 队头出队列 获取队列头部元素 获取队列尾部元素 获取队列中元素个数 检测队列是否为空 销毁队列 什么是栈 栈:一种特殊的线性表,其只允许在固定的一端进行插入和删除元素的操作.进行数据插入和删除的一端称为栈顶,另一端称为栈底.栈中的数据元素遵守先进后出LIFO(Last In First Out

  • SpringBoot整合rockerMQ消息队列详解

    目录 Springboot整合RockerMQ 使用总结 消费模式 生产者组和消费者组 生产者投递消息的三种方式 如何保证消息不丢失 顺序消息 分布式事务 Springboot整合RockerMQ 1.maven依赖 <dependencies> <!-- springboot-web组件 --> <dependency> <groupId>org.springframework.boot</groupId> <artifactId>

  • Java多线程案例之阻塞队列详解

    目录 一.阻塞队列介绍 1.1阻塞队列特性 1.2阻塞队列的优点 二.生产者消费者模型 2.1阻塞队列对生产者的优化 三.标准库中的阻塞队列 3.1Java提供阻塞队列实现的标准类 3.2Blockingqueue基本使用 四.阻塞队列实现 4.1阻塞队列的代码实现 4.2阻塞队列搭配生产者与消费者的代码实现 一.阻塞队列介绍 1.1阻塞队列特性 阻塞队列特性: 一.安全性 二.产生阻塞效果 阻塞队列是一种特殊的队列. 也遵守 “先进先出” 的原则.阻塞队列能是一种线程安全的数据结构, 并且具有

  • RocketMq 消息重试机制及死信队列详解

    目录 生产者消息重试 消费者消息重试 并发消费 顺序消费 并发消费和顺序消费区别 死信队列 实践出真知 公共部分创建 测试并发消费 并发消费状态 测试顺序消费 顺序消费状态 测试死信队列 死信队列特性 生产者消息重试 消息队列中的消息消费时并不能保证总是成功的,那失败的消息该怎么进行消息补偿呢?这就用到今天的主角消息重试和死信队列了. 有时因为网路等原因生产者也可能发送消息失败,也会进行消息重试,生产者消息重试比较简单,在springboot中只要在配置文件中配置一下就可以了. # 异步消息发送

  • C语言 表、栈和队列详解及实例代码

    C语言 表.栈和队列详解 表ADT 形如A1,A2,A3-An的表,这个表的大小为n,而大小为0的表称为空表,非空表中,Ai+1后继Ai,Ai-1前驱Ai,表ADT的相关操有PrintList打印表中的元素:CreateEmpty创建一个空表:Find返回关键字首次出现的位置:Insert和Delete从表的某个位置插入和删除某个关键字. 对表的所有操作都可以通过使用数组来实现,但在这里使用链表的方式来实现.链表(linked list)由一系列不必在内存中相连的结构组成,每个结构均含有元素和指

  • Java 阻塞队列详解及简单使用

     Java 阻塞队列详解 概要: 在新增的Concurrent包中,BlockingQueue很好的解决了多线程中,如何高效安全"传输"数据的问题.通过这些高效并且线程安全的队列类,为我们快速搭建高质量的多线程程序带来极大的便利.本文详细介绍了BlockingQueue家庭中的所有成员,包括他们各自的功能以及常见使用场景. 认识BlockingQueue阻塞队列,顾名思义,首先它是一个队列,而一个队列在数据结构中所起的作用大致如下图所示: 从上图我们可以很清楚看到,通过一个共享的队列,

随机推荐