3.6链队列

3.6链队列

.队列：只允许在一端进行插入，在另一端进行删除的线性表。

链队列：使用链表实现的队列；具有队头指针和队尾指针，指示队列元素所在的位置。

链队列特性：

• 只能队尾插入元素、在队头删除元素。
• 先进先出（First In First Out）的线性表，先进入的元素出队，后进入的元素才能出队。

优点：

• 相比普通的队列，元素出队时无需移动大量元素，只需移动头指针。
• 可动态分配空间，不需要预先分配大量存储空间。
• 适合处理用户排队等待的情况。

缺点：

• 需要为表中的逻辑关系增加额外的存储空间。

时间复杂度

• 读取时的时间复杂度为O(1)。
• 插入、删除时的时间复杂度为O(1)。

帆哥的代码：

#include <stdio.h>
#include <malloc.h>/*** 链队列的节点.*/
typedef struct LinkNode{int data;LinkNode* next;
}*LinkNodePtr;/*** 链队列.*/
typedef struct LinkQueue{LinkNodePtr front;LinkNodePtr rear;
}*LinkQueuePtr;/*** Construct an empty queue.*/
LinkQueuePtr initQueue(){LinkQueuePtr resultPtr = (LinkQueuePtr)malloc(sizeof(struct LinkQueue));//The header, the data is not useful.LinkNodePtr headerPtr = (LinkNodePtr)malloc(sizeof(struct LinkNodePtr));headerPtr->next = NULL;resultPtr->front = headerPtr;resultPtr->rear = headerPtr;return resultPtr;
}//Of initQueue/*** Output the queue.*/
void outputLinkQueue(LinkQueuePtr paraQueuePtr){LinkNodePtr tempPtr = paraQueuePtr->front->next;while (tempPtr != NULL) {printf("%d ", tempPtr->data);tempPtr = tempPtr->next;}//Of whileprintf("rn");
}//Of outputLinkQueue/*** Enqueue.*/
void enqueue(LinkQueuePtr paraQueuePtr, int paraElement) {//Step 1. Create a new nodeLinkNodePtr tempNodePtr = (LinkNodePtr)malloc(sizeof(struct LinkNode));tempNodePtr->data = paraElement;tempNodePtr->next = NULL;//Step 2. Link to the existing rearparaQueuePtr->rear->next = tempNodePtr;//Step 3.