顺序循环队列的基本操作(C语言实现)

一、队列和循环队列基本概念

队列:

顺序循环队列的基本操作(C语言实现)

  • 和栈相反,队列是一种先进先出(FIFO)的线性表。只允许在一端插入,在另一端删除。
  • 允许插入的叫"队尾"(rear),允许删除的叫"队头"(front)。

  • 入队操作:L->rear++;   L->data[L->rear]=x;(需要入队的元素)

  • 出队操作:L->front++;  x=L->data[L->front];

  • 求队长:队长=(L->rear)-(L->front);

  • 队空:L->rear==L->front==-1;

  • 队满:队长=max

  • 使用场景:一切具备先来后到的任务场景

 

循环队列:

顺序循环队列的基本操作(C语言实现)

 

  •  和队列类似,只不过队头和队尾相连,解决了队列的假溢出现象(队尾指针达到申请空间的最大时,系统会认定空间满,但是队头指针如果不为-1则就是假溢出)。
  • 入队:L->rear==(L->rear+1)%max;
  • 出队:L->front==(L->front+1)%max;
  • 队满:由图可知 队满和队空条件重复,所以为了避免这一情况现如今有两种方法:1.少用一个元素空间,也就是说front指针在定义时指向0的位置,这样才能使front和rear之间空出一个元素空间。2.这个方法比较容易理解,就是定义一个Num值来记录元素个数,num==0时则队空,num==max时则队满。

具体操作:(L->rear+1)%max==front;  num==max;

  • 队空:L->rear==L->front;
  • 队长:分两种情况:1.头指针在尾指针之后:按普通队列求法。2.头指针在尾指针之前:队长=L->rear+(max-(L->front));

二、代码实操

 图示:

 

顺序循环队列的基本操作(C语言实现)

 具体代码:

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define ture 1
#define false 0
#define max 5
typedef struct {
	int data[max];
	int front,rear;
}cteam,*team;
static int num=0;  //全局变量 num  
//初始队列
int Initteam(team &L){
	L=(cteam *)malloc(sizeof(cteam));
	if(L==NULL){
		printf("申请空间失败!");
		return false;
	}
	L->front=L->rear=-1;
	return true;
}
//入队
int pushteam(team &L,int x){
	if(num==max){
		printf("队满");
		return false;
	}else{
		L->rear=(L->rear+1)%max;  //rear始终在0-10中循环
		L->data[L->rear]=x; 
		num++;
		return true;
	}
} 
//出队
int popteam(team &L,int &x){
	if(num==0){
		printf("队空!");
		return false;
	}else{
		L->front=(L->front+1)%max;  //front始终在0-10中循环
		x=L->data[L->front];
		num--;
		printf("\n%d出队\n",x);
		return x;
	} 
}
//遍历队
void printteam(team L){
	int p;
	p=L->front+1;
	if(L->front<L->rear){
		while(p<=L->rear){
		printf("%d ",L->data[p]);
		p++;}
	}else{
		while((p-1)!=L->rear){
			printf("%d ",L->data[p]);
			p=(p+1)%max;
		}
	}
  }
//求队长 
 int teamlength(team L){
 	int p;
 	if(L->front<L->rear){
 		p=(L->rear)-(L->front);      //当队列正常时 
	 }else{
	 	p=L->rear+(max-(L->front));  //当队列开始循环时 
	 }
	printf("\n队长为:%d",p);
 }
 //取队头元素
  int gettop(team L){
  	if(L->front==L->rear){
  		printf("队空!");
  		return false;
	  }else{
	  	int t=L->data[L->front+1];
	  	return t;
	  }
  } 
  
  
  /*     
  		pushteam:入队函数	popteam:出队函数 
  		printteam:遍历函数	gettop:取队头函数 
  		Initteam:初始化函数	teamlength:求队长函数 
  */
  
  
int main(){
	team s;
	int w;
	Initteam(s);
	//1-3进队列 
	pushteam(s,1);      
	pushteam(s,2);
	pushteam(s,3);
	printf("------1-3进队列后----------\n");
	printf("此时队列为:");
	printteam(s);
   	popteam(s,w);
	popteam(s,w);
	printf("此时队列为:");
	printteam(s);
	printf("\n------4-6进队列后----------\n");
	pushteam(s,4);
	pushteam(s,5);
	pushteam(s,6);
	printf("此时队列为:");
	printteam(s);
	teamlength(s);
	int T=gettop(s);
	printf("\n队头元素为:%d",T);
}

实现结果:

顺序循环队列的基本操作(C语言实现)

 

上一篇:环形队列


下一篇:如何使用 vercel + hexo 搭建博客