第4章(2) 队列

2019-03-07 本文已影响0人 cb_guo

队列是只允许在一端进行插入操作、而在另一端进行删除操作的线性表

队列是一种先进先出(First In First Out) 的线性表，简称FIFO
允许插入的一段称为队尾，允许删除的一端称为队头

1、队列的抽象数据类型

同样是线性表，队列也有类似线性表的各种操作，不同的是插入数据只能在队尾，删除数据只能在队头进行

2、循环队列

队列的头尾相接的顺序存储结构称为循环队列

2.1、队列顺序存储结构不足

队列顺序存储结构用数组来实现
这部分详情去看《大华数据结构》第四章栈与队列，书上讲述的很详细

2.2 循环队列代码实现

通用循环队列长度公式为 (rear - front + QueueSize) % QueueSize

循环队列的顺序存储结构代码

typedef int Status; 
typedef int QElemType; /* QElemType类型根据实际情况而定，这里假设为int */

/* 循环队列的顺序存储结构 */
typedef struct
{
    QElemType data[MAXSIZE];
    int front;      /* 头指针 */
    int rear;       /* 尾指针，若队列不空，指向队列尾元素的下一个位置 */
}SqQueue;

循环队列的初始化代码

/* 初始化一个空队列Q */
Status InitQueue(SqQueue *Q)
{
    Q->front=0;
    Q->rear=0;
    return  OK;
}

循环队列求队列长度代码

/* 返回Q的元素个数，也就是队列的当前长度 */
int QueueLength(SqQueue Q)
{
    return  (Q.rear-Q.front+MAXSIZE)%MAXSIZE;
}

循环队列入队列代码

/* 若队列未满，则插入元素e为Q新的队尾元素 */
Status EnQueue(SqQueue *Q,QElemType e)
{
    if ((Q->rear+1)%MAXSIZE == Q->front)    /* 队列满的判断 */
        return ERROR;
    Q->data[Q->rear]=e;         /* 将元素e赋值给队尾 */
    Q->rear=(Q->rear+1)%MAXSIZE;/* rear指针向后移一位置， */
                                /* 若到最后则转到数组头部 */
    return  OK;
}

循环队列出队列代码

/* 若队列不空，则删除Q中队头元素，用e返回其值 */
Status DeQueue(SqQueue *Q,QElemType *e)
{
    if (Q->front == Q->rear)            /* 队列空的判断 */
        return ERROR;
    *e=Q->data[Q->front];               /* 将队头元素赋值给e */
    Q->front=(Q->front+1)%MAXSIZE;  /* front指针向后移一位置， */
                                    /* 若到最后则转到数组头部 */
    return  OK;
}

总结：从上我们可看到，单是顺序存储，若不是循环队列，算法的时间性能是不高的，但循环队列又面临数组可能会溢出的问题，所以我们还需要研究一下不需要担心队列长度的链式存储结构

3、队列链式存储结构及实现

队列的链式存储结构，其实就是线性表的单链表，只不过它只能尾进头出而已，简称为链队列

为了操作上的方便，我们将队头指针指向链队列的头节点，而队尾指针指向终端节点，如下图所示

链队列的结构为

typedef int QElemType; /* QElemType类型根据实际情况而定，这里假设为int */

typedef struct QNode    /* 结点结构 */
{
   QElemType data;
   struct QNode *next;
}QNode,*QueuePtr;

typedef struct          /* 队列的链表结构 */
{
   QueuePtr front,rear; /* 队头、队尾指针 */
}LinkQueue;

入队操作

其实就是在链表尾部插入节点

/* 插入元素e为Q的新的队尾元素 */
Status EnQueue(LinkQueue *Q,QElemType e)
{ 
    QueuePtr s=(QueuePtr)malloc(sizeof(QNode));
    if(!s) /* 存储分配失败 */
        exit(OVERFLOW);
    s->data=e;
    s->next=NULL;
    Q->rear->next=s;    /* 把拥有元素e的新结点s赋值给原队尾结点的后继，见图中① */
    Q->rear=s;      /* 把当前的s设置为队尾结点，rear指向s，见图中② */
    return OK;
}

出队操作

/* 若队列不空,删除Q的队头元素,用e返回其值,并返回OK,否则返回ERROR */
Status DeQueue(LinkQueue *Q,QElemType *e)
{
    QueuePtr p;
    if(Q->front==Q->rear)
        return ERROR;
    p=Q->front->next;       /* 将欲删除的队头结点暂存给p，见图中① */
    *e=p->data;             /* 将欲删除的队头结点的值赋值给e */
    Q->front->next=p->next;/* 将原队头结点的后继p->next赋值给头结点后继，见图中② */
    if(Q->rear==p)      /* 若队头就是队尾，则删除后将rear指向头结点，见图中③ */
        Q->rear=Q->front;
    free(p);
    return OK;
}

循环队列与链队列总结：

1、时间：它们基本操作都是常数时间，即都是 O(1)。不过循环队列是事先申请好空间，使用期间不释放，而对于链队列，每次申请和释放存在一些时间开销，如果入队出队频繁，则两者还是有细微差异
2、空间：循环空间必须有一个固定的长度，所以就有了存储元素个数和空间浪费问题。而链队列不存在这个问题，尽管它需要一个指针域，会产生一些空间上的开销，但也可以接受。所以在空间上，链队列更加灵活
总体来说，在可以确定队列长度的情况下，建议用循环队列，如果你无法预估队列的长度时，则用链队列