队列的实现

基本概念

队列（queue）是一种抽象数据类型，与栈相比，队列是一种先进先出(FIFO first in frist out)的线性表，它只允许在表的一端进行插入，而在另一端删除元素。和日常生活中的排队相似，最早进入队列的元素最早离开。在队列中，允许插入元素的一端叫做队尾（rear），允许删除的一端叫做队头(front)。
建立队列必须为其申请静态或者动态的连续存储空间，并设置两个指针进行管理，队尾指针和队头指针，当插入一个元素（入队）时，队尾指针加一，而删除一个元素（出队）时，队头指针减一。
队列的结构如下图所示：

队列

队列的定义及其实现

队列定义

在C语言中，用两个结构体表示链式队列，其中第一个结构体表示队列结点，包含指针域和数据域第二个结构体表示队列，包含一个队头和队尾。如下所示：

typedef struct qNode {
    int data;
    struct qNode *next;
}qNode,*queuePtr;

typedef struct queueList{
    queuePtr front;
    queuePtr rear;
}queueList;

接口定义

根据队列特点，队列有以下接口定义，包括初始化，入队，出队，队列情空和队列销毁等，具体如下所示：

#pragma once
#ifndef QUEUE_H
#define QUEUE_H
#define INIT_QUEUE_SIZE 100
#define bool int
#define true 1
#define false 0
//
typedef struct qNode {
    int data;
    struct qNode *next;
}qNode,*queuePtr;

typedef struct queueList{
    queuePtr front;
    queuePtr rear;
}queueList;

queueList* initQueue(); //初始化
queueList* enQueue(queueList* queue,int element); //入队
queueList* deQueue(queueList* queue); //出队
void clearQueue(queueList*  queue); //清空队列
void destoryQueue(queueList*  queue); //销毁队列
void queueTraverse(queueList*  queue); //遍历队列
int getLength(queueList*  queue); //返回队列长度

int locateQueue(queueList*  queue, int element); //查找指定元素的位置
#endif

接口实现

根据队列接口定义，接口实现如下所示：

• 初始化
  链式队列的初始化包括整个队列的初始化和队列结点的初始化，并需要将队尾指针指向队头指针，具体实现如下所示

queueList* initQueue()
{
    
    queueList *queue = (queueList*)malloc(sizeof(queueList));
    if (!queue)
    {
        printf("空间分配失败！");
        exit(0);
    }

    queue->front = queue->rear = (queuePtr)malloc(sizeof(qNode));
    if (!queue->front)
    {
        printf("空间分配失败！");
    }
    queue->front->next = NULL;
    return queue;
}

• 入队
  入队操作主要是以下步骤：
  1). 生成临时结点，并将数据赋值给临时结点的数据域；
  2). 队尾指针指向临时结点；
  3). 新插入的临时结点变为队尾;

以上过程可以用以下动态图表示：

入队

以上过程可以有以下代码实现

queueList* enQueue(queueList* queue, int element)
{
    queuePtr temp=(queuePtr)malloc(sizeof(qNode));
    if (!temp)
    {
        printf("错误！");
        exit(0);
    }
    temp->data = element;
    temp->next = NULL;
    queue->rear->next = temp;
    queue->rear = temp;  //新插入的元素自动成为队尾
    return queue;
}

• 出队
  队列的出队操作主要有以下步骤实现：
  1). 将头部赋值给一个临时结点；
  2). 将队列头部的后继变成队列的头部
  3). 删除临时结点。
  可由以下动态图表示这一过程，如下所示：

  
  出队
  

  以上过程可以由以下代码实现

queueList* deQueue(queueList *queue) //出队
{
    queuePtr temp = NULL;
    if (queue->rear == queue->front)
    {
        printf("空队列！");
        exit(0);
    }
    temp = queue->front->next;  //临时=头部
    queue->front->next = temp->next;  // 头部 = 头部的后继
    if (queue->rear==temp)
    {
        queue->rear = queue->front;
    }
    free(temp);
    return queue;
}

• 遍历队列
  链式队列的遍历与单向链表一样，从队头开始，输出每一个结点的数据，具体代码实现如下所示;

void queueTraverse(queueList*  queue)
{
    if (queue->rear==queue->front->next)
    {
        printf("空队列！");
        exit(0);
    }
    queuePtr p;
    p = queue->front;
    while (queue->rear != p)
    {
        printf("%d", p->next->data);
        p = p->next;
    }
}

• 队列长度
  队列长度与遍历队列相似，从队头开始，直到队尾结束。具体如下代码所示：

int getLength(queueList*  queue)
{
    int length = 0;
    if (queue->front == queue->rear)
    {
        length = 0;
        
    }
    
    queuePtr p = queue->front;
    while (p != queue->rear)
    {
        length++;
        p = p->next;
    }
    return length;
}

• 查找元素
  查找指定元素在队列中的位置，与求取队列长度类似，从队头开始遍历，若找到指定的元素，则返回计数器的值。具体代码实现如下所示：

int locateQueue(queueList*  queue, int element)
{
    int index = 0;
    if (queue->rear == queue->front)
    {
        return -1;
    }
    queuePtr p;
    p = queue->front;
    while (p != queue->rear)
    {
        if (p->next->data == element)
        {
            return index;
        }
        
        p = p->next;
        index++;
    }
    return index;
}

• 清空队列
  清空队列需要将队尾指针指向队头，并从队头开始，回收每一个结点，具体如下所示：

void clearQueue(queueList*  queue)
{
    queuePtr p, q;
    queue->front = queue->rear;
    p = queue->front->next;

    queue->front->next = NULL;
    while (p)
    {
        q = p;
        p = p->next;
        free(q);
    }
}

• 销毁队列
  队列的销毁主要包括以下步骤：
  1). 将队尾指向队头下一个节点的地址（第1个节点）
  2). 回收队头
  3). 将队头指向队尾（相当于第1个节点变成了队头，然后依次第2个第3个直到没有下一个节点，也就是 Q->front == NULL 的时候）
  具体实现如下所示

void destoryQueue(queueList*  queue)
{
    while (queue->front)
    {
        queue->rear = queue->front->next; //1)
        free(queue->front);  //2)
        queue->front = queue->rear;  //3)
    }
    free(queue);
}

教材：数据结构（C语言）清华大学出版社
辅助学习网站：https://visualgo.net