概念
-
队列也是一种线性表，是一种先进先出的线性结构（FIFO）。队列只允许在表的一端进行插入（入队）、删除（出队）操作。
-
允许插入的一端称为队尾，允许删除的一端称为队头。
队列的基本操作
- 入队EnterQueue：在队列的队尾插入一个元素
- 出队DeleteQueue：将队列的队头元素出队
- 判空IsEmpty：判断队列是否有元素存在
- 判满IsFull：判断队列是否已满
- front：返回队头元素
数组实现队列
顺序队列
- 一开始令front和rear等于-1，表示队空。入队第一个元素时front和rear都赋值为0，然后每入队一个元素rear+1，每出队一个元素front+1，当front等于rear时队空两个整数重新赋值为-1。
- 代码：
#include <stdio.h>
#define MAX_SIZE 8//定义队列的最大空间
struct queue
{
int front; //索引队头
int rear; //索引队尾
int data[MAX_SIZE]; //存放队列元素的数组
};
int IsEmpty(struct queue *p)//判空
{
if (p->front == -1 && p->rear == -1)
{
return 0;
}
else
{
return 1;
}
}
int IsFull(struct queue *p) //判满
{
if (p->rear == MAX_SIZE - 1)
{
return 0;
}
else
{
return 1;
}
}
int EnterQueue(struct queue *p, int num) //入队
{
if (!IsFull(p))
{
printf("队列已满\n");
return 0;
}
else if (!IsEmpty(p))//入队第一个元素
{
p->front = 0;
p->rear = 0;
}
else
{
p->rear++;
}
p->data[p->rear] = num;
}
int DeleteQueue(struct queue *p) //出队
{
if (!IsEmpty(p))
{
printf("队列已空\n");
return 0;
}
else if (p->front == p->rear)
{
p->rear = -1;
p->front = -1;
return 0;
}
else
{
p->front++;
}
}
void front(struct queue *p) //打印队首元素
{
printf("队首元素：%d\n", p->data[p->front]);
}
void printQ(struct queue *p) //打印队列
{
printf("\n^front|\n");
int i = p->front;
while (i <= p->rear)
{
printf("%d\n", p->data[i++]);
}
printf("^rear|\n");
}
int main()
{
int i = 0;
struct queue q = {-1, -1, 0};
for (i = 0; i < 10; i++)
{
EnterQueue(&q, 2 * i + 1);
}
printQ(&q);
DeleteQueue(&q);
DeleteQueue(&q);
printQ(&q);
return 0;
}
- 终端显示：
队列已满
队列已满
^front|
1
3
5
7
9
11
13
15
^rear|
^front|
5
7
9
11
13
15
^rear|
循环队列
-
虽然上述的功能实现了，但是有一个很大的问题。因为入队时rear只往后走，出队时front也是往后走，当rear走到数组末尾时就停下了，而front前面的空间就浪费了，这种现象被称为假溢出
-
为了解决这个问题我们可以构造出来一个逻辑上环形的数组，当front和rear走到数组末尾后会从数组头开始再往后走。要实现也不难，只需要front和rear在++的时候先+1再对数组的最大值取余就行了。
-
代码：
#include <stdio.h>
#define MAX_SIZE 8
struct queue
{
int front;
int rear;
int n; //方便起见定义队列内元素个数
int data[MAX_SIZE];
};
int IsEmpty(struct queue *p)
{
if (p->front == -1 && p->rear == -1)
{
return 0;
}
else
{
return 1;
}
}
int IsFull(struct queue *p)
{
int i = p->rear;//不要动rear，赋值给i去判断
if ((i + 1) % MAX_SIZE == p->front) //rear和front头尾相连的情况
{
return 0;
}
else
{
return 1;
}
}
int EnterQueue(struct queue *p, int num)
{
if (!IsFull(p))
{
printf("队列已满\n");
return 0;
}
else if (!IsEmpty(p))
{
p->front = 0;
p->rear = 0;
}
else
{
p->rear = (p->rear + 1) % MAX_SIZE;
}
p->data[p->rear] = num;
p->n++; //元素数量+1
}
int DeleteQueue(struct queue *p)
{
if (!IsEmpty(p))
{
printf("队列已空\n");
return 0;
}
else if (p->front == p->rear)
{
p->rear = -1;
p->front = -1;
p->n = 0; //元素数量置零
return 0;
}
else
{
p->front = (p->front + 1) % MAX_SIZE;
p->n--; //元素数量-1
}
}
void front(struct queue *p)
{
printf("队首元素：%d\n", p->data[p->front]);
}
int printQ(struct queue *p)
{
printf("\n^front|\n");
int i = p->front;
if (p->n == 0)
{
printf("队列已空\n");
return 0;
}
else if (i <= p->rear)
{
while (i < p->rear)
{
printf("%d\n", p->data[i]);
i++;
}
}
else //队尾在数组前面的情况
{
for (int j = 0; j < p->n; j++)
{
printf("%d\n", p->data[i]);
i = (i + 1) % MAX_SIZE;
}
}
printf("^rear|\n");
}
int main()
{
int i = 0;
struct queue q = {-1, -1, 0, 0};
for (i = 0; i < MAX_SIZE+2; i++) //把队列排满，就是这么大气
{
EnterQueue(&q, i + 1);
}
printQ(&q);
DeleteQueue(&q); //出队三个元素
DeleteQueue(&q);
DeleteQueue(&q);
printQ(&q);
EnterQueue(&q, 666); //再进来两个
EnterQueue(&q, 233);
printQ(&q);
return 0;
}
- 终端显示
队列已满
队列已满
^front|
1
2
3
4
5
6
7
8
^rear|
^front|
4
5
6
7
8
^rear|
^front|
4
5
6
7
8
666
233
^rear|
链表实现队列
- 定义两个指针分别指向队头和队尾，队头即链表头。入队时使用队尾指针把新节点给尾节点的next，指针后移；出队时队头指针后移的同时释放头节点。
- 代码：
#include <stdio.h>
#include <stdlib.h>
struct node //定义节点
{
int data;
struct node *next;
};
struct queue //定义队列
{
struct node *front;
struct node *rear;
int num; //节点数
int size; //定义队列大小
};
int IsEmpty(struct queue *p)
{
if (p->front == NULL && p->rear == NULL)
{
return 0;
}
else
{
return 1;
}
}
int IsFull(struct queue *p)
{
if (p->num == p->size)
{
return 0;
}
else
{
return 1;
}
}
int EnterQueue(struct queue *p)
{
if (!IsFull(p))
{
printf("队列已满\n");
return 0;
}
else if (!IsEmpty(p))
{
p->rear = (struct node *)malloc(sizeof(struct node));
p->front = p->rear;
p->rear->next = NULL;
p->num++;
printf("请输入第1个节点数据：\n");
scanf("%d", &(p->rear->data));
return 0;
}
else
{
p->rear->next = (struct node *)malloc(sizeof(struct node));
p->rear->next->next = NULL;
p->rear = p->rear->next;
p->num++;
printf("请输入第%d个节点数据：\n", p->num);
scanf("%d", &(p->rear->data));
return 0;
}
}
int DeleteQueue(struct queue *p)
{
if (!IsEmpty(p))
{
printf("队列已空\n");
return 0;
}
else if (p->front == p->rear) //只有一个节点的情况
{
free(p->rear);
p->rear = NULL;
p->front = NULL;
p->num = 0; //元素数量置零
return 0;
}
else
{
struct node *temp = p->front;
p->front = p->front->next;
free(temp);
p->num--; //元素数量-1
return 0;
}
}
int front(struct node *front)
{
if (!IsEmpty)
{
printf("队列已空\n");
return 0;
}
printf("队首元素：%d\n", front->data);
}
int printQ(struct node *front) //遍历链表，打印数据
{
printf("\nfront:< ");
if (!IsEmpty)
{
printf("队列已空\n");
return 0;
}
while (front)
{
printf("%d ", front->data);
front = front->next;
}
printf("<rear\n");
}
int main()
{
int i = 0;
struct queue q = {NULL, NULL, 0, 8};
printf("请输入要入队的元素个数，最多入队%d个\n", q.size);
scanf("%d", &i);
while (i--)
{
EnterQueue(&q);
}
printQ(q.front);
front(q.front);
DeleteQueue(&q);
DeleteQueue(&q);
printQ(q.front);
return 0;
}
- 终端显示：
请输入要入队的元素个数，最多入队8个
9
请输入第1个节点数据：
111
请输入第2个节点数据：
222
请输入第3个节点数据：
333
请输入第4个节点数据：
444
请输入第5个节点数据：
555
请输入第6个节点数据：
666666
请输入第7个节点数据：
777
请输入第8个节点数据：
888
队列已满
front:< 111 222 333 444 555 666666 777 888 <rear
队首元素：111
front:< 333 444 555 666666 777 888 <rear
再见！ ??