|
顺序队列，就是数组，不多赘述
链式队列就是用链表来实现队列，像链表一样，在头部增加头部指针指向头结点，在尾部增加尾部指针指向队尾节点。
代码如下：
/*
链式队列，也就是用链表实现的对列，用指针指向头结点做front,尾部也来一个指针指向rear，而当front和rear相等时，队列为空
*/
#include <stdio.h>
#include <stdlib.h>
typedef struct LinkQueue//节点
{
int data;
struct LinkQueue *next;
}MyQueue;
typedef struct//存放头和尾指针，能够找到这两
{
MyQueue *front,*rear;//分别指向头和尾
}pQueue;
//初始化
void init(pQueue *q)
{
q->front = (MyQueue *)malloc(sizeof(MyQueue));
if(q->front == NULL)
{
printf("ERROR\n");
exit(1);
}
q->rear = q->front;//rear只用到指针作用，无需分配内存
q->rear->next = NULL;
}
//入队
void enQueue(pQueue *q, int x)
{
MyQueue *pNew = (MyQueue *)malloc(sizeof(MyQueue));
if(pNew == NULL)
{
printf("ERROR\n");
exit(1);
}
pNew->data = x;
pNew->next = NULL;
q->rear->next = pNew;//将pNew连接到末尾
q->rear = pNew;//将尾指针指向新插入的尾结点
}
//出队
void outQueue(pQueue *q)
{
if(q->rear == q->front)
{
printf("对为空\n");
return ;
}
MyQueue *p = q->front->next;//指向第一个节点
q->front->next = p->next;
if(q->rear == p)//如果只有一个元素
{
q->rear = q->front;
}
free(p);
p = NULL;
}
//遍历
void display(pQueue *q)
{
if(q->rear == q->front)
{
printf("对为空\n");
return ;
}
MyQueue *p = q->front->next;
while(p != q->rear->next)
{
printf("%d\n",p->data);
p = p->next;
}
}
int main()
{
pQueue *p = (pQueue *)malloc(sizeof(pQueue));
init(p);
//下面一堆实验
/*int i = 1;
printf("入5个\n");
for(i = 1;i < 6; i++)
{
enQueue(p,i);
}
//printf("出对一个\n");
//outQueue(p);
display(p);
enQueue(p,7);
printf("入一个7\n");
display(p);
printf("出对5次\n");
for(i = 1;i < 6; i++)
{
outQueue(p);
}
display(p);
printf("入队5个元素\n");
for(i = 1;i < 6; i++)//入队5个元素
{
enQueue(p,i);
}
display(p);
printf("出两个\n");
outQueue(p);
outQueue(p);
display(p);*/
delete(p);
p = NULL;
return 0;
}
循环队列：
说到循环队列，先说顺序队列，
在顺序队列中，front作为队列头部下标，rear作为队列尾部下标，当队列为空时，front == rear。当有元素入队，放入rear下标元素中，然后rear后移一位，入队就按照这个规程往后。这样很方便但会产生一个假溢出的问题，如下图：
如图所见，front前面还有空位，但rear已经溢出，明明还有多余位置，但系统已经判断溢出，造成很大浪费。
那怎么解决？循环队列：
代码如下：
#define MAX 5
typedef struct Queue
{
int data[MAX];
int front;
int rear;
}MyQueue;
//初始化
void init(MyQueue *q)
{
q->front = 0;
q->rear = 0;
}
//入队
void enQueue(MyQueue *q,int x)
{
if((q->rear + 1)%MAX == q->front)
{
printf("队满\n");
return;
}
q->data[q->rear] = x;
q->rear = (q->rear + 1)%MAX;
//printf("%d入队\n",x);
}
//出队
void outQueue(MyQueue *q)
{
if(q->front == q->rear)
{
printf("队空\n");
return ;
}
q->front = (q->front + 1)%MAX;
}
//遍历
void display(MyQueue *q)
{
int i = q->front;
while(i%MAX != q->rear)
{
printf("i%MAX = %d,data = %d\n",i%MAX,q->data[i%MAX]);
i++;
}
}
//队列长度
int getLength(MyQueue *q)
{
return ((q->rear - q->front + MAX) % MAX);
}
| 
转播
