007-队列

moc

1、基本概念
队列（queue）是一种 特殊的线性表；
队列仅在线性表的两端进行操作；
队头（Front）：取出数据元素的一端；
队尾（Rear）:   插入数据元素的一端。
队列不允许在中间位置插入元素或其他操作。
        队列是只允许在一端进行插入操作，在另一端进行删除操作的线性表。是一种先进先出的线性表（FIFO）.

常用操作：
        创建队列；
        销毁队列；
        清空队列；
        进队列；
        出队列；
        获取队头元素；
        获取队列的长度。
2、队列的线性存储
      同样由于队列是一种特殊的线性表，其实现也是可以通过线性表来完成的。
通过线性表的顺序存储来实现队列的顺序 存储。

// 创建一个队列  相当于 创建一个线性表
SeqQueue* SeqQueue_Create(int capacity)
{
        return SeqList_Create(capacity);
}

// 销毁一个队列  相当于 销毁一个线性表 
void SeqQueue_Destroy(SeqQueue* queue)
{
        SeqList_Destroy(queue);
}

// 清空一个队列  相当于 清空一个线性表 
void SeqQueue_Clear(SeqQueue* queue)
{
        SeqList_Clear(queue);
}

// 入队  相当于 向线性表添加一个元素
// 头插、尾插都可以，这里选择尾插法
int SeqQueue_Append(SeqQueue* queue, void* item)
{
        return SeqList_Insert(queue, item, SeqQueue_Length(queue));
}

// 出队 相当于 删除链表头部元素
void* SeqQueue_Retrieve(SeqQueue* queue)
{
        return SeqList_Delete(queue, 0);
}

// 获取队列头部元素 相当于 获取线性表头部元素
void* SeqQueue_Header(SeqQueue* queue)
{
        return SeqList_Get(queue, 0);
}

// 获取队列长度  相当于 获取线性表长度 
int SeqQueue_Length(SeqQueue* queue)
{
        return SeqList_Length(queue);
}

// 获取队列容量  相当于 获取线性表容量
int SeqQueue_Capacity(SeqQueue* queue)
{
        return SeqList_Capacity(queue);
}

3、队列的链式存储
和栈类似，队列的链式存储同样涉及到  ① 队列的业务结点向线性表业务结点的转换    ② 结点的生命周期的管理。

// 队列也是一种特殊的线性表
// 队列的业务结点的数据结构
typedef struct _tag_LinkQueueNode
{
        LinkListNode node;
        void* item;
}TLinkQueueNode;



// 创建一个队列  相当于 创建一个线性表
LinkQueue* LinkQueue_Create()
{
        return LinkList_Create();
}

// 销毁一个队列  相当于 销毁一个线性表 
// 结点的内存管理
void LinkQueue_Destroy(LinkQueue* queue)
{
        LinkQueue_Clear(queue);
        LinkList_Destroy(queue);
}


// 清空一个队列  需要把队列里的每个元素取出来  释放掉
void LinkQueue_Clear(LinkQueue* queue)
{
        while (LinkQueue_Length(queue) > 0)
        {
                LinkQueue_Retrieve(queue);
        }
        LinkList_Clear(queue);
}


// 入队  相当于 向线性表添加一个元素
// 头插、尾插都可以，这里选择尾插法
int LinkQueue_Append(LinkQueue* queue, void* item)
{
        int ret = 0;
        TLinkQueueNode *tmp = NULL;
        tmp = (TLinkQueueNode*)malloc(sizeof(TLinkQueueNode));
        if (tmp == NULL)
        {
                ret = -1;
                printf("Fun LinkQueue_Append() malloc error:%d", ret);
                return ret;
        }
        memset(tmp, 0, sizeof(TLinkQueueNode));
        tmp->item = item;
        // 需要把队列的业务结点 转换为 线性表的业务结点
         ret = LinkList_Insert(queue, (LinkListNode*)tmp, LinkList_Length(queue));
        if (ret != 0)
        {
                printf("Fun LinkList_Insert() error: %d\n", ret);
                if (tmp != NULL)
                {
                        free(tmp);
                        tmp = NULL;
                }
        }
        return ret;
}

// 从队列中删除一个元素 相当于  从线性表中删除一个元素
void* LinkQueue_Retrieve(LinkQueue* queue)
{
        TLinkQueueNode *tmp = NULL;
        void                   *ret = NULL;
        tmp = (TLinkQueueNode*)LinkList_Delete(queue, 0);
        if (tmp == NULL)
        {
                printf("Fun LinkList_Delete error\n");
                return NULL;
        }
        ret = tmp->item;
        if (tmp != NULL)
        {
                free(tmp);
        }
        return ret;
}

// 获取队列中头部元素 相当于  获取线性表的头部元素
void* LinkQueue_Header(LinkQueue* queue)
{
        TLinkQueueNode *tmp = NULL;
        void                   *ret = NULL;
        tmp = LinkList_Get(queue, 0);
        if (tmp == NULL)
        {
                printf("func LinkList_Get() reeor\n");
                return NULL;
        }
        return tmp->item;
}

// 求队列的长度 相当于 求线性表的长度
int LinkQueue_Length(LinkQueue* queue)
{
        return LinkList_Length(queue);
}

完整代码： 队列的顺序存储.zip (2.72 KB, 下载次数: 5)

2018-9-26 23:01 上传

点击文件名下载附件
队列的顺序存储

                 队列的链式存储.zip (2.98 KB, 下载次数: 6)

2018-9-26 23:01 上传

点击文件名下载附件
队列的链式存储