队列
注：不足及错误请指正
+qq1366963396讨论
队列（queue）是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。
是一种先进先出的线性表。
一.循环队列
struct Queue
{
int data[MAXSIZE];
int front;//头指针
int rear;//尾指针
};
循环队列
如果不是循环队列，出列是在队头，那么后面所有元素都必须向前移动，可是为什么又要全部移动呢，队头可以不在下标为0的位置呀，但是如果一直再往队尾插入，会导致队列假溢出，也就是数组越界，而前面还有空闲的地方。所以，我们想到用循环队列，即队列的头尾相接的顺序存储结构。
但是又有问题了，什么时候表示为队满呢，rear==front?可是队空的时候也是rear==front呀。所以有以下两种办法：
*****设置标志量flag，当front==rear&&flag=0时队列为空，front==reat&&flag=1时队列为满。
*****还有就是可以保留一个元素空间，也就是说，当队列满时数组中还有一个空闲单元，例如上图所示就认为队列已满，重点讨论第二种办法。
//初始化空队列
void InitQueue(Queue* Q)
{
Q->front = 0;
Q->rear = 0;
}
//判队空
bool IsEmpty(Queue* Q)
{
if (Q->front ==Q->rear)
return true;
return false;
}
//判队满
bool IsFull(Queue* Q)
{
if ((Q->rear + 1) % MAXSIZE == Q->front)
return true;
return false;
}
//求队列长度
int QueueLength(Queue* Q)
{
return (Q->rear - Q->front + MAXSIZE)%MAXSIZE;
}
//入队
bool EnQueue(Queue* Q, int data)
{
if (IsFull(Q))//判队满
return false;
Q->data[Q->rear] = data;
Q->rear = (Q->rear + 1) % MAXSIZE;//front后移
return true;
}
//出队
int DeQueue(Queue* Q, int data)
{
if (IsEmpty(Q))//判队空
return NULL;
data = Q->data[Q->front];
Q->front = (Q->front++) % MAXSIZE;//front后移
return data;
}
//建队
void CreatQueue(Queue* Q)
{
InitQueue(Q);
int data = 0;
int i = 1; //计数
while (1)
{
printf("请输入队列第%d个元素:", i);
scanf("%d", &data);
if (data==-1||IsFull(Q))//队满-1表示结束
break;
EnQueue(Q, data);//入队
i++;
}
}
二.链式存储队列
struct QueueNode//节点结构
{
int data;
QueueNode* next;
};
struct LinkQueue//队列的链表结构
{
QueueNode* front;//队头指针
QueueNode* rear;//队尾指针
};
//初始化空队
void InitQueue(LinkQueue* Q)
{
Q->front =Q->rear =(QueueNode*)malloc(sizeof(QueueNode));//生成头结点
Q->front->next= NULL;//置空队
Q->rear->next = NULL;
}
//置空队
void SetEmptyQueue(LinkQueue* Q)
{
Q->front->next = NULL;
Q->front = Q->rear;
}
//判队空
bool IsEmpty(LinkQueue* Q)
{
if (Q->front == Q->rear)
return true;
return false;
}
//求队列长度
int LengthQueuue(LinkQueue* Q,int length)
{
QueueNode* p = Q->front->next;
while (p)
{
length++;
p = p->next;
}
return length;
}
//入队
void EnQueue(LinkQueue* Q, int data)
{
QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode));//申请新节点
newNode->data = data;
newNode->next = NULL;
Q->rear->next = newNode;//尾节点指向新节点
Q->rear = newNode;//新节点成为尾节点
}
//出队
int DeQueue(LinkQueue* Q, int data)
{
if (IsEmpty(Q))//判队空
return NULL;
QueueNode* p = (QueueNode*)malloc(sizeof(QueueNode));//申请p存放队头节点
p = Q->front->next;
data = p->data;//取得删除的队头节点值
Q->front->next = p->next;//头结点指向删除节点的后一个节点
if (Q->rear == p)//若队头是队尾，删除后将rear指向头结点
Q->rear = Q->front;
free(p);
return data;
}
//建队
void CreatQueue(LinkQueue* Q)
{
int data = 0;
int i = 0;
while (1)
{
printf("请输入第%d个元素:", ++i);
scanf("%d", &data);
if (data==-1)//-1表示结束
break;
EnQueue(Q, data);//入队
}
}
应用：球钟问题（栈和队列）
基本程序与上文一致
球钟问题描述：球钟是一个利用球的移动来记录时间的简单装置。他有三个可以容纳若干球的指示器：分钟指示器，五分钟指示器，小时指示器。若分钟指示器中有两个球，5分钟指示器中有6个球，小时指示器中有5个球，则时间为5:32.
工作原理：每过一分钟，球钟就会从球队列的队首取出一个球放入分钟指示器，分钟指示器可最多容纳四个球。当放入第五个球时，在分钟指示器的4个球就会按照他们被放入时的相反顺序加入球队列的队尾。而第五个球就会进入分钟指示器。依此类推，五分钟指示器最多可放11个球，小时指示器最多可放11个球。当小时指示器放入第12个球时，原来的11个球按照他们被放入时的相反顺序加入球队列的队尾，然后第12个球也回到队尾。这时三个指示器均为空，回到初始状态，从而形成一个循环。因此，该球钟表示的时间范围时从00：00到11：59；
bool TrueBallQueue(LinkQueue* Q)//是否与原来状态相同
{
QueueNode* p = Q->front->next;
for (int i = 1; i <= 27; i++)
{
if (p->data != i)
return false;
p = p->next;
}
return true;
}
//主程序
int main()
{
Stack* mStack = (Stack*)malloc(sizeof(Stack));//分钟栈
Stack* fmStack = (Stack*)malloc(sizeof(Stack)); //五分钟栈
Stack*hStack = (Stack*)malloc(sizeof(Stack));//小时栈
LinkQueue* ballQueue = (LinkQueue*)malloc(sizeof(LinkQueue));球队列
int data=0;
int time = 0;//记录计满次数
//队列，栈初始化
InitStack(mStack);//分钟栈
InitStack(fmStack);//五分钟栈
InitStack(hStack);//小时栈
InitQueue(ballQueue);//球队列
//给队列装球
int i = 0;
for (i = 1; i <= 27; i++)
{
EnQueue(ballQueue,i);
}
while (1)//从球队列出球进入分钟指示器
{
data = DeQueue(ballQueue,data);//球出队
if (mStack->top == 3)//分钟是否计满
{
int i = 0;
int temp;
//分钟指示器的球进入球队列
for (i = 0; i < 4; i++)
{
temp = PopStack(mStack);
EnQueue(ballQueue, temp);
}
if (fmStack->top == 10)//5分钟指示器是否计满
{
//计满退栈
for (i = 0; i < 11; i++)
{
temp = PopStack(fmStack);
EnQueue(ballQueue, temp);
}
if (hStack->top == 10)//小时指示器是否计满
{
//计满退栈
for (i = 0; i < 11; i++)
{
temp = PopStack(hStack);
EnQueue(ballQueue, temp);
}
EnQueue(ballQueue, data);
time++;//计满一次，即12小时
if (TrueBallQueue(ballQueue))//回到初始状态
{
break;
}
}
else
{
PushStack(hStack, data);
}
}
else
{
PushStack(fmStack, data);
}
}
else
{
PushStack(mStack, data);
}
}
time = (time * 12) / 24;
printf("需要经过%d天球队列恢复初始状态！\n", time);
return 0;
}
