静态队列——循环队列
```
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <malloc.h>
/*
线性结构的常见应用之:队列
定义:
一种可以实现“先进先出”的存储结构
分类:
链式队列:链表
静态队列:数组(此处进行实现)
静态队列都必须是循环队列
循环队列:
1.静态队列为什么必须是循环队列
分配内存空间
2.循环队列需要几个参数
两个参数,不同场合有不同的含义
front与rear
3.各个参数的含义
1).队列初始化
front与rear的值都为0
2).队列非空
front代表队列的第一个元素
rear代表队列的最后一个有效元素的下一个元素
3).队列空
front与rear的值相等,但不一定为0
4.循环队列入队伪算法
1.将值放入r所代表的位置
2.r=(r+1)%数组长度
5.循环队列出队伪算法
1.f=(f+1)%数组长度
6.如何判断循环队列是否为空
1.如果f == r 则该队列为空
7.如何判断循环队列已满
两种方式:
1.多增加一个标识参数
2.少用一个元素,r f紧挨着
if((r+1)%数组长度 == f)
已满
else
未满
算法:
入队
出队
队列的具体应用:
所有和时间有关的操作
*/
typedef struct Queue
{
int *pBase;
int front;
int rear;
} QUEUE;
void init(QUEUE *);//初始化
bool en_queue(QUEUE *,int val);//入队
void traverse_queue(QUEUE *);//遍历
bool full_queue(QUEUE *);//判断是否满
bool emput_queue(QUEUE *pQ);//判断是否为空
bool out_queue(QUEUE *,int *pVal);//出队 保存出队的元素
int main()
{
int val;
QUEUE Q;
init(&Q);
en_queue(&Q,1);
en_queue(&Q,2);
en_queue(&Q,3);
traverse_queue(&Q);
printf("\n");
if(out_queue(&Q,&val))
{
printf("出队成功,出队的元素是:%d\n",val);
}
else
{
printf("出队失败!\n");
}
traverse_queue(&Q);
return 0;
}
bool emput_queue(QUEUE *pQ)
{
if(pQ->front==pQ->rear)
{
return true;
}
else
{
return false;
}
}
bool out_queue(QUEUE *pQ,int *pVal)
{
if(emput_queue(pQ))
{
return false;
}
else
{
*pVal = pQ->pBase[pQ->front];
pQ->front = (pQ->front+1)%6;
return true;
}
}
void traverse_queue(QUEUE *pQ)
{
int i = pQ->front;
while(i!=pQ->rear)
{
printf("%d ",pQ->pBase[i]);
i=(i+1)%6;
}
}
bool full_queue(QUEUE *pQ)
{
if((pQ->rear+1)%6==pQ->front)
{
return true;
}
else
{
return false;
}
}
bool en_queue(QUEUE *pQ,int val)
{
if(full_queue(pQ))
{
return false;
}
else
{
pQ->pBase[pQ->rear] = val;
pQ->rear = (pQ->rear+1)%6;
return true;
}
}
void init(QUEUE *pQ)
{
pQ->pBase = (int *)malloc(sizeof(int)*6);//创建数组长度为6的数组,并获取数组的首地址
pQ->front = 0;
pQ->rear = 0;
}
```
链式队列——链队列
```
#include <stdio.h>
#include <stdlib.h>
typedef struct QNode //结点结构
{
int data;
struct QNode *next;
}QNode,*QueuePtr;
typedef struct //队列的链表结构
{
//队头、尾指针
QueuePtr front;
QueuePtr rear;
}LinkQueue;
int main(void)
{
LinkQueue Q;
int i,e;
InitQueue(&Q);
for(i=0;i<5;i++){
EnQueue(&Q,i);
}
Display(&Q);
printf("\n");
i=DeQueue(&Q,&e);
printf("%d %d",i,e);
}
//入队 插入元素e为Q的新的队尾元素
int EnQueue(LinkQueue *Q,int e)
{
QueuePtr s = (QueuePtr)malloc(sizeof(QNode));
if(!s){
return 0;
}
s->data = e;
s->next = NULL;
Q->rear->next = s;//把拥有元素e新结点s赋值给原队尾结点的后继
Q->rear = s;//把当前的s设置为队尾结点,rear指向s
return 1;
}
//出队 若队列不空,删除Q的队头元素,用e返回其值,并返回1,否则返回0
int DeQueue(LinkQueue *Q,int *e){
QueuePtr p;
if(Q->front==Q->rear){
return 0;
}
p=Q->front->next;
*e = p->data;
Q->front->next = p->next;
if(Q->rear = p){
Q->rear = Q->front;
}
free(p);
return 1;
}
//建立一个空队列
void InitQueue(LinkQueue *Q)
{
Q->front=Q->rear = (QNode *)malloc(sizeof(QNode));
Q->rear->next = NULL;
}
//遍历
void Display(LinkQueue *Q){
QNode *p;
p = Q->front->next;
while(p!=NULL)
{
printf("%d ", p->data);
p = p->next;
}
}
```