一、队列的定义及实现
1.队列的定义
--队列是一种特殊的线性表
--队列仅在线性表的两端进行操作
-----队头(Front):取出数据元素的一端。
-----队尾(Rear):插入数据元素的一端。
2.队列的性质:先进先出(FIFO)
3.队列的一些常用操作
--创建队列
--销毁队列
--清空队列
--进队列
--出队列
--获取队头元素
--获取队列长度
4.顺序队列的瓶颈
(1)顺序队列
------线性表的第一个元素作为队头
------线性表的最后一个元素作为队尾
--入队的新元素是在线性表的最后,时间复杂度为O(1)
--出队时需要将后续的所有元素向前移动,时间复杂度为O(n)
(2)顺序队列的优化方案
--定义front使其始终代表队头的下标。
--出队时将队头元素返回,且front++
--定义rear使其始终代表队尾下一个元素的下标。
--入队时将新元素插入,且rear++
(3)顺序队列的关键状态
--初始状态:length == 0, front == 0, rear == 0;
--空队列状态:length == 0, front == rear;
--满队列状态:length == capacity, front == rear;
(4)循环使用队列中的空间
--入队:rear = (rear + 1) % capacity;
--出队:front= (front + 1)% capacity;
实现:
//SeqQueue.h头文件
#ifndef SEQQUEUE_H
#define SEQQUEUE_H
typedef void SeqQueue;
SeqQueue* SeqQueue_Create(int capacity);
void SeqQueue_Destroy(SeqQueue* queue);
void SeqQueue_Clear(SeqQueue* queue);
int SeqQueue_Append(SeqQueue* queue,void* item);
void* SeqQueue_Retrive(SeqQueue* queue);
void* SeqQueue_Header(SeqQueue* queue);
int SeqQueue_Length(SeqQueue* queue);
int SeqQueue_Capacity(SeqQueue* queue);
#endif
//SeqQueue.c文件
#include "SeqQueue.h"
#include
#include
typedef unsigned int TSeqQueueNode;
typedef struct _tag_SeqQueue
{
int capacity;
int length;
int front;
int rear;
TSeqQueueNode* node;
}TSeqQueue;
SeqQueue* SeqQueue_Create(int capacity)
{
TSeqQueue* ret = NULL;
if(capacity >= 0){
ret = (TSeqQueue*)malloc(sizeof(TSeqQueue) + sizeof(TSeqQueueNode) * capacity);
}
if(ret != NULL){
ret->capacity = capacity;
ret->length = 0;
ret->front = 0;
ret->rear = 0;
ret->node = (TSeqQueueNode*)(ret+1);
}
}
void SeqQueue_Destroy(SeqQueue* queue)
{
free(queue);
}
void SeqQueue_Clear(SeqQueue* queue)
{
TSeqQueue* squeue = (TSeqQueue*)queue;
if(squeue != NULL){
squeue->length = 0;
squeue->front = 0;
squeue->rear = 0;
}
}
int SeqQueue_Append(SeqQueue* queue,void* item)
{
TSeqQueue* squeue = (TSeqQueue*)queue;
int ret = (squeue != NULL) && (item != NULL) && (squeue->length + 1 <= squeue->capacity );
if(ret){
squeue->node[squeue->rear] = (TSeqQueueNode)item;
squeue->rear = (squeue->rear + 1) % squeue->capacity;
squeue->length++;
}
}
void* SeqQueue_Retrive(SeqQueue* queue)
{
TSeqQueue* squeue = (TSeqQueue*)queue;
void* ret = SeqQueue_Header(queue);
if(ret != NULL){
squeue->front = (squeue->front + 1) % squeue->capacity;
squeue->length--;
}
return ret;
}
void* SeqQueue_Header(SeqQueue* queue)
{
TSeqQueue* squeue = (TSeqQueue*)queue;
void* ret = NULL;
if((squeue != NULL) && (squeue->length > 0)){
ret = (void*)(squeue->node[squeue->front]);
}
return ret;
}
int SeqQueue_Length(SeqQueue* queue)
{
TSeqQueue* squeue = (TSeqQueue*)queue;
int ret = -1;
if(squeue != NULL){
ret = squeue->length;
}
return ret;
}
int SeqQueue_Capacity(SeqQueue* queue)
{
TSeqQueue* squeue = (TSeqQueue*)queue;
int ret = -1;
if(squeue != NULL){
ret = squeue->capacity;
}
return ret;
}
5.链式队列的瓶颈
(1)链式队列
------线性表的第一个元素作为队头
------线性表的最后一个元素作为队尾
--入队的新元素是在线性表的最后,时间复杂度为O(n)
--出队的元素即链表的第一个元素,时间复杂度为O(1)
(2)链式队列的优化方案
--定义rear指针始终指向链表中的最后一个元素
---入队时将新元素通过rear指针插入队尾,且将rear指向新元素
(3)链式队列的关键状态
--空队列状态:front == NULL, rear == NULL;
--关键操作
----入队:
rear->next = node;
rear = node;
node->next = NULL;
----出队:
front = front->next;
(4)实现
//LinkQueue.h
#ifndef LINKQUEUE_H_
#define LINKQUEUE_H_
typedef void LinkQueue;
LinkQueue* LinkQueue_Create();
void LinkQueue_Destroy(LinkQueue* queue);
void LinkQueue_Clear(LinkQueue* queue);
int LinkQueue_Append(LinkQueue* queue,void* item);
void* LinkQueue_Retrive(LinkQueue* queue);
void* LinkQueue_Header(LinkQueue* queue);
int LinkQueue_Length(LinkQueue* queue);
#endif
//LinkQueue.c
#include "LinkQueue.h"
#include
#include
typedef struct _tag_LinkQueueNode TLinkQueueNode;
struct _tag_LinkQueueNode
{
TLinkQueueNode* next;
void* item;
};
typedef struct _tag_LinkQueue
{
TLinkQueueNode* front;
TLinkQueueNode* rear;
int length;
}TLinkQueue;
LinkQueue* LinkQueue_Create()
{
TLinkQueue* ret = (TLinkQueue*)malloc(sizeof(TLinkQueue));
if(ret != NULL){
ret->front = NULL;
ret->rear = NULL;
ret->length = 0;
}
return ret;
}
void LinkQueue_Destroy(LinkQueue* queue)
{
LinkQueue_Clear(queue);
free(queue);
}
int LinkQueue_Length(LinkQueue* queue)
{
TLinkQueue* squeue = (TLinkQueue*)queue;
int ret = -1;
if(squeue != NULL){
ret = squeue->length;
}
return ret;
}
void LinkQueue_Clear(LinkQueue* queue)
{
while(LinkQueue_Length(queue) > 0){
LinkQueue_Retrive(queue);
}
}
int LinkQueue_Append(LinkQueue* queue,void* item)
{
TLinkQueue* squeue = (TLinkQueue*)queue;
TLinkQueueNode* node = (TLinkQueueNode*)malloc(sizeof(TLinkQueueNode));
int ret = (squeue != NULL) && (node != NULL) && (item != NULL);
if(ret){
node->item = item;
if(squeue->length > 0){
squeue->rear->next = node;
squeue->rear = node;
node->next = NULL;
}else{
squeue->front = node;
squeue->rear = node;
node->next = NULL;
}
squeue->length++;
}else{
free(node);
}
return ret;
}
void* LinkQueue_Retrive(LinkQueue* queue)
{
TLinkQueue* squeue = (TLinkQueue*)queue;
TLinkQueueNode* node = NULL;
void* ret = NULL;
if((squeue != NULL) && (squeue->length > 0)){
node = squeue->front;
squeue->front = node->next;
ret = node->item;
free(node);
squeue->length--;
if(squeue->length == 0){
squeue->front = NULL;
squeue->rear = NULL;
}
}
return ret;
}
void* LinkQueue_Header(LinkQueue* queue)
{
TLinkQueue* squeue = (TLinkQueue*)queue;
void* ret = NULL;
if((squeue != NULL) && (squeue->length > 0)){
ret = squeue->front->item;
}
return ret;
}
阅读(1892) | 评论(0) | 转发(1) |