五、栈和队列(二)、队列

数据结构目录

1.定义

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

• 与栈相反，队列是一种先进先出(First In First Out,FIFO)的线性表
• 与栈相同的是，队列也是一种重要的线性结构，实现一个队列同样需要顺序表或链表作为基础

队列

2.队列的链式存储结构

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

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

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

我们将队头指针指向链队列的头结点,而队尾指针指向终端结点。(注:头结点不是必要的，但我们加上后操作更方便)

队列

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

空队列

(1)创建一个队列

创建一个队列要完成两个任务：

1. 创建头结点
2. 将队列的头指针和尾指针都指向头结点，生成空队列

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

(2) 入队列操作

入队列操作

如图所示，入队列就是在队尾插入一个新的结点

Status insertQueue(LinkQueue *q,ElemType e){
    QueuePtr p = (QueuePtr)malloc(sizeof(QNode));
    if (!p) {
        return ERROR;
    }
    p->data = e;
    p->next = NULL;
    q->rear->next = p;
    q->rear = p;
    
    return OK;
}

(3)出队列操作

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

出队列操作

如果原队列只有一个元素，那么我们就应该处理一下队尾指针，让它指向头结点

处理一个元素的情况

Status deleteQueue(LinkQueue *q,ElemType *e){
    if (q->rear == q->front) {
        //队尾和队头指向相同，表示空队列
        return ERROR;
    }
    QueuePtr p = q->front->next;
    //返回值
    *e = p->data;
    
    //头结点指向下一个元素
    q->front->next = p->next;
    if (q->rear == p) {
        //只有一个元素的队列
        q->rear = q->front;
    }
    free(p);
    return OK;
}

(4)销毁一个队列

由于链队列建立在内存的动态区，因此当一个队列不再有用时应当把它及时销毁掉，以免过多的占用内存空间

Status destroyQueue(LinkQueue *q){
    while (q->front) {
        QueuePtr p = q->front;
        q->front = q->front->next;
        free(p);
    }
    q->front = q->rear = NULL;
    return OK;
}