首页 > 其他分享 >05. 队列

05. 队列

时间:2023-03-23 17:57:20浏览次数:38  
标签:struct 05 队列 PtrQ Queue front rear

一、什么是队列

  队列(Queue)是具有一定约束的线性表,它只能在 一端插入入队,AddQ)而在 另一端删除出队,DeleteQ)。它具有 先进先出(FIFO)的特性。

  队列的抽象类型描述:

  • 类型名称:队列(Quene)
  • 数据对象集:一个有 0 个或多个元素的有穷线性表
  • 操作集:长度为 MaxSize 的队列 Q ∈ Quene,队列元素 item ∈ ElementType
Queue CreateQuene(int MaxSzie);         // 生成长度为MaxSize的空队列
int IsFullQ(Queue Q,int MaxSize);       // 判断队列Q是否已满
void AddQ(Queue Q,ElementType item);    // 将数据元素item插入队列Q中
int IsEmptyQ(Quenu Q);                  // 判断队列Q是否为空
ElementType DeleteQ(Queue Q);           // 将队头数据元素从队列中删除并返回

二、队列的顺序存储实现

  队列的顺序存储结构通用由一个一维数组和一个记录 队列头元素位置 的变量 front 以及一个记录 队列尾元素位置 的变量 rear 组成。

#define MaxSize         // 存储数据元素的最大个数
struct QNode
{
    ElementType Data[MaxSize];
    int rear;
    int front;
};

typedef struct QNode *Queue;

【1】、入队(AddQ)

void AddQ(Queue PtrQ,ElementType item)
{
    if((PtrQ->rear+1) % MaxSize == PtrQ->front)
    {
        printf("队列已满\n");
        return;
    }

    PtrQ->rear = (PtrQ->rear + 1) % MaxSize;
    PtrQ->Data[PtrQ->rear] = item;
}

循环队列当存储空间全部使用时,read 等于 front,此时无法表示循环队列是空的还是满的,此时解决方法有两种:第一种是 使用额外的标记:Size 或者 tag域,Size 用来记录当前循环队列中元素的个数。第二种方式是 仅使用 n-1 个数组空间

【2】、出队(DeleteQ)

ElementType DeleteQ(Queue PtrQ)
{
    if(PtrQ->front == PtrQ->rear)
    {
        printf("队列空\n");
        return ERROR;
    }
    else
    {
        PtrQ->front = (PtrQ->font + 1) % MaxSize;
        return PtrQ->Data[PtrQ->front];
    }
}

三、队列的链式存储实现

  队列的链式存储结构可以用一个单链表实现。插入入栈,AddQ)和 删除出栈,DeleteQ)操作分别在链表的两头进行。队列头指针 front 指向 链表头队列尾指针 rear 指向 链表尾

img

typedef struct QNode *Queue;

struct Node
{
    ElementType Data;
    struct Node *Next;
};

struct QNode                // 链队列结构
{
    struct Node *rear;      // 指向队尾结点
    struct Node *front;     // 指向队头结点
};

Queue PtrQ;

【1】、入队(AddQ)

  不带头节点的链式队列入队操作:

void AddQ(Queue PtrQ,ElementType item)
{
    struct Node *temCell;

    temCell = (struct Node *)malloc(sizeof(struct Node));
    temCell->Data = item;
    tempCell->Next = NULL;

    if(PtrQ->font == NULL)                      // 如果是第一个结点
    {
        PtrQ->rear = PtrQ->front = temCell;     // 队列的头指针和尾指针都指向第一个结点
    }
    else
    {
        PtrQ->rear->Next = temCell;             // 之前的链表的尾结点连接新结点,形成链
        PtrQ->rear = temCell;                   // 队列的尾结点指向新结点
    }
}

【2】、出队(DeleteQ)

  不带头节点的链式队列出队操作:

ElementType DeleteQ(Queue PtrQ)
{
    struct Node *FrontCell;
    ElementType FrontElem;

    if(PtrQ->front == NULL)
    {
        printf("队列已空\n");
        return ERROR;
    }

    FrontCell = PtrQ->front;
    if(PtrQ->front = PtrQ->rear)            // 若队列只有一个元素
    {
        PtrQ->front = PtrQ->rear = NULL;    // 删除后队列置为空
    }
    else
    {
        PtrQ->front = PtrQ->front->Next;    // 队列头指针指向第二个元素
    }

    FrontElem = FrontCell->Data;            // 获取原队列头指针指向的元素
    free(FrontCell);                        // 释放被删除的结点空间
  
    return FrontElem;
}

标签:struct,05,队列,PtrQ,Queue,front,rear
From: https://www.cnblogs.com/kurome/p/17248340.html

相关文章

  • 螺纹2305 短线偏空
        中线还是看涨 ......
  • 消息队列之日志处理
    消息队列之日志处理应用场景:大型电商网站(淘宝、京东、国美、苏宁...)、App(抖音、美团、滴滴等)等需要分析用户行为,要根据用户的访问行为来发现用户的喜好以及活跃情况,需要......
  • 消息队列之系统解耦
    消息队列之系统解耦A系统产生一条数据,发送到MQ里面去,哪个系统需要数据自己去MQ里面消费。如果新系统需要数据,直接从MQ里消费即可;如果某个系统不需要这条数据了,就......
  • Google Guice 入门教程05 - AOP(面向切面编程)
    2AOP面向切面编程2.1AOP入门在前面的章节主要讲Guice的依赖注入,有了依赖注入的基础后我们再来看Guice的AOP。我们先从一个例子入手,深入浅出的去理解Guice的AOP的原理和实......
  • 【杂题乱写】ARC105
    AtCoderRegularContest105AFourtuneCookies按题意模拟。BMAX-=min题目中提到过程一定会停止,考虑\(n=2\)时就是更相减损至相等,即求\(\gcd\),扩展到\(n\)更大......
  • 一种异步延迟队列的实现方式
    作者:京东零售张路瑶1.应用场景目前系统中有很多需要用到延时处理的功能:支付超时取消、排队超时、短信、微信等提醒延迟发送、token刷新、会员卡过期等等。通过延时处理,......
  • C05大整数相加
    importjava.math.BigInteger;importjava.util.Scanner;publicclassA05大整数相加{publicstaticvoidmain(String[]args){Scannerinput=newScanner(System......
  • A05鸡兔同笼
    publicclassA05鸡兔同笼{publicstaticvoidmain(String[]args){//鸡兔同笼,鸡的数量是兔子的4倍,总的脚数是396,问鸡兔各有多少只?intj;//j表示鸡for(int......
  • VMware ESXi 8.0.0 build-20513097 许可证
    有效:4V492-44210-48830-931GK-2PRJ4 ESXi8:4V492-44210-48830-931GK-2PRJ4VCSA8:0Z20K-07JEH-08030-908EP-1CUK4ESXi8:4F40H-4ML1K-M89U0-0C2N4-1AKL4VCSA8:0F41K-0M......
  • 如何防止队列中的信息丢失?
    如何防止队列中的信息丢失?我们先用两个名词来概括往队列中放入消息的行为和处理队列中消息的行为,称之为生产者与消费者。应用场景:订单请求过来,为了快速的响应给前端,需......