队列的基本操作（实现链式栈）_给定一个初始为空的栈和一系列进栈,出栈操作(链队列)

一、熟悉队列的基本概念
只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表
（1）进行插入操作的一端称为队尾（入队列）
（2）进行删除操作的一端称为队头（出队列）
（3)队列具有先进先出（FIFO）的特性
二、 队列的性质
队列是一种操作受限制的线性表
三、 队列存储结构
 1、顺序队列：
（1）队头不动，出队列时队头后的所有元素向前移动
缺陷：操作时如果出队列比较多，要搬移大量元素
（2）队头移动，出队列时队头向后移动一个位置
缺陷：可能会发生假溢出（顺序队列因多次入队列和出队列操作后出现的尚有存储空间但不能再进行
入队列操作的溢出）
真溢出：顺序队列最大存储空间已经存满而又要求进行入队列操作所引起的溢出
2、循环队列：
循环队列（解决“假溢出”的办法就是后面满了，从头再开始，将头尾相接的顺序存储队列称为循环队列）
(rear + 1) % (空间大小) == front则队满
循环队列如何解决队列空或者满？
（1）少用一个存储单元：（队尾指针加一等于队头）
（2）设置一个标记位：（对头，队尾在同一位置：flag = 1存满了；flag = 0空）
（3）设置一个计数器：（count=0空；count等于空间总大小 满了）

3、链式队列：特殊的单链表，只在单链表上进行头删尾插的操作

4、优先级队列：带有优先级的队列称为优先级队列

队列具有先进先出的特性，即最先进入队列的元素将被最先出队列

有时也需要把进入队列中的元素分优先级（如线性调度），出队列时首先选择优先级最高的元素出队列（优先级高先被服务VIP），对于优先级相同的元素则按照先进先出的原则出队列

即优先级队列的出队列操作不是直接将队头元素出队列，而是把队列中优先级最高的元素出队列

四、实现链式栈

.h

# pragma once
# include<stdio.h>
# include<stdlib.h>
# include<string.h>
# include<assert.h>

//实现链式队列的以下操作：
typedef int DataType;
typedef struct Node
{
	DataType _data;
	struct Node* _pNext;
}Node, *PNode;

typedef struct Queue
{
	PNode _pHead;
	PNode _pTail;
}Queue;

// 队列的初始化 
void QueueInit(Queue* q);

// 入队列 
void QueuePush(Queue* q, DataType data);

// 出队列 
void QueuePop(Queue* q);

// 取队头元素 
DataType QueueFront(Queue* q);

// 取队尾元素 
DataType QueueBack(Queue* q);

// 获取队列中元素的个数 
int QueueSize(Queue* q);

// 检测队列是否为空 
int QueueEmpty(Queue* q);
PNode BuyNode(DataType data)
{
	PNode pNewNode = (PNode)malloc(sizeof(Node));
	if (NULL == pNewNode)
	{
		assert(0);
		return NULL;
	}
	pNewNode->_data = data;
	pNewNode->_pNext = NULL;
	return pNewNode;
}

.c

# define _CRT_SECURE_NO_WARNINGS 1
# include"Queue.h"
void QueueInit(Queue* q)
{
	assert(q);
	q->_pHead = q->_pTail = NULL;
}
void QueuePush(Queue* q, DataType data)
{
	assert(q);
	if (NULL == q->_pHead)
		q->_pHead = q->_pTail = BuyNode(data);
	else
	{
		q->_pTail->_pNext = BuyNode(data);
		q->_pTail = q->_pTail->_pNext;
	}
}
void QueuePop(Queue* q)
{
	PNode pDelNode = q->_pHead;
	if (pDelNode)
	{
		q->_pHead= pDelNode->_pNext;
		free(pDelNode);
	}
}
DataType QueueFront(Queue* q)
{
	assert(q);
	return q->_pHead->_data;
}
DataType QueueBack(Queue* q)
{
	assert(q);
	return q->_pTail->_data;
}
int QueueSize(Queue* q)
{
	int count = 0;
	PNode pCur = q->_pHead;
	while (pCur)
	{
		++count;
		pCur = pCur->_pNext;
	}
	return count;
}
int QueueEmpty(Queue* q)
{
	return NULL == q->_pHead;
}