当前位置： 首页 > article >正文

数据结构—队列

article 2024/12/4 16:38:55

目录

一、队列的定义

二、队列的顺序储存结构

2.1顺序队列的定义

2.2循环队列定义

2.3循环队列的基本操作

三、队列的链式储存结构

3.1链队列的定义

3.2链队列的基本操作

一、队列的定义

队列是一种线性表，其特殊性在于队列的基本操作是线性表的子表。队列按先进先出的规则进行操作，故称其为操作受限的线性表。

队列（queue）是只允许在一端进行插入操作，在另一端进行删除操作的线性表，简称“队”。

允许插入的一端称为队尾（rear），允许删除的一端称为队头(front)。

向队列中插入新的数据元素称为入队，新入队的元素就成为了队列的队尾元素。

从队列中删除队头元素称为出队，其后继元素成为新的队头元素。

注：出队的方向应该与入队的方向一致。

以下为一个简单的队列实现代码：

#include <stdio.h>
#include <stdlib.h>

#define MAX_SIZE 100

// 定义队列结构体
typedef struct {
    int items[MAX_SIZE];
    int front;
    int rear;
} Queue;

// 初始化队列
void initQueue(Queue *q) {
    q->front = -1;
    q->rear = -1;
}

// 检查队列是否为空
int isEmpty(Queue *q) {
    return q->front == -1;
}

// 检查队列是否已满
int isFull(Queue *q) {
    return (q->rear == MAX_SIZE - 1);
}

// 入队操作
void enqueue(Queue *q, int value) {
    if (isFull(q)) {
        printf("Queue is full\n");
        return;
    }
    if (q->front == -1) {
        q->front = 0;
    }
    q->rear++;
    q->items[q->rear] = value;
}

// 出队操作
int dequeue(Queue *q) {
    int item;
    if (isEmpty(q)) {
        printf("Queue is empty\n");
        return -1;
    }
    item = q->items[q->front];
    if (q->front == q->rear) {
        q->front = -1;
        q->rear = -1;
    } else {
        q->front++;
    }
    return item;
}

int main() {
    Queue q;
    initQueue(&q);
    enqueue(&q, 10);
    enqueue(&q, 20);
    enqueue(&q, 30);
    printf("%d dequeued from queue\n", dequeue(&q));
    printf("%d dequeued from queue\n", dequeue(&q));
    return 0;
}

二、队列的顺序储存结构

队列作为一种特殊的线性表，也同样存在两种存储结构：顺序存储结构和链式存储结构，可以分别用数组和链表来实现队列。

2.1顺序队列的定义

用一组地址连续的存储单元，依次存放从队头到队尾的数据元素，称为顺序队列。

需要附设两个指针：队头指针（front）和队尾指针（rear），分别指向队头元素和队尾元素。

以下为实现代码：

#include <stdio.h>
#include <stdlib.h>

#define MAX_SIZE 100

// 定义队列结构体
typedef struct {
    int items[MAX_SIZE];
    int front;
    int rear;
} Queue;

// 初始化队列
void initQueue(Queue *q) {
    q->front = 0;
    q->rear = -1;
}

// 检查队列是否为空
int isEmpty(Queue *q) {
    return (q->rear < q->front);
}

// 检查队列是否已满
int isFull(Queue *q) {
    return (q->rear == MAX_SIZE - 1);
}

// 入队操作
void enqueue(Queue *q, int value) {
    if (isFull(q)) {
        printf("Queue is full\n");
        return;
    }
    q->rear++;
    q->items[q->rear] = value;
}

// 出队操作
int dequeue(Queue *q) {
    int item;
    if (isEmpty(q)) {
        printf("Queue is empty\n");
        return -1;
    }
    item = q->items[q->front];
    q->front++;
    return item;
}

// 获取队列长度
int queueLength(Queue *q) {
    if (isEmpty(q)) {
        return 0;
    }
    return (q->rear - q->front + 1);
}

int main() {
    Queue q;
    initQueue(&q);
    enqueue(&q, 10);
    enqueue(&q, 20);
    enqueue(&q, 30);
    printf("%d dequeued from queue\n", dequeue(&q));
    printf("%d dequeued from queue\n", dequeue(&q));
    printf("Queue length: %d\n", queueLength(&q));
    return 0;
}

 

 接下来介绍在此过程中可能出现的假溢出的现象：

“假溢出”：如果在插入E的基础上再插入元素F，将会插入失败。因为rear==MAXSIZE，尾指针已经达到队列的最大长度。但实际上队列存储空间并未全部被占满，这种现象叫做“假溢出”。

假溢出的原因是顺序队列进行队头出队、队尾入队，造成数组前面会出现空闲单元未被充分利用。

 2.2循环队列的定义

为了解决可能出现的假溢出现象，使得队列中的储存空间可以得到充分利用，一个巧妙的方法就是使用循环队列的方法，将顺序队列看作一个头尾相接的循环结构。

故可以得出循环队列的定义是：队列头尾相接的顺序储存结构称为循环队列。

循环队列的实现代码：

#include <stdio.h>
#include <stdlib.h>

#define MAX_SIZE 100

// 定义队列结构体
typedef struct {
    int items[MAX_SIZE];
    int front;
    int rear;
    int size;
} Queue;

// 初始化队列
void initQueue(Queue *q) {
    q->front = 0;
    q->rear = -1;
    q->size = 0;
}

// 检查队列是否为空
int isEmpty(Queue *q) {
    return (q->size == 0);
}

// 检查队列是否已满
int isFull(Queue *q) {
    return (q->size == MAX_SIZE);
}

// 入队操作
void enqueue(Queue *q, int value) {
    if (isFull(q)) {
        printf("Queue is full\n");
        return;
    }
    q->rear = (q->rear + 1) % MAX_SIZE;
    q->items[q->rear] = value;
    q->size++;
}

// 出队操作
int dequeue(Queue *q) {
    int item;
    if (isEmpty(q)) {
        printf("Queue is empty\n");
        return -1;
    }
    item = q->items[q->front];
    q->front = (q->front + 1) % MAX_SIZE;
    q->size--;
    return item;
}

int main() {
    Queue q;
    initQueue(&q);
    enqueue(&q, 10);
    enqueue(&q, 20);
    enqueue(&q, 30);
    printf("%d dequeued from queue\n", dequeue(&q));
    printf("%d dequeued from queue\n", dequeue(&q));
    return 0;
}

 

但是循环队列也是会出现问题：

问题：当循环对列为空或满时，都是队尾指针等于队头指针，即rear==front 。当rear==front时，该是判满还是判空呢？

解决方案：

方案一：设置一个计数器，开始时计数器设为0，新元素入队时，计数器加1，元素出队，计数器减1。当计数器==MAXSIZE时，队满；计数器==0时，队空。

方案二：保留一个元素空间，当队尾指针指的空闲单元的后继单元是队头元素所在单元时，队满。

队满的条件为（Q.rear+1）%MAXSIZE==Q.front；

队空的条件为  Q.rear==Q.front

2.3循环队列的基本操作

typedef int ElemType
#define MAXSIZE 1024
 
/*循环队列的顺序存储结构*/
typedef struct
{
    ElemType data[MAXSIZE];
    int front;    //头指针
    int rear;    //尾指针
}SqQueue;
 
/*初始化一个空队列*/
int Init_SeQueue(SeQueue *Q)
{
    Q=(SeQueue *)malloc(sizeof(SeQueue));
    if(Q!=NULL)
    {
        Q->front=0;
        Q->rear=0;
    }
    return 1;
}
 
/*求队列长度*/
int QueueLength(SeQueue *Q)
{
    return (Q->rear-Q->front+MAXSIZE)%MAXSIZE;
}
 
/*判空*/
int SeQueue_Empty(SeQueue *Q)
{
    return Q->rear==Q->front;
}
 
/*判满*/
int SeQueue_Full(SeQueue *Q)
{
    return (Q->rear+1)%MAXSIZE==Q->front;
}
 
/*入队操作*/
int Enter_SeQueue(SeQueue *Q,ElemType e)
{
    if(SeQueue_Full(Q))
    {
        return 0;
    }
 
    Q->data[Q->rear]=e;
    Q->rear=(Q->rear+1)%MAXSIZE;
    return 1;
}
 
/*出队操作*/
int Delete_SeQueue(SeQueue *Q,ElemType e)
{
    if(SeQueue_Empty(Q))
    {
        return 0;
    }
 
    e=Q->data[Q->front];
    Q->front=(Q->front+1)%MAXSIZE;
    return 1;
}

三、队列的链式存储结构

3.1链队列的定义

采用链式储存结构的队列称为链队列。

为了使操作更加方便，将队头指针指向链队列的头结点，而队尾指针指向终端结点。 

空队列时，front和rear都指向头结点，即front==rear

代码实现链队列结构：

typedef int ElemType
 
/*结点结构*/
typedef struct QNode
{
    ElemType data;
    struct QNode *next;
}QNode,*QueuePtr;
 
/*链队列结构*/
typedef struct 
{
    QueuePtr front,rear;//队头、队尾指针
}LinkQueue;

3.2链队列的基本操作

typedef int ElemType
 
/*结点结构*/
typedef struct QNode
{
    ElemType data;
    struct QNode *next;
}QNode,*QNodePtr;
 
/*链队列结构*/
typedef struct 
{
    QNodePtr front,rear;//队头、队尾指针
}LinkQueue,*LinkQueuePtr;
 
/*初始化一个空队列*/
int Init_LinkQueue(LinkQueuePtr Q)
{
    Q=(LinkQueuePtr)malloc(sizeof(LinkQueue));
    QNodePtr head=(QueuePtr)malloc(sizeof(QNode));
    
    if(head!=NULL && Q!=NULL)
    {
        head->next=NULL;
        Q->front=head;
        Q->rear=head;
    }
    return 1;
}
 
/*判空*/
int LinkQueue_Empty(LinkQueuePtr Q)
{
    return Q->front==Q->rear;
}
 
/*入队操作*/
int Enter_LinkQueue(LinkQueuePtr Q,ElemType e)
{
    QNodePtr s=(QNodePtr)malloc(sizeof(QNode));
    if(s==NULL){
        return 0
    }    
    //初始化新结点
    s->data=e;
    s->next=NULL;
    //建立新联系
    Q->rear->next=s;
    Q->rear=s;
 
    return 1;
}
 
/*出队操作*/
int Delte_LinkQueue(LinkQueuePtr Q,ElemType *e)
{
    QNodePtr p;
    if(LinkQueue_Empty(Q)){
        return 0
    } 
       
    //保留删除结点的信息
    p=Q->front->next;
    *e=p->data;
 
    //建立新联系
    Q->front->next=p->next;
   
    if(Q->rear==p)
    {
        Q->rear=Q->front)
    }
    
    free(p);
 
    return 1;
}

以上就是有关队列的知识及代码实现。


http://www.kler.cn/a/421512.html

相关文章：

  • 单机环境下Caffeine和Redis两级缓存的实现与问题解决
  • 基于Matlab卡尔曼滤波的GPS/INS集成导航系统研究与实现
  • Docker：在 ubuntu 系统上生成和加载 Docker 镜像
  • vue2 虚拟DOM 和 真实DOM （概念、作用、Diff 算法）
  • [241129] Docker Desktop 4.36 发布：企业级管理功能、WSL 2 增强 | Smile v4.0.0 发布
  • pandas 大数据获取某列所有唯一值
  • 顶刊算法 | 鱼鹰算法OOA-BiTCN-BiGRU-Attention多输入单输出回归预测（Maltab）
  • Zabbix添加防火墙温度监控值实战
  • Macos用brew安装Nodejs亲手教程
  • LLM与动态符号执行生成测试用例的比较
  • C语言第十五周课——课堂练习
  • 数据结构自测题1
  • Qt 5 中的 QTextStream 使用指南
  • 接口自动化测试框架(pytest+allure+aiohttp+用例自动生成)
  • 正则表达式解析
  • ceph mon 数据重建
  • yt6801 ubuntu有线连接驱动安装
  • vue前端 下载、预览图片
  • 【Unity】【游戏开发】【VR】如何解决脚本不在同一个项目无法引用Public变量的问题
  • Epsilon2系列战术级微型惯性RTK卫星高精度组合导航系统0.5°/h
  • 开发中使用UML的流程_06 PIM-2：分析业务规则
  • Lumos学习王佩丰Excel第十九讲：Indirect函数
  • 《NGINX金典教程》读书笔记
  • 什么是敏捷（Agile）开发？Scrum和Kanban有什么关系？
  • 【Leetcode Top 100】2. 两数相加
  • 海康gige工业相机无驱动取像突破（c#实现，最后更新，你也可以移植到linux下去用）