C语言队列的基本实现

• • 1.队列的简介
  • 2.队列的简单实现
  • 3.循环队列说明
  • 4.循环队列实现

队列（Queue），简称队，它也是一种运算受限的特殊的线性表，它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列的数据元素又称为队列元素。在队列中插入一个队列元素称为入队，从队列中删除一个队列元素称为出队。因为队列只允许在一端插入，在另一端删除，所以只有最早进入队列的元素才能最先从队列中删除，故队列又称为先进先出（FIFO）线性表。
对应我们日常生活中的情形，比如，在食堂的单窗口买饭，一个食堂阿姨每次只能给一位同学打饭，那么我们就需要排队买饭，先到的同学排在队伍的前面，后来的同学排在后面。前面的同学先买到饭然后出队离开；后面来的同学原则上只能排到队伍的后面（手动狗头）。这就是先来的先请求得到服务。再比如我们有一台网络共享打印机，网络中的任何一台机器都可以向它发出打印请求。但它每次只能服务一个，该如何处理这些请求呢？这个时候控制打印机的程序就会把请求们加入到一个队列，只要队列中有内容，打印机就会从不断地从队列头部取出请求执行打印。计算机的处理器也是一个共享的资源，很多程序或者说进程需要处理器的时间片来执行，那么这些进程也会被放入一个队列。

对于栈，插入和删除只能从一端进行；对于队列，插入和删除操作必须从不同端进行。接下来我们用两种方式来实现相关操作。

首先创建一个包含整型元素的数组来存储队列。下面是一种极其简单的实现方式。代码：

#include
#define MAXSIZE 10
int A[MAXSIZE];//定义一个全局整型数组存放队元素
int front = -1;
int rear = -1; //队空时将索引置为-1；
//入队操作
 void Enqueue(int x){
 	//队满则不支持入队
	 if(rear ==MAXSIZE-1){
	 	printf("Error:Queue is Full ");
	 		return ;
		 }
		 A[++rear] = x;
	 
 }
 //出队操作
 void Dequeue(){
 	if((rear ==-1)&& front ==-1){
 		printf("Error:Queue is Empty");
 		return ;
	 }
	 else if(rear == front&&(rear!=-1)){//队列只有一个元素 
	 	rear = -1;
	 	front = -1;
	 	
	 }
	 else{
	 	front  = front+1;
	 } 	 
 } 
 // 返回队尾值
 int Rear(){
 	return A[rear];
 } 
 void Print(){
 	int i;
 	printf("queue:  ");
 	for(i=front+1;i<=rear;i++){
 		printf("%d  ",A[i]);
	 }
 	printf("n");
 }
 int main(){
 	Enqueue(1);
 	Enqueue(2);
 	Enqueue(3);
 	Print();
 	Dequeue();
 	Dequeue();
 	printf("now the queue is: ");
 	Print();
 }

运行结果：

很明显，以上的方法，我们只是利用简单的数组进行了模拟。它存在着很多的不足。比如，当我们删去队列中的元素时，我们没法使用他们留下来的空位，每一次Dequeue空下来的front位都会被闲置。这样对空间造成了很大的浪费。于是，我们设计循环数组。通过取余的操作，使front和rear指针发生改变。除此之外，我们说队列也是一种线性表，对于线性表，我们使用结构体来定义才是一种更加理想的方式。

结构体定义：

typedef struct
{
	QElemType *base;//初始化动态分配的指定长度的空间
	int front;//头指针，若队列不空，指向队列头元素
	int rear;//尾指针，若队列不空，指向队列尾元素的下一个位置
}SqQueue;

循环队列初始化：

bool InitQueue(SqQueue *Q)
{
	Q->base=(QElemType*)malloc(maxQueueSize*sizeof(QElemType));
	if (!Q->base)
	{
		return false;
	}
	Q->front=0;
	Q->rear=0;
	return true;
}

入队函数：

bool EnQueue(SqQueue *Q,QElemType e)
{
	if ((Q->rear+1)%maxQueueSize==Q->front)//队列满
	{
		return false;
	}
	Q->base[Q->rear]=e;
	Q->rear=(Q->rear+1)%maxQueueSize;
	printf("%d successfully inn",e);
	return true;
}

出队函数：

bool DeQueue(SqQueue *Q,QElemType *e)
{
	if (Q->front==Q->rear)//队列空
	{
		return false;
	}
	*e=Q->base[Q->front];
	Q->front=(Q->front+1)%maxQueueSize;
	printf("%d successfully out！n",*e);
	return true;
}

打印函数和主函数：

void printfQueue(SqQueue Q)
{
	printf("Now the queue is:n");
	while (Q.front!=Q.rear)
	{
		if (Q.front==maxQueueSize &&(Q.rear+1)%maxQueueSize!=Q.front)
		{
			Q.front=0;
		}
		printf("%d ",Q.base[Q.front]);
		Q.front++;
	}
	printf("n");
}

int main()
{
	SqQueue *Q=(SqQueue*)malloc(sizeof(SqQueue));
	InitQueue(Q);

	EnQueue(Q,1);
	EnQueue(Q,3);
	EnQueue(Q,1);
	EnQueue(Q,4);
	printfQueue(*Q);
	QElemType *e=(QElemType*)malloc(sizeof(QElemType));
	DeQueue(Q,e);
	DeQueue(Q,e);
	EnQueue(Q,9);
	EnQueue(Q,9);
	printfQueue(*Q);

	
	return 0;
}

执行结果：