首页 > 编程语言 >04 队列 | 数据结构与算法

04 队列 | 数据结构与算法

时间:2022-10-16 19:47:49浏览次数:61  
标签:return 04 队列 queue empty front 数据结构 rear

1. 队列

1. 队列的概念

  1. 队列:操作受限的线性表,只允许在一端进行元素的插入,另一端进行元素的删除
  2. 空队列:不含有任何元素的队列
  3. 队头和队尾:进行删除的一端叫 队头front,进行插入的一段叫 队尾rear

2. 队列的存储形式

  1. 连续设计:利用一组连续的存储单元(一维数组) 依次存放从队首到队尾的各个元素,称为顺序队列
    1. 队头指针 总是指向队头元素的 前一个位置
    2. 操作
    #define MAXN 1000
    typedef struct queue{
        int queue_array[MAXN];
        int front, rear;
    }queue;
    
    // 1. initialize a queue
    void initialize(queue& q){
        q.front = q.rear = 0;
    }
    
    // 2. insert element in the queue
    bool push(queue& q, int data){
        q.rear = q.rear + 1;
        if(q.rear == MAXN) return false;    //overflow
        else {
            q.queue_array[q.rear] = data;
            return true;
        }
    }
    
    // 3. delete element in the queue
    bool pop(queue& q){
        if(q.empty()) return false;     // there's no element
        else {
            q.front = q.front + 1;  
            //会导致队列 *假溢出*(实际上还有空间)
            return true;
        }
    }
    
    // 4. check the queue is empty or not
    bool empty(queue& q){
        return q.front == q.rear;
    }
    
    // 5. return the top of the queue
    int front(queue& q){
        if(q.empty()) return -1;    //queue is empty
        else return q.queue_array[q.front + 1];
    }
    
  2. 循环队列
    1. 定义:将为队列分配的向量空间看成为一个首尾相接的圆环;充分利用了向量空间,克服上述假溢出现象
      image

    2. 操作

    #define MAXN 1000   //queue max size
    typedef struct queue{
        int queue_array[MAXN];
        int front, rear;    //full queue is (front+1)%MAXN == rear
    }queue;
    
    // 1. initialize a queue
    void initialize(queue& q){
        q.front = q.rear = 0;
    }
    
    // 2. insert element in the queue
    bool push(queue& q, int data){
        q.rear = (q.rear + 1) % MAXN;
        if((q.front + 1)%MAXN == rear) return false;    //overflow
        else {
            q.queue_array[q.rear] = data;
            return true;
        }
    }
    
    // 3. delete element in the queue
    bool pop(queue& q){
        if(q.empty()) return false;     // there's no element
        else {
            q.front = (q.front + 1) % MAXN;
            return true;
        }
    }
    
    // 4. check the queue is empty or not
    bool empty(queue& q){
        return q.front == q.rear;
    }
    
    // 5. return the top of the queue
    int front(queue& q){
        if(q.empty()) return -1;    //queue is empty
        else return q.queue_array[(q.front + 1) % MAXN];
    }
    
  3. 链接设计
    1. 队列的链式存储结构简称为链队列,它是限制仅在表头进行删除操作和表尾进行插入操作的单链表。需要两类不同的结点:数据元素结点,队列的队首指针和队尾指针的结点
    2. 操作和单链表相似,只是多了frontrear队头队尾指针,并且操作限制在队头队尾
    typedef struct queue_node{
        int data;
        queue_node *next;
    }node;
    
    typedef struct queue{
        node *front, *rear;
        queue(node *front = nullptr, node *rear = nullptr):front(front), rear(rear){}
    }queue;
    

2. 其他操作受限的线性表

  1. 输入受限的队列:限定在一端进行输入,可以在两端进行删除的队列
  2. 输出受限的队列:限定在一端进行输出,可以在两端进行加入的队列
  3. \(Deque\)双向队列:输入输出限定在两头的队列:限定在两端进行输出,在两端进行加入的队列

标签:return,04,队列,queue,empty,front,数据结构,rear
From: https://www.cnblogs.com/RadiumGalaxy/p/16796874.html

相关文章

  • Windows不分区VHD装Linux多系统(七):ubuntu 22.04.1安装实验
    一、安装过程:环境:1.物理机系统:Win102. ISO镜像:ubuntu-22.04.1-desktop-amd64.iso3.虚拟机:VirtualBox图形用户界面,版本6.1.36r152435(Qt5.6.2)    安......
  • Persistent data structure 不可变数据结构
    持久性变数据不要和持久储存相混淆在计算机中持久性数据或非临时数据是一种数据结构,在修改时始终保持其自身的先前版本。这些数据实际上是不可变的,因为对这类数据操作不会......
  • 数据结构-串、数组、广义表
    @目录XDOJ0224矩阵相乘XDOJ0250螺旋填数XDOJ0257公共子串XDOJ0287求矩阵中的马鞍点XDOJ0288求一个顺序串的next函数值XDOJ0296中心对称的字符串XDOJ0309矩阵加法运......
  • k8s部署tomcat访问报错404
    [root@k8smaster~]#kubectlgetpodsNAMEREADYSTATUSRESTARTSAGEnginx-6799fc88d8-62njk1/1Running212htomcat-......
  • 04 RabbitMQ 3.8 Feature Focus - Single Active Consumer
    标题:RabbitMQ3.8FeatureFocus-SingleActiveConsumer原文:https://www.cloudamqp.com/blog/rabbitmq-3-8-feature-focus-single-active-consumer.html时间:2019-04-2......
  • 2022-2023-1 20221304 《计算机基础与程序设计》第七周学习总结
    2022-2023-120221304《计算机基础与程序设计》第七周学习总结作业信息这个作业属于哪个课程https://edu.cnblogs.com/campus/besti/2022-2023-1-CFAP这个作业......
  • 队列
    应用:广搜总结:链表总的来说比较灵活,普通的顺序表有一头是固定的,因此对于队列这种两端都存在数据变化的情况,使用链表实现会比较自然,而使用顺序表实现则要用循环队列的方式来......
  • 堆与优先队列
    数据结构就是定义一种性质并去维护这种性质所产生的结构。优先队列(堆)#include<stdio.h>#include<stdlib.h>#include<time.h>#defineswap(a,b){\__type......
  • 【图形基础篇】04 # GPU与渲染管线:如何用WebGL绘制最简单的几何图形?
    说明【跟月影学可视化】学习笔记。图形系统是如何绘图的?一个通用计算机图形系统主要包括6个部分,分别是:输入设备中央处理单元:首先,数据经过CPU处理,成为具有特定结构的几何......
  • redis bitmap数据结构之java对等操作
    在之前的文章中,我们有说过bitmap,bitmap在很多场景可以应用,比如黑白名单,快速判定,登录情况等等。总之,bitmap是以其高性能出名。其基本原理是一位存储一个标识,其他衍生知......