C语言数据结构与算法--简单实现队列的入队和出队

 （一）队列的基本概念

        和栈相反，队列(Queue)是一种先进先出（First In First Out）的线性表。只 允许在表的一端进行插入，而在另一端删除元素，如日常生活中的排队现象。队列中 允许插入的一端叫队尾(rear)，允许删除的一端称队头(front)。假设队列为 q=(a1, a2, …, an)，则 a1 为队头元素， an 为队尾元素。队列中出队的顺序和进队顺序一 致。队列的基本操作与栈类似，包括：初始化、清空、销毁、求长度、得到对头元 素、插入、删除。

（二）队列的表示形式

队列的表示形式有两种：队列的链式表示、队列的顺序表示。 

1．队列的链式表示

        用链表来表示的队列，简称链队列。在这种表示形式中，需要两个分别指向队头（front 或 head）和队尾(rearh 或 end)的指针。与线性 表的单链表类似，需要设置头结点。队列为空的 条件是队头指针和队尾指针均指向头结点。实际 上链队列的操作为单链表的插入和删除操作的特 殊情况。

        链队列插入与删除元素时的指针变化情况如 下图。

2．队列的顺序表示

        队列的顺序表示用一组地址连续的存储单元依次存放从队头（front）到队尾 （rear）的元素。此外，还需要设置两个指针分别指向队头元素和队尾元素。初始化 时 Q. front = Q.rear = 0，插入元素时尾指针加 1，删除元素时，头指针增加 1。

        为保证插入新元素时不会使数组越界，并充分利用队头删除元素后的空间，可 设计一个环行空间，构成循环队列。但是，凭 Q.front = Q.rear 无法判断队列是满 还是空。处理方法有两种：一是设标志，二是少用一个元素空间。特点是无法用动态 分配的一维数组实现循环队列。

（三）循环队列入队、出队实现思路

1．循环队列入队算法

        入队算法过程为：判断队列是否已满？如果已满则退出；否则，队尾指针加 1， 并在队尾插入新的元素。

2．循环队列出队算法

        出队算法过程为：判断队列是否为空？如果为空则退出；否则，队头指针加 1，并删除队头元素。

（四）算法实现

队列的顺序表示

#define _CRT_SECURE_NO_WARNINGS  
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 12  //设置循环队列的最大存储元素个数typedef struct {int* base;int front;int rear;
} queue;//队列初始化
void InitQueue(queue* Q)
{//为队列分配存储空间Q->base = (int*)malloc(sizeof(int) * MAX_SIZE);Q->front = Q->rear = 0;
}
//入队操作
void InputQueue(queue* Q, int x)
{//判断循环队列是否已满if (((Q->rear + 1) % MAX_SIZE) == Q->front)return;//队列未满，将数据入队Q->base[Q->rear] = x;Q->rear = (Q->rear + 1) % MAX_SIZE;
}
//出队操作
void OutputQueue(queue* Q)
{if (Q->front == Q->rear)return;//如果非空，实现可循环出队Q->front = (Q->front + 1) % MAX_SIZE;
}void ShowQueue(queue* Q)
{//遍历循环队列中的元素，并将数据打印for (int i = Q->front; i != Q->rear;){printf("%d ", Q->base[i]);i = (i + 1) % MAX_SIZE;}printf("\n");
}void main() {queue Q;InitQueue(&Q);int n;printf("请输入入队个数n:\n");scanf("%d", &n);for (int i = 0; i < n; i++) {int data;printf("请输入第%d个入队元素：\n",i+1);scanf("%d", &data);InputQueue(&Q, data);}printf("入队:\n");ShowQueue(&Q);OutputQueue(&Q);printf("出队:\n");ShowQueue(&Q);}

运行结果：

          至于队列的链式表示和环形表示大家可以自己做做，环形表示思路也在上面，链式表示大家可以仿照我之前写的线性表的链式表示和栈的链式表示。

最后。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。

听说点赞、收藏加关注的人都能长命千岁，万事如意。。。。。。。。。。。。。。。。。。。。