• 周六. 3月 2nd, 2024

    数据结构笔记 5. 队列

    root

    3月 22, 2022 #队列

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

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

    1、 队列的抽象数据类型

    ADT 队列(Queue)
    Data
        同线性表。元素具有相同的类型,相信元素具有前驱和后继关系。
    Operation
        InitQueue(*Q):初始化操作, 建立一个空队列Q。
        DestroyQueue(*Q):若队列Q存在,则销毁它。
        ClearQueue(*Q):将队列Q清空
        QueueEmpty(Q); 若队列Q为空返回true,否则false.
        GetHead(Q, *e); 若队列Q存在且非空,用e返回队列Q的队头元素
        EnQueue(*Q, e); 若队列Q存在,插入新元素e到队列Q中并成为队尾元素。
        DeQueue(*Q, *e); 删除队列Q中队头元素,并用e返回其值。
        QueueLength(Q); 返回队列Q的元素个数
    endADT

    2. 循环队列

    2.1 队列顺序存储的不足

    我们假设一个队列有n个元素,则顺序存储的队列需要建立一个大于n的数组,并把队列的所有元素存储在数组的前n个单元,数组下标为0的一端即是队头。所谓的入队列操作,其实就是在队尾追加一个元素,不需要移动任何元素,因此时间复杂度为O(1)

    与栈不同的是,队列元素的出队是在队头,即下标为0的位置,那也就是意味着队列中的所有元素都得向前移动,以保证队头,也就是下标为0的位置不为空,此时时间复杂度为O(n)

    2.2 循环队列的定义

    我们把队列的这种头尾相接的顺序存储结构称为循环队列

    队列满的条件是(rear+1)%queueSize == front(rear队尾指针,front队头指针, queueSize队列的的大小)

    队列长度:(rear-front+queueSize)%queueSize

    循环队列顺序存储结构代码如下:

    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];
        Q->front = (Q->front + 1) % MAXSIZE; /*front指针向后移一位置,若到最后则转到数组头部*/
        return OK;
    }

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

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

    我们将头指针指向链队列的头结点,而队尾指针指向终端结点。

    空队列时,front和rear都指向头结点。

    链队列的结构为:

    typedef int QElemType; /*QElemType类型根据实际情况而定,这里假设为int*/
    typedef struct QNode /*结点结构*/
    {
        QElemType data;
        struct QNode *next;
    }QNode, *QueuePtr;
    
    typedef struct   /*队列的链表结构*/
    {
        QueuePtr front, rear; /*队头,队尾指针*/
    }LinkQueue;
    

    3.1 入队操作

    /*插入元素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;
    }

    3.2 出队操作

    出队操作时,就是头结点的后继结点出队,将头结点的后继改为它后面的结点,若链表除头结点外只剩一个元素时,则需将rear指向头结点。

    /*若队列不空,删除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. 循环队列是事先申请好空间,使用期间不释放,而链队列,每次申请和释放结点会存在一些时间开销。
    3. 空间上,循环队列固定长度,所以就有了存储元素个数和空间浪费的问题,链队列不存在这个问题。空间上链队列更加灵活。

    在可以确定队列长度最大值的情况下,建议用循环队列,否则无法预估队列长度时,用链队列。

    root