环形队列day02

程序员文章站 2022-06-04 09:13:04

...

队列

队列是一个有序列表，可以用数组或者链表来实现
遵循**先入先出（FIFO）**原则。

数组模拟队列

环形队列day02
maxSize表示队列的最大容量
front队头
rear队尾

存数据到队列（addQueue）步骤：

将尾指针后移：rear+1。front==rear【队列空】
若尾指针rear小于队列的最大下标maxSize-1，则将数据存入rear所指的数组元素中，否则无法存入数据。rear=maxSize-1【队列满】

package com.xhl.Queue;

public class ArrayQueue {
	private int maxSize;//队列容量
	private int front;//队头
	private int rear;//队尾
	private int[] arr;//存放数据，模拟队列
	
	//构造方法
	public ArrayQueue(int maxSize) {
		super();
		this.maxSize = maxSize;
		arr = new int[maxSize];
		front = -1 ;
		rear = -1;
	}
	
	
	//判满
	public boolean isFull() {
		return rear==maxSize-1;
	}
	
	//判空
	public boolean isEmpty() {
		return front == rear;
	}
	
	//添加数据到队列
	public void addQueue(int n) {
		if(isFull()) {
			System.out.println("队列已满，无法插入数据");
			return;
		}
		arr[++rear]=n;
	}
	
	//数据出队列
	public int getQueue() {
		if(isEmpty()) {
			throw new RuntimeException("队列为空，不能取数据");
		}
		return arr[++front];
	}
	
	//显示所有数据
	public void showQueue() {
		if(isEmpty()) {
			throw new RuntimeException("队列为空，不能取数据");
		}
		for(int i=front+1 ; i<= rear;i++) {
			System.out.printf("arr[%d]=%d\n",i,arr[i]);
		}
	}
	
	//显示队头数据	
		public int headQueue() {
			if(isEmpty()) {
				throw new RuntimeException("队列为空，不能取数据");
			}
			return arr[front+1];
		}
}

package com.xhl.Queue;

import java.util.Scanner;

public class ArrayQueueDemo {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		//测试
		ArrayQueue queue = new ArrayQueue(5);
		char key=' ';
		Scanner scanner = new Scanner(System.in);
		boolean loop = true;
		
		while(loop) {
			//菜单
			System.out.println("s(show)：显示队列");
			System.out.println("e(exit)：退出程序");
			System.out.println("a(add)：添加数据");
			System.out.println("g(get)：取出数据");
			System.out.println("h(head)：显示队头");

			key = scanner.next().charAt(0);//接收一个字符
			switch(key) {
			case's':
				queue.showQueue();
				break;
			case'a':
				System.out.println("请输入需要插入的数据：");
				int value = scanner.nextInt();
				queue.addQueue(value);
				break;
			case'g':
				int res = queue.getQueue();
				System.out.println("取出的数据是："+res);
				break;
			case'h':
				int head = queue.headQueue();
				System.out.println("队头的数据是："+head);
				break;	
			case'e':
				scanner.close();
				loop = false;
				break;
			default:
				break;
			}
			
		}
		
		System.out.println("程序退出！！！！");
	}

}

运行结果：
环形队列day02
问题分析及优化：
数组使用一次就不能再用，造成资源浪费，可以使用环形队列

数组模拟环形队列

front指向队列第一个元素，即arr[front]为第一个元素
rear指向队列最后一个元素后一行的位置，即arr[rear-1]为最后一个元素
队空：rearfront
队满：（rear+1）%maxSizefront

环形队列预留一个空数据位（我复习的时候没细看文字，就看了一下书上的图，图上没有显示空的数据位T_T，我一直以为我的理解有问题，咋到最后一个的时候会判满，我还翻自己之前写的C语言版本，发现也是这样，沉思了好久，好气哦，浪费了好多时间，
必须要吐槽一下b(╬￣皿￣)）

package com.xhl.CircleArrayQueue;

public class CircleArray {
	private int maxSize;//队列容量
	private int front;//队头
	private int rear;//队尾
	private int[] arr;//存放数据，模拟队列
	
	//构造方法
	public CircleArray(int maxSize) {
		super();
		this.maxSize = maxSize;
		arr = new int[maxSize];
		front = 0 ;
		rear = 0;
	}
	
	
	//判满
	public boolean isFull() {
		return (rear+1)%maxSize==front;
	}
	
	//判空
	public boolean isEmpty() {
		return front == rear;
	}
	
	//添加数据到队列
	public void addQueue(int n) {
		if(isFull()) {
			System.out.println("队列已满，无法插入数据");
			return;
		}
		arr[rear]=n;
		rear = (rear+1)%maxSize;
	}
	
	//数据出队列
	public int getQueue() {
		if(isEmpty()) {
			throw new RuntimeException("队列为空，不能取数据");
		}
		int value = arr[front];
		front = (front+1)%maxSize;
		return value;
	}
	
	//显示所有数据
	public void showQueue() {
		if(isEmpty()) {
			throw new RuntimeException("队列为空，不能取数据");
		}
		for(int i=front ; i%maxSize != rear ;i++) {
			System.out.printf("arr[%d]=%d\n",i%maxSize,arr[i%maxSize]);
		}
	}
	
	//显示队头数据	
		public int headQueue() {
			if(isEmpty()) {
				throw new RuntimeException("队列为空，不能取数据");
			}
			return arr[front];
		}
}

package com.xhl.CircleArrayQueue;

import java.util.Scanner;

public class CircleArrayQueueDemo {


	public static void main(String[] args) {
		// TODO Auto-generated method stub
		//测试
		CircleArray queue = new CircleArray(3);
		char key=' ';
		Scanner scanner = new Scanner(System.in);
		boolean loop = true;
		
		while(loop) {
			//菜单
			System.out.println("s(show)：显示队列");
			System.out.println("e(exit)：退出程序");
			System.out.println("a(add)：添加数据");
			System.out.println("g(get)：取出数据");
			System.out.println("h(head)：显示队头");

			key = scanner.next().charAt(0);//接收一个字符
			switch(key) {
			case's':
				queue.showQueue();
				break;
			case'a':
				System.out.println("请输入需要插入的数据：");
				int value = scanner.nextInt();
				queue.addQueue(value);
				break;
			case'g':
				int res = queue.getQueue();
				System.out.println("取出的数据是："+res);
				break;
			case'h':
				int head = queue.headQueue();
				System.out.println("队头的数据是："+head);
				break;	
			case'e':
				scanner.close();
				loop = false;
				break;
			default:
				break;
			}
			
		}
		
		System.out.println("程序退出！！！！");
	}

}

运行结果：
环形队列day02
c语言版本：
（发现c语言好久没用都快忘记了）

#include <stdio.h>
#include <stdlib.h>
#define MAXQSIZE 4

typedef int ElemType;//设置ElemType类型 
typedef struct
{
    ElemType  *data;
    int front,rear;
}SqQueue;

//初始化函数
void InitQueue(SqQueue *Q)
{
	Q->data = (ElemType*) malloc (MAXQSIZE*sizeof(ElemType));
    Q->front=Q->rear=0;
}

//入队函数
void EnQueue (SqQueue *Q, ElemType e)
{ 
	if ((Q->rear+1)%MAXQSIZE == Q->front) 
	{
		printf("队已满，无法入队\n");
		return ; 
	}    
	Q->data[Q->rear]=e;
	Q->rear=(Q->rear+1)%MAXQSIZE;
}


//出队函数
void DeQueue(SqQueue *Q, ElemType *e)
{ 
	if (Q->rear == Q->front) 
	{
		printf("队已空，无法出队\n");
		return ; 
	}    	
	*e=Q->data[Q->front];
	Q->front=(Q->front+1)%MAXQSIZE;
}

void headQueue(SqQueue *Q,ElemType *e){
	if (Q->rear == Q->front) 
	{
		printf("队已空，无法出队\n");
		return ; 
	}  
	*e=Q->data[Q->front];
}

void showQueue(SqQueue *Q){
	for(int i=Q->front ; i%MAXQSIZE != Q->rear ;i++){
		printf("data[%d]=%d\n",i,Q->data[i]);
	}
}

int main()
{
	SqQueue Q;
	InitQueue(&Q);
	bool loop=true;
	char key;
	
	//菜单
	printf("s(show)：显示队列\n");
	printf("e(exit)：退出程序\n");
	printf("a(add)：添加数据\n");
	printf("g(get)：取出数据\n");
	printf("h(head)：显示队头\n");	
	
	while(loop) {
			scanf("%c",&key);//接收一个字符
			switch(key) {
			case's':
				showQueue(&Q);
				break;
			case'a':
				printf("请输入需要插入的数据：");
				ElemType value;
				scanf("%d",&value);
				EnQueue (&Q, value);
				break;
			case'g':
				ElemType res;
				DeQueue(&Q,&res);
				printf("取出的数据是：%d",res);
				break;
			case'h':
				ElemType head;
				headQueue(&Q,&head);
				printf("队头的数据是：%d",head);
				break;	
			case'e':
				loop = false;
				break;
			default:
				break;
			}
			
		}
		
		printf("程序退出！！！！");	
}

运行结果：
环形队列day02

相关标签：数据结构复习数据结构

上一篇：官方揭秘华为HMS路在何方：无处不在的“小叮当”

下一篇：数据结构：堆排序

环形队列day02

队列

数组模拟队列

存数据到队列（addQueue）步骤：

数组模拟环形队列

echarts白色实心环形图（空心饼图）的编写

使用golang编写一个并发工作队列

vue环形进度条组件实例应用

JS异步函数队列功能实例分析

使用 PHP 消息队列实现 Android 与 Web 通信

RabbitMQ消息队列入门（一）——RabbitMQ消息队列的安装(Windows环境下)

栈与队列（含单调栈与单调队列）

PHP使用Redis的List(列表)命令实现消息队列

C#内置队列类Queue用法实例

Mysql,Oracle使用rollup函数完成队列统计