《数据结构和算法》之队列的创建、入列和出列

一，队列的定义

队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。

队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。队列的数据元素又称为队列元素。在队列中插入一个队列元素称为入队，从队列中删除一个队列元素称为出队。因为队列只允许在一端插入，在另一端删除，所以只有最早进入队列的元素才能最先从队列中删除，故队列又称为先进先出（FIFO—first in first out）线性表。

图 1 队列的实现形式示意图

二，队列的实现形式

1，队列的链式存储结构

队列既可以用链表实现，也可以用顺序表实现。跟栈相反的是，栈一般我们用顺序表来实现，而队列我们常用链表来实现，简称链队列。

定义的结构体如下：

typedef struct QNode
{
   ElemType data;
   struct QNode *next;
}QNode, *QueuePrt;

typedef struct
{
    QueuePrt front,rear; // 队头、尾指针
}LinkQueue;

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

《数据结构和算法》之队列的创建、入列和出列

图2 链队列的结构图

当为空队列的时候，front与rear都会指向头结点。

2，创建一个队列

创建一个队列要完成两个任务：一是在内存中创建一个头结点，二是将队列中的头结点和尾指针都指向这个生成的头结点，因为此时是空队列。

initQueue(LinkQueue *q)
{
    q->front = q->rear = (QueuePrt)malloc(sizeof(QNode));
    if(!q->front)
        exit(0);
    q->front->next = NULL;
}

3，入队列操作

入队列的操作过程如图3所示，要插入的元素是e2结点，这个时候将rear指针指向e2结点，则p指针失去作用，就如第三步显示的那样成功入队列。

《数据结构和算法》之队列的创建、入列和出列

图3 入队列示意图

InsertQueue(LinkQueue *q, ElemType e)
{
    QueuePrt p;
    P = (QueuePrt)malloc(sizeof(QNode));
    if( p == NULL)
        exit(0);
    p->data = e;
    p->next =NULL;
    q->rear->next = p;
    q->rear = p;
}

4，出队列操作

出队列操作是将队列中的第一个元素移出，队头指针是不需要改变的，改变头结点的next指针即可。

《数据结构和算法》之队列的创建、入列和出列

图4 出队列的操作示意图

出队列有一个特殊情况，如果原队列只有一个元素，这个时候就需要处理一下尾部指针。
《数据结构和算法》之队列的创建、入列和出列

图5 只有一个元素的时候

DeleteQueue(LinkQueue *q, ElemType *e)
{
    QueuePrt p;
    if( q->front == q->rear )
        return;
    p = q->front->next;
    *e = p->data;
    q->front->next = p->next;
    if( q->rear == p)
        q->rear = q->front;
    free(p);
}

秒客网

《数据结构和算法》之队列的创建、入列和出列

相关文章