队列

“队列(Queue)”:具有一定操作约束的线性表

  • 插入和删除操作:只能在一端插入(队头),在另一端删除(队尾)
  • 数据插入:入队列(AddQ)
  • 数据删除:出队列(DeleteQ)
  • 先来先服务、先进先出:FIFO

现实中最能体现堆栈结构的实例:排队

  • 后来的人只能排在队尾,先来的人先离队

队列的抽象数据类型描述

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

队列的顺序存储实现

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

#define MaxSize<储存数据元素的最大个数>
struct QNode
{
    ElementType Data[MaxSize];
    int front,rear;                 //rear指向队尾元素,front指向队头元素之前一个元素
};
typedef struct QNode *Queue;

队列的链式存储实现

队列的链式存储结构也可以用一个单链表实现

插入和删除操作分别在链表的两头进行    //front应指向链表表头,因为删除时需要知道队列元素的位置
struct Node                     //rear应指向链表表尾,因为插入时不需要知道下一个元素的位置,并且把后入队元素加在表尾
{
    ElementType Data;
    struct Node *Next;
};
struct QNode
{
    struct Node *rear;
    struct Node *front;
};
typedef struct QNode *Queue;
Queue PtrQ;

循环队列

顺序队列存在的“假溢出”缺陷

  • 当rear指向数组空间最后时,队列无法再进入新元素
  • 只要进行过一次出队列操作,front就不会指向数组开始下标
  • 因此,顺序队列可能存在数组没满但无法入队列的情况

解决“假溢出”:引入循环队列

  • 当队尾指针rear和队头指针front到达存储空间最大值时,让队尾指针自动转化为存储空间的最小值0(+1取余法)

循环队列中,队空和队满条件都是front==rear,此时存在二义性

  • 二义性的根本原因:假设数组长度为n,则两个下标之间的差有n种可能(0,1…,n-1),而队列长度有n+1(0,1…,n)种可能,
    要使用n种状态表示n+1种情况是不可能的
  • 解决方案有三种:
    • 加设标志位,让删除动作使其为1,插入动作使其为0 //当动作为插入/删除时导致front==rear,则说明队满/队空
    • 使用一个计数器记录队列中元素个数(即队列长度)
    • 人为浪费一个单元,令队满特征为front=(rear+1)%N

队列的顺序存储演示

//以下两部分顺序存储和链式存储代码均来自浙江大学数据结构课程
#include<cstdio>
#include<cstdlib>
#define ERROR -1
typedef int ElementType;
typedef struct Node *PtrToNode;
struct Node { /* 队列中的结点 */
    ElementType Data;
    PtrToNode Next;
};
typedef PtrToNode Position;

struct QNode {
    Position Front, Rear;  /* 队列的头、尾指针 */
    int MaxSize;           /* 队列最大容量 */
};
typedef struct QNode *Queue;

bool IsEmpty( Queue Q )
{
    return ( Q->Front == NULL);
}

ElementType DeleteQ( Queue Q )
{
    Position FrontCell; 
    ElementType FrontElem;
  
    if  ( IsEmpty(Q) ) {
        printf("队列空");
        return ERROR;
    }
    else {
        FrontCell = Q->Front;
        if ( Q->Front == Q->Rear ) /* 若队列只有一个元素 */
            Q->Front = Q->Rear = NULL; /* 删除后队列置为空 */
        else                 
            Q->Front = Q->Front->Next;
        FrontElem = FrontCell->Data;

        free( FrontCell );  /* 释放被删除结点空间  */
        return  FrontElem;
    }
}
#include<cstdio>
#include<cstdlib>
#define ERROR -1
typedef int ElementType;
typedef int Position;
struct QNode {
    ElementType *Data;     /* 存储元素的数组 */
    Position Front, Rear;  /* 队列的头、尾指针 */
    int MaxSize;           /* 队列最大容量 */
};
typedef struct QNode *Queue;

/* Front和rear移动使用“+1取余法”实现顺序存储的“循环使用” */
/* 其它基本操作可参考线性结构和堆栈的示例 */

Queue CreateQueue( int MaxSize )
{
    Queue Q = (Queue)malloc(sizeof(struct QNode));
    Q->Data = (ElementType *)malloc(MaxSize * sizeof(ElementType));
    Q->Front = Q->Rear = 0;
    Q->MaxSize = MaxSize;
    return Q;
}

bool IsFull( Queue Q )
{
    return ((Q->Rear+1)%Q->MaxSize == Q->Front);            //队满条件:(rear+1)%n=front
}

bool AddQ( Queue Q, ElementType X )
{
    if ( IsFull(Q) ) {
        printf("队列满");
        return false;
    }
    else {
        Q->Rear = (Q->Rear+1)%Q->MaxSize;
        Q->Data[Q->Rear] = X;
        return true;
    }
}

bool IsEmpty( Queue Q )
{
    return (Q->Front == Q->Rear);               //必须相等(没有取模),否则比如队满后再加一个元素也满足rear%n=front
}

ElementType DeleteQ( Queue Q )
{
    if ( IsEmpty(Q) ) { 
        printf("队列空");
        return ERROR;
    }
    else  {
        Q->Front =(Q->Front+1)%Q->MaxSize;
        return  Q->Data[Q->Front];      //front原本是队头元素前一个位置,删除一个元素front+1后正好表示原来队头元素位置
    }
}

队列的链式存储演示

#include<cstdio>
#include<cstdlib>
#define ERROR -1
typedef int ElementType;
typedef struct Node *PtrToNode;
struct Node { /* 队列中的结点 */
    ElementType Data;
    PtrToNode Next;
};
typedef PtrToNode Position;

struct QNode {
    Position Front, Rear;  /* 队列的头、尾指针 */
    int MaxSize;           /* 队列最大容量 */
};
typedef struct QNode *Queue;

bool IsEmpty( Queue Q )
{
    return ( Q->Front == NULL);
}

ElementType DeleteQ( Queue Q )
{
    Position FrontCell; 
    ElementType FrontElem;
  
    if  ( IsEmpty(Q) ) {
        printf("队列空");
        return ERROR;
    }
    else {
        FrontCell = Q->Front;
        if ( Q->Front == Q->Rear ) /* 若队列只有一个元素 */
            Q->Front = Q->Rear = NULL; /* 删除后队列置为空 */
        else                   
            Q->Front = Q->Front->Next;
        FrontElem = FrontCell->Data;

        free( FrontCell );  /* 释放被删除结点空间  */
        return  FrontElem;
    }
}