队列"/>
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("\r\n");
}//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.
更多推荐
3.6链队列
发布评论