嗨，这里是逻辑iOS技术号：一个让知识变得感性，让学习变得轻松！活跃的技术小站，希望给你的生活与技术带来意思不一样！关注公众号，回复“     面试题 ”，即可领取更多大厂面试题型哦~ 小逻辑相信我们的生活不止眼前的苟且，还有我们向往的诗和大厂高薪工作~

关于队列的介绍,在前面一篇 循环队列 已经说过。我们来看看第二种队列——链队列。物理结构为链式存储结构的队列，对内存空间的利用率更高。

 

链式队列的表示

是不是似曾相识的结构？链栈，再看看链栈的表示

区别：

栈，新的元素添加在栈顶，而且栈顶先出；队列，队尾进，队首出。

二者相反 所以，我们链队列的操作简单来说就是：

 

• 进入队列 ：Q.rear尾节点后追加新节点，将Q.rear指向新节点，新节点成队尾；

• 出队列 ：Q.front指向的首元节点出队列，Q.front指向首元节点的下一个节点

 

老规矩先定义数据结构

#define ERROR 0#define TRUE 1#define FALSE 0#define OK 1typedef int Status;/* Status是函数的类型,其值是函数结果状态代码，如OK等 */typedef int ElemType;/* ElemType类型根据实际情况而定，这里假设为int */typedef struct QueueNode {    ElemType data;    struct QueueNode *next;} QueueNode, *QueueNodePtr;typedef struct {    QueueNodePtr front;    QueueNodePtr rear;} LinkQueue;

（滑动显示更多）

初始化

先创建一个头节点，让Q.front和Q.rear指向头节点，头节点的next为NULL

/// 初始化Status InitQueue(LinkQueue *Q){    // 初始队列为空,只有头节点，不是有效数据的节点    *Q->front = *Q->rear = (QueueNodePtr)malloc(sizeof(QueueNode));    if (*Q->front == NULL) return ERROR;    // 头节点的后面为空    *Q->front->next = NULL;    return OK;}

（滑动显示更多 ）

判断队列为空

当队列为空时，恰入上图初始化的状态，只剩一个头节点，此时 Q.front == Q.rear

/// 判断是否为空Status QueueEmpty(LinkQueue Q){    if (Q.front == Q.rear) return TRUE;    return FALSE;}

（滑动显示更多 ）

进入队列

进入队列的操作，是将新元素，追加到rear指向的队尾之后，rear->next = 新元素，再将rear指向新元素，此时，新元素成为队尾。因为不受存储空间限制（内存占满另说），所以不需要一开始就判断是否队满，也没有队满的操作。

• 创建新节点p

• 追加到队尾

• 队列的rear指向p，标记成新队尾

Status EnQueue(LinkQueue *Q, ElemType e){    QueueNodePtr p = (QueueNodePtr)malloc(sizeof(QueueNode));    if (p == NULL) return ERROR;    p->data = e;    p->next = NULL;    // 追加到队尾    *Q->rear->next = p;    // 标记成队尾    *Q->rear = p;    return OK;}

（滑动显示更多 ）

出队列

出队列操作，是将首元节点从链队删除。

• 判断队列是否为空

• 找到队首节点head（此时已拿到节点，将该节点的data回调出去），等待删除

• 更改标记head后面的节点s为首元节点，即head->next

• 判断是否是最后一个节点，是的话，rear也指向头节点

• 释放原首节点head

Status DeQueue(LinkQueue *Q, ElemType *e){    if (QueueEmpty(*Q)) return ERROR;    QueueNodePtr head;    // 找到要删除的节点    head = *Q->front->next;    // 回调到函数外    *e = head->data;    // 更改头节点    *Q->front->next = head->next;    // 如果删到了队尾最后一个元素    if (*Q->rear == head)        *Q->rear = *Q->front;    // 删除临时指针指向的头节点    free(head);    return OK;}

（滑动显示更多 ）

清空

仅清空头节点以外的全部节点，有头节点在，清空完，还能继续EnQueue()操作。又回到初始化后的状态

/// 清空队列Status ClearQueue(LinkQueue *Q){    if (*Q->front->next == NULL) return ERROR;    QueueNodePtr temp, p; // 首元节点    *Q->rear = *Q->front;    p = *Q->front->next;    *Q->front->next = NULL;    // 此时只有temp指向首元节点    while (p) {        temp = p;        p = p->next;        free(temp);    }    return OK;}

（滑动显示更多 ）

销毁

销毁操作，和清空不一样，清空仅仅删除除头节点以外的所有节点，清空后还可以再入队。但是销毁已经彻底不使用，需要连头节点也一并free掉，所以代码中是从front开始，而非front->next。已free所有的节点

/// 销毁队列Status DestoryQueue(LinkQueue *Q){    if (*Q->front->next == NULL) return ERROR;    /*     说明，头节点也是个malloc开辟的，也需要释放     */    while (*Q->front) {        *Q->rear = *Q->front->next;        free(*Q->front);        *Q->front = *Q->rear;    }    return OK;}

（滑动显示更多 ）

获取队首

不更改队列，不破坏队列现有结构，仅查找。所以首元节的数据直接读取 Q.front->next->data，

Status GetHead(LinkQueue Q, ElemType *e){    if (QueueEmpty(*Q)) return ERROR;    *e = Q.front->next->data;    return OK;}

（滑动显示更多 ）