队列的定义
队列（Queue） 是一种操作受限的线性表，只允许在表的一端进行插入，而在表的另一端进行删除。
队列操作的特性：先进先出（Frist In First Out）
队列的顺序存储–>循环队列
方案1：牺牲一个单元来区分队空和队满
实现：
// 顺序循环队列
// 方案1：牺牲一个单元来区分队空和队满
// 队尾指针指向 队尾元素的后一个位置（下一个应该插入的位置）
#define MaxSize 50 //定义队列中元素的最大个数
typedef int ElemType;
typedef struct{
ElemType data[MaxSize]; //存放队列元素
int front; //队头指针
int rear; //队尾指针
}SeqQueue;
// 初始化队列
void InitQueue(SeqQueue& q)
{
q.front = q.rear = 0;
}
// 判断队列是否为空
bool QueueEmpty(SeqQueue& q)
{
if (q.rear == q.front) //队空条件
return true;
else
return false;
}
// 入队
bool EnQueue(SeqQueue& q, ElemType x)
{
if ((q.rear+1) % MaxSize == q.front)
return false; //队列满则报错
q.data[q.rear] = x; //将x插入队尾
q.rear = (q.rear + 1) % MaxSize; //队尾指针后移
return true;
}
// 出队
bool DeQueue(SeqQueue& q, ElemType& x)
{
if (q.rear == q.front)
return false; //队空则报错
x = q.data[q.front];
q.front = (q.front + 1) % MaxSize; //队头指针后移
return true;
}
// 获取队头元素
bool GetHead(SeqQueue& q, ElemType& x)
{
if (q.rear == q.front)
return false; //队空则报错
x = q.data[q.front];
return true;
}
// 队列中元素的个数
int QueueNum(SeqQueue& q)
{
return (q.rear - q.front + MaxSize) % MaxSize;
}
方案2：增设表示元素个数的变量（不牺牲存储单元）
实现：
// 方案2：不浪费存储空间
// 设置一个变量size，记录队列当中存储元素的个数
// 队尾指针指向 队尾元素的后一个位置（下一个应该插入的位置）
#define MaxSize 50
typedef int ElemType;
typedef struct{
ElemType data[MaxSize];
int front;
int rear;
int size; //队列当前长度
}SeqQueue;
// 初始化队列
void InitQueue(SeqQueue& q)
{
q.front = q.rear = 0;
q.size = 0; //队列当前长度为0
}
// 判断队列是否为空
bool QueueEmpty(SeqQueue& q)
{
if (q.size==0) //队空条件
return true;
else
return false;
}
// 入队
bool EnQueue(SeqQueue& q, ElemType x)
{
if (q.size==MaxSize)
return false; //队列满则报错
q.data[q.rear] = x; //将x插入队尾
q.rear = (q.rear + 1) % MaxSize; //队尾指针后移
q.size++;
return true;
}
// 出队
bool DeQueue(SeqQueue& q, ElemType& x)
{
if (q.size==0)
return false; //队空则报错
x = q.data[q.front];
q.front = (q.front + 1) % MaxSize; //队头指针后移
q.size--;
return true;
}
// 获取队头元素
bool GetHead(SeqQueue& q, ElemType& x)
{
if (q.size==0)
return false; //队空则报错
x = q.data[q.front];
return true;
}
// 队列中元素的个数
int QueueNum(SeqQueue& q)
{
return q.size;
}
方案3：增设tag数据成员区分队空队满（不牺牲存储单元）
实现：
// 方案3：设置tag数据成员，以区分队满还是队空
// 不浪费存储空间
#define MaxSize 50
typedef int ElemType;
typedef struct{
ElemType data[MaxSize];
int front;
int rear;
int tag; //最近进行的是删除/插入操作
}SeqQueue;
// 初始化队列
void InitQueue(SeqQueue& q)
{
q.front = q.rear = 0;
q.tag = 0;
}
// 判断队列是否为空
bool IsEmpty(SeqQueue& q)
{
if (q.front == q.rear && q.tag == 0) //队空条件
return true;
else
return false;
}
// 入队
// 只有插入操作，才可能导致队满
bool EnQueue(SeqQueue& q, ElemType x)
{
if (q.front == q.rear && q.tag == 1)
return false; //队满则报错
q.data[q.rear] = x;
q.rear = (q.rear + 1) % MaxSize; //队尾指针加1取模
q.tag = 1; //每次插入操作成功时，都令tag=1;
return true;
}
// 出队
// 只有删除操作，才可能导致队空
bool EnQueue(SeqQueue& q, ElemType& x)
{
if (q.front == q.rear && q.tag == 0)
return false; //队空则报错
x = q.data[q.front];
q.front = (q.front + 1) % MaxSize; //队头指针加1取模
q.tag = 0; //每次出队成功时，都令tag=0;
return true;
}
// 获取队头元素
bool GetHead(SeqQueue& q, ElemType& x)
{
if (q.front==q.rear && q.tag==0)
return false; //队空则报错
x = q.data[q.front];
return true;
}
链式队列的实现
带头结点的链式队列
// 队列的链式存储实现(带头节点)
typedef int ElemType;
typedef struct LinkNode{
ElemType data;
struct LinkNode* next;
}LinkNode;
typedef struct{
LinkNode* front; //头指针指向头结点
LinkNode* rear; //尾指针指向尾节点
int length; //队列长度
}LinkQueue;
// 初始化队列
void InitQueue(LinkQueue& q)
{
//初始时front，rear都指向头结点
q.front = q.rear = (LinkNode*)malloc(sizeof(LinkNode)); //建立头结点
q.front->next = NULL;
q.length = 0;
}
// 判断队列是否为空
bool IsEmpty(LinkQueue& q)
{
if (q.front == q.rear)
return true;
else
return false;
}
// 入队
bool EnQueue(LinkQueue& q, ElemType x)
{
LinkNode* s = (LinkNode*)malloc(sizeof(LinkNode));
s->data = x;
s->next = NULL;
q.rear->next = s; //新节点插入到rear之后
q.rear = s; //修改表尾指针
q.length++;
return true;
}
// 出队
bool DeQueue(LinkQueue& q, ElemType& x)
{
if (q.front == q.rear)
return false; //空队
LinkNode* p = q.front->next;
x = p->data; //用变量x返回队头元素
q.front->next = p->next; //修改头结点的next指针
if (q.rear = p) //若是最后一个结点出队
q.rear = q.front;
free(p); //释放节点空间
q.length--;
return true;
}
// 求队列长度
int LengthQueue(LinkQueue& q)
{
return q.length;
}
不带头结点的链式队列
// 链式队列的实现(不带头结点)
typedef int ElemType;
typedef struct LinkNode{
ElemType data;
struct LinkNode* next;
}LinkNode;
typedef struct{
LinkNode* front;
LinkNode* rear;
int length;
}LinkQueue;
// 初始化队列
void InitQueue(LinkQueue& q)
{
//初始时 front，rear都指向NULL
q.front = NULL;
q.rear = NULL;
}
// 判断队列是否为空
bool IsEmpty(LinkQueue& q)
{
if (q.front == NULL)
return true;
else
return false;
}
// 入队
void EnQueue(LinkQueue& q, ElemType x)
{
LinkNode* s = (LinkNode*)malloc(sizeof(LinkNode));
s->data = x;
s->next = NULL;
if (q.front == NULL) //在空队列中插入第一个元素
{
q.front = s;
q.rear = s;
}
else
{
q.rear->next = s; // 新节点插入到rear节点之后
q.rear = s; // 修改rear指针
}
q.length++;
}
// 出队
bool DeQueue(LinkQueue& q, ElemType& x)
{
if (q.front == NULL)
return false; //队空则报错
LinkNode* p = q.front; //p指向此次出队的节点
x = p->data; //用变量x返回队头指针
q.front = p->next; //修改front指针
if (q.rear == p) //此次是最后一个节点出队
{
q.front = NULL; //front指向NULL
q.rear = NULL; //rear指向NULL
}
free(p);
q.length--;
return true;
}
// 求队列长度
int LengthQueue(LinkQueue& q)
{
int count = 0;
LinkNode* p = q.front;
while (p != NULL)
{
++count;
p = p->next;
}
return count;
}