数据结构 | 队列探究与学习、对比堆栈、队列存储实现-蒲公英云

数据结构 | 队列探究与学习、对比堆栈、队列存储实现

墨蓝 2024-04-01 15:02 170阅读 0赞

前言

队列(Queue)

概念：

队列抽象数据类型描述

顺序存储

操作

链式存储

前言

上一篇我们讲解了堆栈相关的知识点，今天我们就对队列详细讲讲，并在此文中将其与堆栈进行适当对比，队列最主要的两个操作是什么呢，我们一起往下看吧

队列(Queue)

概念：

具有一定操作约束的线性表，插入和删除操作，只能在一端插入，而在另一端删除

堆栈也是受限的线性表，但它的插入和删除只在一端进行

数据插入：入队列(AddQ)

数据删除：出队列(DeleteQ)

先来先服务，先进先出(FIFO) 堆栈——先进后出

队列抽象数据类型描述

数据对象集：一个有0个或多个元素的有穷线性表

操作集：长度为MaxSize的队列Q∈Queue，队列元素item∈ElementType

Queue CreatQueue(int MaxSize): 生成长度为MaxSize 的空队列
int IsFullQ(Queue Q,int MaxSize): 判断队列Q是否已满
void AddQ(Queue Q,ElementType item): 将数据元素item插入队列Q中
int IsEmptyQ(Queue Q): 判断队列Q是否为空
ElementType DeleteQ(Queue Q): 将队头数据元素从队列中删除并返回

顺序存储

与堆栈一样，顺序存储也可以用数组来实现，队列也可以用数组来存储队列里的元素，，队列顺序存储结构通常由一个一维数组和一个记录队列头元素位置的变量front以及一个记录队列尾元素位置的变量rear组成

#define MaxSize
Struct QNode{
        ElementType Data[MaxSize];
        int rear;
        int front;
};
typedef struct QNode*Queue;

front指向第一个元素前面的位置，rear指向最后一个元素的位置

初始时front==rear，当元素排满每一个位置时，front和rear也相等，这是该怎么区分？为什么会出现这种情况？

根本原因：数组大小只有n种状态，无法对应n+1种情况

解决方法：1.增加额外的标记，如Size或者tag域

2.仅使用n-1个数组空间

操作

入队列

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

出队列

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

链式存储

队列的链式村粗结构也可以用一个单链表实现。插入和删除操作分别在链表的两头进行；队列指针front和rear应分别指向链表的头和尾

struct Node{
    ElementType Data;
    struct Node *Next;
};
struct QNode{        //链队列结构
    struct Node *rear;    //指向队尾结点
    struct Node *front;   //指向队头结点
};
typedef struct QNode *Queue;
Queue PtrQ;