数据结构深入剖析（4）

一、队列的定义及实现
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;
}