[队列](2)队列

和栈相反,队列(queue)是一种先进先出(first in first out,缩写为FIFO)的线性表。

它只允许在表的一端进行插入,而在表的另一端删除元素, 这和我们日常生活中的排队是一致的,最早进入队列的元素最早离开。

在队列中,允许插入的一端叫做队尾(rear),允许删除的一段则称为队头(front),假设队列为q=(a1,a2,a3.....,an),那么a1就是队头元素,an则是队尾元素,队列中的元素是按照a1,a2,a3......an的顺序进入的,退出队列也只能按照这个次序依次退出。

也就是说,只有在a1,a2...an-1都离开队列之后,an才能退出队列。

我们可以理解为,插入在尾端,删除在头端,指示图如下所示:

img

我们可以形象的理解成:买车票的时候,需要排队,排队就是插入,办理完手续出队就是删除

队列在程序设计中也经常出现,一个最典型的例子就是操作系统中的作业排队,在允许多道程序运行的计算机系统中,同时又几个作业运行,如果运行的结果都需要通过通道输出,那就按请求输出的先后次序排队。

每当通道传输完毕可以接受新的输出任务时,队头的作业先从队列中退出作输出操作,凡事申请输出的作业都从队尾进入队列。

下面是队列的抽象数据类型定义

ADT Queue
{
    数据对象:D = {ai | ai属于ElemSet,i = 1,2,...,n,n >= 0}
    数据关系:R1 = {<a(i - 1)> | a(i - 1),ai属于D,i = 2,...,n}
             约定其中a1端为队列头,an端为队列尾

    基本操作:
        InitQueue(&Q);
        操作结果:构造一个空队列Q

        DestroyQueue(&Q)
        初始条件:队列Q已存在
        操作结果:队列Q被销毁,不再存在

        ClearQueue(&Q)
        初始条件:队列Q已存在
        操作结果:将Q清为空队列

        QueueEmpty(Q)
        初始条件:队列Q已存在
        操作结果:若Q为空队列,则返回TRUE,否则FALSE

        QueueLength(Q)
        初始条件:队列Q已存在
        操作结果:返回Q的元素个数,即队列的长度

        GetHead(Q,&e)
        初始条件:队列Q已存在
        操作结果:用e返回Q的队头元素

        EnQueue(&Q,&e)
        初始条件:队列Q已存在
        操作结果:插入元素e为Q的新的队尾元素

        DeQueue(&Q,&e)
        初始条件:Q为非空队列
        操作结果:删除Q的队头元素,并用e返回其值

        QueueTraverse(Q,visit())
        初始条件:Q已存在且非空
        操作结果:从队头到队尾,依次对Q的每个数据元素调用函数visit(),一旦visit()失败
                  则操作失败

}ADT Queue

除了栈和队列之外,还有一种限定性数据结构是双端队列(deque),双端队列是,队头和队尾都可以做插入和删除,但是它的操作远不及栈和队列有用,则不做讲述

链队列

和线性表类似,队列也可以由两种存储表示,用链表表示的队列简称为链队列。

一个链队列显然需要两个分别指示队头和队尾的指针(分别称为头指针和尾指针)才能唯一确定,这里,和线性表的单链表一样,为了操作方便起见,我们也给链队列添加一个头结点,并让头指针指向头结点,由此,空的链队列的判决条件为头指针和尾指针均指向头结点

链队列的操作即为单链表的插入和删除操作的特殊情况,只是尚需修改尾指针或头指针的指向,如下图所示

img

下面是单链队列的存储结构:

typedef int QelemType, Status;

/*单链队列存储结构*/
typedef struct QNode
{
    QelemType data;
    struct QNode* next;
}QNode, * QueuePtr;


typedef struct
{
    QueuePtr front;//队头指针
    QueuePtr rear  //队尾指针

}LinkQueue;


/*基本操作函数原型说明*/


Status InitQueue(LinkQueue& Q);
//构造一个空队列Q

Status DestroyQueue(LinkQueue& Q);
//销毁队列Q,Q不再存在

Status ClearQueue(LinkQueue& Q);
//将Q清为空队列

Status QueueEmpty(LinkQueue Q);
//若队列Q为空列,则返回TRUE否则返回FALSE

int QueueLength(LinkQueue Q);
//返回队列Q的元素个数,即为长度

Status GetHead(LinkQueue Q, QelemType& e);
//若队列不空,用e返回队列Q的队头元素,并返回TRUE,否则返回ERROR

Status EnQueue(LinkQueue& Q, QelemType);
//插入元素e为Q的新队尾元素

Status DeQueue(LinkQueue& Q, QelemType);
//若队列不空,则删除Q的队头元素,用e返回其值,并返回OK,否则返回ERROR

Status QueueTraverse(LinkQueue Q, visit());
//从队头到队尾依次对队列Q中每个元素调用函数visit(),一旦visit失败,则操作失败

下面是链队列的基本操作:

初始化队列

Status InitQueue(LinkQueue* Q)
{
    Q->front = Q->rear = (QueuePtr)malloc(sizeof(QNode));
    if (!Q->front)
    {
        exit(ERROR);
    }
    Q->front->next = NULL;
    return OK;
}

销毁队列

Status DestroyQueue(LinkQueue* Q)
{
    while (Q->front)
    {
        Q->rear = Q->front->next;
        free(Q->front);
        Q->front = Q->rear;
    }
    return OK;
}

插入元素在队尾

Status EnQueue(LinkQueue* Q, QelemType e)
{
    QueuePtr p;
    p = (QueuePtr)malloc(sizeof(QNode));
    p->data = e;
    p->next = Q->rear->next;
    Q->rear->next = p;
    Q->rear = p;

    return OK;
}

删除元素在队头

Status DeQueue(LinkQueue* Q, QelemType* e)
{
    if (Q->rear == Q->front)
    {
        exit(ERROR);
    }
    QueuePtr p;
    p = Q->front->next;
    Q->front->next = p->next;
    *e = p->data;
    
    if (Q->rear == p)
    {
        Q->rear = Q->front;
    }
    free(p);
}

在上述模块的算法描述中,需要注意的是:删除队列头元素的算法中的特殊情况,一般情况下,删除队列头元素时仅需修改头结点的指针域,但当队列中最后一个元素被删后,尾指针必须指向头结点。

循环队列——队列的顺序表示和实现

和顺序栈类似,在队列的顺序存储结构中,除了用一组地址连续的存储单元依次存放从队列头到队列尾的元素之外,尚需附设两个指针front和rear分别指示队列头元素及队列尾元素的位置。

为了在C语音中描述方便起见,以后初始化队列的时候,让指针front和rear都为0.

因此,在非空队列中,头指针始终指向队列头元素,而尾指针始终指向队列尾元素的下一个位置,如下图所示:

img

假设当前为队列分配的最大空间为6,则当队列处于上述第四状况后不可再继续插入新的队尾元素,否则会因数组越界而导致程序被破坏

当时此时右不宜如顺序栈那样,进行存储在分配扩大数组空间,因为队列的实际可用空间并未占满。

一个巧妙的办法就是将顺序队列想成一个环状空间,称为循环队列,指针和队列元素之间的关系不变。

凭借判断头指针front和尾指针rear是否相遇并不能判断队列是否满,我们来看下面三张图

img

显而易见,a图所示的循环队列中,队头元素是J3,队列尾元素是J5。

b图中,J6,J7,J8三个元素相继入队,则队列空间被占满,此时头指针跟尾指针相遇,有表达式,Q.front==Q.rear。

但是到c图中,从a图若是J3,J4,J5相继被删除,也呈现B图的两指针相遇的情况,所以并不能利用两指针相遇来判断队列为空还是为满。

可以有两种解决办法:

  • 其一是另设一个标志位以区别队列是“空”还是“满”
  • 其二是少用一个元素空间,约定以“队列头指针在队列尾指针的下一位置(指环状的下一个位置)”上,作队列满的操作

从上述分析可见,在C语言中不能用动态分配的一维数组来实现循环队列,如果用户的应用程序中设有循环队列,则必须为它设定一个最大队列长度,若用户无法预估所用队列的最大长度,则采用链队列

循环队列类型的模块说明如下:

typedef int QElemType, Status;

#define MAXQSIZE 100//最大队列长度

typedef struct
{
    QElemType* base;
    int front;//游标头指针,若队列不空,则指向队列头元素
    int reae;//游标尾指针,若队列不空,指向队列尾元素的下一个位置
}SqQueue;


//构造一个空队列
Status InitQueue(SqQueue* Q)
{
    Q->base = (QElemType*)malloc(sizeof(QElemType) * MAXQSIZE);
    if (!Q->base)
    {
        exit(0);
    }
    Q->front = Q->reae = 0;
}

//返回队列元素个数
int QueueLength(SqQueue Q)
{
    return(Q.reae - Q.front + MAXQSIZE) % MAXQSIZE;
    //用尾指针减去头指针计算出元素个数,加上队列总元素个数对队列总元素个数求余
}


//插入元素e为Q的新的队尾元素
Status EnQueue(SqQueue* Q, QElemType e)
{
    if ((Q->reae + 1) % MAXQSIZE == Q->front)
    {
        return ERROR//队列满
    }
    Q->base[Q->reae] = e;
    Q->reae = (Q->reae + 1) % MAXQSIZE;

    return OK;
}


//若队列不空,则删除Q的队头元素,用e返回其值,并返回OK,否则返回ERROR
Status DeQueue(SqQueue* Q, QElemType* e)
{
    if (Q->front == Q->reae)
    {
        return ERROR;
    }
    e = Q->base[Q->front];
    Q->front = (Q->front + 1) % MAXQSIZE;
    return OK;
}

队列有一个很经典的运用:

离散事件模拟

在日常生活中,我们经常会遇到许多为了维护社会正常秩序而需要排队的情景,这样一类活动的模拟程序通常需要用到队列和线性表之类的数据结构。

我们来模拟一下银行业务的模拟程序

假设某银行有4个窗口对外接待客户,从早晨的银行开门起不断有客户进入银行,由于每个窗口在某个时刻只能接待一个客户,因此在客户人数众多时需在每个窗口前顺次排队,对于刚进入银行的客户,如果某个窗口的业务员正空闲,则可上前办理业务,反之,若四个窗口均有客户所占,他便会排在人数最少的队伍后面。

现在需要编制一个程序以模拟银行这种业务活动并计算一天中客户在银行逗留的平均时间。

具体请看补充笔记

本文链接:

https://nullcode.fun/22.html
1 + 4 =
快来做第一个评论的人吧~