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

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

**目录**

前言

队列(Queue)

概念：

队列抽象数据类型描述

顺序存储

操作

链式存储

--------------------

## 前言 ##

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

## 队列(Queue) ##

### 概念： ###

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

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

数据插入：**入队列**(AddQ)

数据删除：**出队列**(DeleteQ)

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

### 队列抽象数据类型描述 ###

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

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

1.  Queue CreatQueue(int MaxSize): 生成长度为MaxSize 的空队列
2.  int IsFullQ(Queue Q,int MaxSize): 判断队列Q是否已满
3.  void AddQ(Queue Q,ElementType item): 将数据元素item插入队列Q中
4.  int IsEmptyQ(Queue Q): 判断队列Q是否为空
5.  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;