队列（Queue）

队列的概念

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out) 的特点。
入队列：进行插入操作的一端称为队尾 。
出队列：进行删除操作的一端称为队头。

队列的实现

定义

#pragma once
#include<stdio.h>   /*printf*/
#include<stdbool.h> /*bool*/
#include<assert.h>  /*assert*/
#include<stdlib.h>  /*malloc*/

typedef int QDataType;
typedef struct QueueNode  //队列节点结构
{
	QDataType data;          //节点数据
	struct QueueNode* next;  //节点指针
}QueueNode;

typedef struct QueuePtr  //队列的链式结构
{
	QueueNode* phead;  //队头指针
	QueueNode* ptail;  //队尾指针
}LinkQueue;

//初始化队列
void QueueInit(LinkQueue* pQ);
//销毁队列
void QueueDestroy(LinkQueue* pQ);
//入队（尾插）
void QueuePush(LinkQueue* pQ, QDataType x);
//出队（头删）
void QueuePop(LinkQueue* pQ);
//获取队列元素个数
int QueueSize(LinkQueue* pQ);
//获取队头元素
QDataType QueueFront(LinkQueue* pQ);
//获取队尾元素
QDataType QueueBack(LinkQueue* pQ);
//检查队列是否为空
bool QueueEmpty(LinkQueue* pQ);

初始化与销毁

//初始化队列
void QueueInit(LinkQueue* pQ)
{
	//队列为空
	pQ->phead = pQ->ptail = NULL;
}

//销毁队列
void QueueDestroy(LinkQueue* pQ)
{
	QueueNode* cur = pQ->phead;
	while (cur)  //遍历链式队列
	{
		QueueNode* next = cur->next;
		free(cur);
		cur = next;
	}
	cur = NULL;
	pQ->phead = pQ->ptail = NULL;  //队列为空
}

入队与出队

//入队（尾插）
void QueuePush(LinkQueue* pQ, QDataType x)
{
	QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode)); //动态申请一个节点
	if (newnode == NULL)  //检查是否申请成功
	{
		perror("malloc");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;  //尾节点next指针置空

	if (pQ->phead == NULL)  //队列为空
	{
		pQ->phead = newnode;
	}
	else  //队列不为空
	{
		pQ->ptail->next = newnode;
	}
	pQ->ptail = newnode;   //更新队尾指针
}

//出队（头删）
void QueuePop(LinkQueue* pQ)
{
	if (pQ->phead == pQ->ptail)  //队列中只有一个节点
	{
		free(pQ->phead);
		pQ->phead = pQ->ptail = NULL;
	}
	else
	{
		QueueNode* next = pQ->phead->next;  //记录头节点的直接后继
		free(pQ->phead);  //释放头节点
		pQ->phead = next; //更新队头指针
	}
}

元素个数

//获取队列元素个数
//如果会频繁调用这个接口函数，可以在QueuePtr中加一个size记录数据个数
int QueueSize(LinkQueue* pQ)
{
	int size = 0;
	QueueNode* cur = pQ->phead;
	while (cur)  //遍历链表
	{
		size++;
		cur = cur->next;
	}
	return size;
}

头元素与尾元素

//获取队头元素
QDataType QueueFront(LinkQueue* pQ)
{
	return pQ->phead->data;
}

//获取队尾元素
QDataType QueueBack(LinkQueue* pQ)
{
	//assert(pQ);
	//assert(!QueueEmpty(pQ));  //队列不能为空
	return pQ->ptail->data;
}

是否为空

//检查队列是否为空，若为空返回true，否则返回false
bool QueueEmpty(LinkQueue* pQ)
{
	return pQ->phead == NULL && pQ->ptail == NULL;
}

void TestQueue()
{
	LinkQueue Q;
	QueueInit(&Q);

	QueuePush(&Q, 1);
	QueuePush(&Q, 2);
	QueuePush(&Q, 3);
	QueuePush(&Q, 4);
	//打印队列
	while (!QueueEmpty(&Q))
	{
		printf("%d ", QueueFront(&Q));  //获取队头元素
		QueuePop(&Q);  //出队
	}
	printf("\n");
}

/*
queue顺序存储实现
*/
#include <stdio.h>
#include <stdlib.h>

typedef struct queue
{
    int queuesize;   //数组的大小
    int head;
    int tail;      //队列的头和尾下标
    int *q;        //数组头指针
}Queue;

void InitQueue(Queue *Q, int queuesize)
{
    Q->q = (int *)malloc(sizeof(int) * queuesize); //分配内存
    if(NULL == Q->q)
    {  
        printf("Memory allocation failure");  
        exit(-1);
    }
    
    Q->tail = 0;
    Q->head = 0;
    Q->queuesize = queuesize;
}

//判断循环链表是否满，留一个预留空间不用
int isFullQueue(Queue *Q)  
{  
    if(Q->head == (Q->tail+1)%Q->queuesize)     //取余保证,空了一个
        return 1;
    else  
        return 0;
}

//判断是否为空  
int isEmptyQueue(Queue *Q)
{  
    if(Q->head == Q->tail)
        return 1;
    else
        return 0;
}

int EnQueue(Queue *Q, int key)
{
    if(isFullQueue(Q))  
        return 0;
    else
    {
        Q->q[Q->tail] = key;
        Q->tail = (Q->tail+1)%(Q->queuesize);
        return 1;
    }
}

int DeQueue(Queue *Q, int *val)
{
    if(isEmptyQueue(Q))
        return 0;
    else
    {
        *val = Q->q[Q->head];
        Q->head = (Q->head+1)%(Q->queuesize);
        return 1;
    }
}

int main()
{
    int a;
    Queue Q;
    InitQueue(&Q, 8);
    EnQueue(&Q, 11);
    EnQueue(&Q, 12);
    EnQueue(&Q, 13);
    EnQueue(&Q, 14);
    EnQueue(&Q, 15);
    EnQueue(&Q, 16);
    EnQueue(&Q, 17);

    DeQueue(&Q, &a);
    printf("%d\n", a);
    DeQueue(&Q, &a);
    printf("%d\n", a);
    DeQueue(&Q, &a);
    printf("%d\n", a);
    DeQueue(&Q, &a);
    printf("%d\n", a);
    DeQueue(&Q, &a);
    printf("%d\n", a);
    DeQueue(&Q, &a);
    printf("%d\n", a);
    DeQueue(&Q, &a);
    printf("%d\n", a);
  
    EnQueue(&Q, 199);
    DeQueue(&Q, &a);
    printf("%d\n", a);
    return 0;
}