【自考】数据结构第三章,队列,期末不挂科指南,第4篇

队列

这篇博客主要介绍一下队列的概念,并且采用C语言,编写两种存储实现方式: 顺序存储链式存储,当然还有常规的队列基本操作的实现算法

队列基本概念

标准解释:队列(Queue)是 有限个同类型数据元素的线性序列,是一种 先进先出(First In First Out FIFO)的线性表,新键入的数据元素插在队列尾端,出队列的数据元素在队列首部被删除。

教材中给了一个示意图,不错

【自考】数据结构第三章,队列,期末不挂科指南,第4篇

顺序队列结构类型中有三个域:data、front、rear。

data:一维数组,存储队列中的数据元素
font:指向队列首元素的前一个单元
rear:指向实际的队列尾元素单元

参考示意图

【自考】数据结构第三章,队列,期末不挂科指南,第4篇

入队列操作可以用两条赋值语句

SQ.rear = SQ.rear+1;
SQ.data[SQ.rear] = x;

出队列操作可以用一条语句完成

SQ.front = SQ.front+1

但是,会出现一些问题,通过示意图说明一下

【自考】数据结构第三章,队列,期末不挂科指南,第4篇

当然还有一种情况,一边入队列,一边出队列
注意下图,SQ.front下面还有空间

【自考】数据结构第三章,队列,期末不挂科指南,第4篇

所以为了解决这种假溢出问题,聪明的开发人员,想出来新的解决办法了,造一个环儿~

[En]

So in order to solve this false overflow problem, smart developers have come up with a new solution to create a ring.

循环队列

下面看一个图,重点看一下SQ.rear与SQ.front的对应位置

【自考】数据结构第三章,队列,期末不挂科指南,第4篇

如果上述图翻译成C语言代码,入队核心逻辑为

SQ.rear = (SQ.rear+1) % maxsize ;
SQ.data[SQ.rear] = x;

出队列的核心逻辑为

SQ.front = (SQ.front+1)%maxsize;

你在学习的时候,肯定对 SQ.rear+1SQ.front+1有疑问

我们举例来说明一下吧

【自考】数据结构第三章,队列,期末不挂科指南,第4篇

顺序队列的C语言实现

接下来难度指数上升,开始用C语言编写代码吧

一顿操作之后,还是比较简单的,总之不写链式存储,顺序的还是比较简单的

[En]

After a meal of operation, it is still relatively simple, in short, do not write chain storage, the order is still relatively simple

#include
#include

//循环队列最大数据元素个数
const int maxsize = 8;

//循环队列的结构体
typedef struct cycqueue{
    int *data;
    int front,rear;
} CycQue;

//队列初始化
void init(CycQue *CQ){
    CQ->data = (int *)malloc(maxsize*sizeof(int));
    CQ->front = 0;
    CQ->rear = 0;
}

//判断队列是否为空
int empty(CycQue *CQ){
    if(CQ->rear==CQ->front) return 1;
    else return 0;
}

//入队列
int EnQueue(CycQue *CQ,int x){
    if((CQ->rear+1)%maxsize==CQ->front){
        printf("队列满");
        return 0;
    }
    else{
        CQ->rear =(CQ->rear+1) % maxsize;
        CQ->data[CQ->rear] = x;
        return 1;
    }

}

//出队列
int OutQueue(CycQue *CQ){
    if(empty(CQ)){
        printf("队列为空");
        return 0;
    }
    else{
        CQ->front = (CQ->front+1) % maxsize;
        return 1;

    }

}

int main()
{
    CycQue CQ;
    init(&CQ);

    EnQueue(&CQ,2);
    EnQueue(&CQ,4);
    printf("%d",CQ.rear);
    OutQueue(&CQ);
    printf("%d",CQ.front);
    return 0;
}

链式队列的C语言实现

链式队列其实有之前的经验之后,写起来难度系数也不会太高,接下来我们编写一个核心的部分代码

[En]

In fact, after the chain queue has previous experience, it will not be too difficult to write, so let’s write a core part of the code.

队列的链接实现实际上是用一个带有头结点的单链表来表示队列,成为链队列
头指针指向链表的头结点
单链表的头结点的next域指向队列首结点
尾指针指向队列尾结点,即单链表的最后一个结点

【自考】数据结构第三章,队列,期末不挂科指南,第4篇

初始化

#include
#include
typedef struct LinkQueueNode{
    int *data;
    struct LinkQueueNode *next;
} LkQueNode;

typedef struct LkQueue{
    LkQueNode *front,*rear;
} LkQue;

void init(LkQue *LQ){
    LkQueNode *temp;
    temp = (LkQueNode *)malloc(sizeof(LkQueNode)); //生成队列的头结点
    LQ->front = temp;    //队列头指针指向队列头结点
    LQ->rear = temp;     //队列尾指针指向队列尾结点
    (LQ->front)->next = NULL;

}

核心两个操作 入队列出队列

【自考】数据结构第三章,队列,期末不挂科指南,第4篇

入队列代码如下

//入队列
void EnQueue(LkQue *LQ,int x){

    LkQueNode *temp;
    temp = (LkQueNode *)malloc(sizeof(LkQueNode));
    temp->data = x;
    temp-next = NULL;
    (LQ->rear)->next = temp;
    LQ->rear = temp;
}

出队列这个事情就交给你自己吧,好好理解一下,就可以写出来了

自考要点

在考试中,队列容易出现编码题目,占比在7~10分,所以还是蛮重要的呢!

看到这里,辛苦啦,BYEBYE

Original: https://www.cnblogs.com/happymeng/p/shujujiegou_4.html
Author: 梦想橡皮擦
Title: 【自考】数据结构第三章,队列,期末不挂科指南,第4篇

原创文章受到原创版权保护。转载请注明出处:https://www.johngo689.com/116704/

转载文章受原作者版权保护。转载请注明原作者出处!

(0)

大家都在看

免费咨询
免费咨询
扫码关注
扫码关注
联系站长

站长Johngo!

大数据和算法重度研究者!

持续产出大数据、算法、LeetCode干货,以及业界好资源!

2022012703491714

微信来撩,免费咨询:xiaozhu_tec

分享本页
返回顶部