C/CPP与数据结构-第二节 栈tack和队列queue （二）

队列Queue

1. 基本概念
   1. 队列是一种特殊的线性表
   2. 队列仅在线性表的两端进行操作
   3. 队头(Front)：取出数据元素的一端
   4. 队尾(Rear)：插入数据元素的一端
   5. 队列不允许在中间部位进行操作！
   6. 队列是只允许在一端进行插入操作，而在另一端进行删除操作的线性表
   7. 队列是一种先进先出（First In Fist Out）的线性表，简称FIFO,允许插入的一端称为队尾，允许删除的一端称为队头。

   8. 如下图

      

2. Queue的常用操作

    //创建队列
    Queue* Queue_Create();
    //销毁队列
    void Queue_Destroy(Queue* queue);
    //清空队列
    void Queue_Clear(Queue* queue);
    //进入队列 
    int Queue_Append(Queue* queue, void* item);
    //出队列
    void* Queue_Retrieve(Queue* queue);
    //获取队头元素
    void* Queue_Header(Queue* queue);
    //获取队列的长度
    int Queue_Length(Queue* queue);
   

3. 队列的顺序存储与链式存储分析
   1. 用数组来模拟队列
      1. 从数组的尾部入队列，从数组的0号位置出队列
   2. 用链表来模拟队列
      1. 从链表的尾部入队列，从链表的0位置出队列
      2. 要注意内存管理

队列的顺序存储设计

#define _CRT_SECURE_NO_WARNINGS
#include<stdlib.h>
#include<string.h>
#include<stdio.h>
#include"seqqueue.h"
#include"seqlist.h"
//创建一个队列相当于创建一个顺序表
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, SeqList_Length(queue));;
}

//出队列，相当于删除顺序表0号元素
void* SeqQueue_Retrieve(SeqQueue* queue) {

	return SeqList_Delete(queue,0);
}

//获取队列头相当于获取顺序表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);
}

//main.c
#define _CRT_SECURE_NO_WARNINGS
#include<stdlib.h>
#include<string.h>
#include<stdio.h>
#include"seqqueue.h"

void main() {

	int i = 0;
	int a[10];
	SeqQueue *queue = NULL;
	for ( i = 0; i < 10; i++)
	{
		a[i] = i + 1;
	}

	queue = SeqQueue_Create(10);
	//向队列中添加元素
	for ( i = 0; i < 10; i++)
	{
		SeqQueue_Append(queue, &a[i]);
	}
	//获取队列的属性
	printf("capacity :%d \n", SeqQueue_Capacity(queue));
	printf("len :%d \n",SeqQueue_Length(queue));
	printf("queue :%d \n", *((int*)SeqQueue_Header(queue)));

	//销毁队列
	while (SeqQueue_Length(queue)>0)
	{
		printf("retrieve :%d \n", *((int *)SeqQueue_Retrieve(queue)));
	}
	SeqQueue_Destroy(queue);

	system("pause");
	return;
}

队列的链式存储设计

#define _CRT_SECURE_NO_WARNINGS
#include<stdlib.h>
#include<string.h>
#include<stdio.h>
#include"linkqueue.h"
#include"LinkList.h"

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 (LinkList_Length(queue)>0)
	{
		LinkQueue_Retrieve(queue);
	}
}

//向队列尾部添加元素
int LinkQueue_Append(LinkQueue* queue, void* item) {
	//1. 将队列的节点转化为链表的节点
	TLinkQueueNode *tem = NULL;
	int ret = 0;
	tem = malloc(sizeof(TLinkQueueNode));
	if (tem == NULL)
	{
		return  -1;
	}
	tem->item = item;
	//2. 向链表的节点尾部插入元素
	ret = LinkList_Insert(queue, tem, LinkList_Length(queue));
	if (ret != 0)
	{
		//3. 插入失败，释放内存
		free(item);
		return ret;
	}
	return ret;
}
//删除堆头元素
void* LinkQueue_Retrieve(LinkQueue* queue) {
	TLinkQueueNode *temp = NULL;
	void *item = NULL;
	temp = (TLinkQueueNode *)LinkList_Delete(queue, 0);
	if (temp != NULL)
	{
		//出队列时节点释放
		item = temp->item;
		free(temp);
	}
	return item;
}

//获取队列头部
void* LinkQueue_Header(LinkQueue* queue) {
	TLinkQueueNode *tem = NULL;
	tem = (TLinkQueueNode *)LinkList_Get(queue, 0);
	if (tem == NULL)
	{
		return NULL;
	}
	return tem->item;
}

int LinkQueue_Length(LinkQueue* queue) {
	return LinkList_Length(queue);
}

//main.c
#define _CRT_SECURE_NO_WARNINGS
#include<stdlib.h>
#include<string.h>
#include<stdio.h>
#include"linkqueue.h"

void main() {
	int i, a[10];
	LinkQueue *lq = NULL;
	for ( i = 0; i < 10; i++)
	{
		a[i] = i + 1;
	}
	//创建
	lq = LinkQueue_Create();
	//加入
	for ( i = 0; i < 10; i++)
	{
		LinkQueue_Append(lq, &a[i]);
	}

	//属性
	printf("len: %d \n", LinkQueue_Length(lq));
	printf("header :%d \n", *((int *)LinkQueue_Header(lq)));
	
	//出队列
	while (LinkQueue_Length(lq)>0)
	{
		printf("ret : %d \n", *((int *)LinkQueue_Retrieve(lq)));
	}

	//销毁队列
	LinkQueue_Destroy(lq);
	system("pause");
	return;
}