.队列：只允许在一端进行插入，在另一端进行删除的线性表。
链队列：使用链表实现的队列；具有队头指针和队尾指针，指示队列元素所在的位置。
链队列特性：
- 只能队尾插入元素、在队头删除元素。
- 先进先出（First In First Out）的线性表，先进入的元素出队，后进入的元素才能出队。
优点：
- 相比普通的队列，元素出队时无需移动大量元素，只需移动头指针。
- 可动态分配空间，不需要预先分配大量存储空间。
- 适合处理用户排队等待的情况。
缺点：
- 需要为表中的逻辑关系增加额外的存储空间。
时间复杂度
- 读取时的时间复杂度为O(1)。
- 插入、删除时的时间复杂度为O(1)。
帆哥的代码：
#include#include typedef struct LinkNode{ int data; LinkNode* next; }*LinkNodePtr; typedef struct LinkQueue{ LinkNodePtr front; LinkNodePtr rear; }*LinkQueuePtr; 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 void outputLinkQueue(LinkQueuePtr paraQueuePtr){ LinkNodePtr tempPtr = paraQueuePtr->front->next; while (tempPtr != NULL) { printf("%d ", tempPtr->data); tempPtr = tempPtr->next; }//Of while printf("rn"); }//Of outputLinkQueue void enqueue(LinkQueuePtr paraQueuePtr, int paraElement) { //Step 1. Create a new node LinkNodePtr tempNodePtr = (LinkNodePtr)malloc(sizeof(struct LinkNode)); tempNodePtr->data = paraElement; tempNodePtr->next = NULL; //Step 2. Link to the existing rear paraQueuePtr->rear->next = tempNodePtr; //Step 3. It is the new rear paraQueuePtr->rear = tempNodePtr; }//Of enqueue int dequeue(LinkQueuePtr paraQueuePtr) { int resultValue; LinkNodePtr tempNodePtr; //Step 1. Is the queue empty? if (paraQueuePtr->front == paraQueuePtr->rear) { printf("The queue is empty.rn"); return -1; }//Of if //Step 2. Change the queue. tempNodePtr = paraQueuePtr->front->next; resultValue = tempNodePtr->data; paraQueuePtr->front->next = paraQueuePtr->front->next->next; if (paraQueuePtr->rear == tempNodePtr) { paraQueuePtr->rear = paraQueuePtr->front; }//Of if //Step 3. Free space. // free(tempNodePtr); tempNodePtr = NULL; //Step 4. Return. return resultValue; }//Of enqueue void testLinkQueue(){ LinkQueuePtr tempQueuePtr; tempQueuePtr = initQueue(); enqueue(tempQueuePtr, 10); enqueue(tempQueuePtr, 30); enqueue(tempQueuePtr, 50); outputLinkQueue(tempQueuePtr); printf("dequeue gets %drn", dequeue(tempQueuePtr)); printf("dequeue gets %drn", dequeue(tempQueuePtr)); printf("dequeue gets %drn", dequeue(tempQueuePtr)); printf("dequeue gets %drn", dequeue(tempQueuePtr)); enqueue(tempQueuePtr, 8); outputLinkQueue(tempQueuePtr); }//Of testLinkQueue int main(){ testLinkQueue(); return 1; }//Of main
帆哥的结果：
10 30 50 dequeue gets 10 dequeue gets 30 dequeue gets 50 The queue is empty. dequeue gets -1 8 Press any key to continue
创建链队列：
//创建链队列的节点
typedef struct LinkNode{
int data;
LinkNode next;
};
//链队列
typedef struct LinkQueue{
LinkNodePtr front; //队头指针
LinkNodePtr rear; //队尾指针
};
初始化：
//Construct an empty queue. 初始化一个空的队列
LinkQueuePtr initQueue(){
LinkQueuePtr resultPtr = (LinkQueuePtr)malloc(sizeof(struct LinkQueue));
//The herader, the data is not useful.
LinkNodePtr headerPtr = (LinkNodePtr)malloc(sizeof(struct LinkNodePtr));
header->next = NULL;
resultPtr->front = headerPtr;
resultPtr->rear = headerPtr;
return resultPtr;
}
输出：
//Output the queue 输出队列
void outputLinkQueue(LinkQueuePtr paraQueuePtr){
LinkNodePtr tempPtr = paraQueuePtr->front->next;
while(tempPtr != NULL){
printf("%d",tempPtr->data);
tempPtr =tempPtr->next;
}
printf("rn");
}
插入：
//Enqueue 插入队列
viod enqueue(LinkQueuePtr paraQueuePtr, int paraElement){
//Step 1.Create a new node 创造一个节点
LinkNodePtr tempNodePtr = (LinkNodePtr)malloc(sizeof(struct LinkNOde));
tempNodePtr->data = paraElement;
tempNodePtr->next = NULL;
//Step 2.Link to the existing rear 联系现存的后面的部分
paraQueuePtr->rear->next = tempNodePtr;
//Step 3.It's the new rear. 变成了新的后部（更新）
//Dequeue. 出队
//@return The value of the header 返回队头
int dequeue(LinkQueuePtr paraQueuePtr){
int resultValue;
LinkNodePtr tempNodePtr;
//Step 1.Is the queue empty? 判断这个队列是否是空的队列
if (paraQueuePtr->front == paraQueuePtr->rear){
printf("The queue is empty.rn"); //队列是空的，无法删除（当队头和队尾相等的时候，就证明是空的队)
return -1;
}
//Step 2.Change the queue. //改变队列的节点
tempNodePtr = paraQueue->ftont->next;
resultValue = tempNodePtr->data;
paraQueuePtr->front->next = paraQueuePtr->front->next->next;
if(paraQueuePtr->rear == tempNodePtr){
paraQueuePtr->rear == paraQueuePtr->front;
}
//Step 3. Free space. 删除它
//free(tempNodePtr);
tempNodePtr = NULL;
//Step 4. Return.
return resultValue;
}
测试：
//Unit test. 测试数据
void testLinkQueue(){
LinkQueuePtr tempQueuePtr;
tempQueuePtr = initQueue();
enqueue(tempQueuePtr,1);
enqueue(tempQueuePtr,2);
enqueue(tempQueuePtr,3);
outputLinkQueue(tempQueuePtr);
printf("dequeue gets %drn",dequeue(tempQueuePtr));
printf("dequeue gets %drn",dequeue(tempQueuePtr));
printf("dequeue gets %drn",dequeue(tempQueuePtr));
printf("dequeue gets %drn",dequeue(tempQueuePtr));
enqueue(tempLinkQueue,520);
outputLinkQueue(tempQueuePtr);
}
//The entrance.
int main(){
testLinkQueue();
return 1;
}
}
全部代码：
#include#include //创建链队列的节点 typedef struct LinkNode{ int data; LinkNode next; }; //链队列 typedef struct LinkQueue{ LinkNodePtr front; //队头指针 LinkNodePtr rear; //队尾指针 }; //Construct an empty queue. 初始化一个空的队列 LinkQueuePtr initQueue(){ LinkQueuePtr resultPtr = (LinkQueuePtr)malloc(sizeof(struct LinkQueue)); //The herader, the data is not useful. LinkNodePtr headerPtr = (LinkNodePtr)malloc(sizeof(struct LinkNodePtr)); header->next = NULL; resultPtr->front = headerPtr; resultPtr->rear = headerPtr; return resultPtr; } //Output the queue 输出队列 void outputLinkQueue(LinkQueuePtr paraQueuePtr){ LinkNodePtr tempPtr = paraQueuePtr->front->next; while(tempPtr != NULL){ printf("%d",tempPtr->data); tempPtr =tempPtr->next; } printf("rn"); } //Enqueue 插入队列 viod enqueue(LinkQueuePtr paraQueuePtr, int paraElement){ //Step 1.Create a new node 创造一个节点 LinkNodePtr tempNodePtr = (LinkNodePtr)malloc(sizeof(struct LinkNOde)); tempNodePtr->data = paraElement; tempNodePtr->next = NULL; //Step 2.Link to the existing rear 联系现存的后面的部分 paraQueuePtr->rear->next = tempNodePtr; //Step 3.It's the new rear. 变成了新的后部（更新） //Dequeue. 出队 //@return The value of the header 返回队头 int dequeue(LinkQueuePtr paraQueuePtr){ int resultValue; LinkNodePtr tempNodePtr; //Step 1.Is the queue empty? 判断这个队列是否是空的队列 if (paraQueuePtr->front == paraQueuePtr->rear){ printf("The queue is empty.rn"); //队列是空的，无法删除（当队头和队尾相等的时候，就证明是空的队) return -1; } //Step 2.Change the queue. //改变队列的节点 tempNodePtr = paraQueue->ftont->next; resultValue = tempNodePtr->data; paraQueuePtr->front->next = paraQueuePtr->front->next->next; if(paraQueuePtr->rear == tempNodePtr){ paraQueuePtr->rear == paraQueuePtr->front; } //Step 3. Free space. 删除它 //free(tempNodePtr); tempNodePtr = NULL; //Step 4. Return. return resultValue; } //Unit test. 测试数据 void testLinkQueue(){ LinkQueuePtr tempQueuePtr; tempQueuePtr = initQueue(); enqueue(tempQueuePtr,1); enqueue(tempQueuePtr,2); enqueue(tempQueuePtr,3); outputLinkQueue(tempQueuePtr); printf("dequeue gets %drn",dequeue(tempQueuePtr)); printf("dequeue gets %drn",dequeue(tempQueuePtr)); printf("dequeue gets %drn",dequeue(tempQueuePtr)); printf("dequeue gets %drn",dequeue(tempQueuePtr)); enqueue(tempLinkQueue,520); outputLinkQueue(tempQueuePtr); } //The entrance. int main(){ testLinkQueue(); return 1; } }
