温馨提示×

温馨提示×

您好,登录后才能下订单哦!

密码登录×
登录注册×
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》

java如何实现队列queue数据结构

发布时间:2022-02-08 09:33:46 来源:亿速云 阅读:121 作者:小新 栏目:开发技术

这篇文章主要介绍java如何实现队列queue数据结构,文中介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们一定要看完!

    概念

    队列是一种非原始(特殊)的线性表,是一种先进先出(FIFO)的数据结构。它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作。

    FIFO:first input first output,即先添加的元素,先移除,最后添加的元素,最后移除。

    工作方式类似于商场排队结账情形:

    java如何实现队列queue数据结构

    数组模拟队列图示:

    java如何实现队列queue数据结构

    队列中两个主要操作

    插入值操作:insert ——》 enqueue(入队) ——》参数是要插入的数据data

    删除值操作:remove ——》 dequeue (出队)——》 无参

    队列遵循以下条件:

    如果 FRONT = 0,那么队列就是空的。

    如果 REAR = size of the queue,那么队列就是满了。

    如果 FRONT = REAR,那么队列中至少有一个元素。

    如果你想知道队列中元素的总数,那么使用这个公式计算(REAR - FRONT)+1。

    队列的数组实现

    我们可以通过数组、堆栈和链表来实现队列。其中数组是实现队列的最简单方法。

    创建一个大小为 n 的数组。将 FRONT 和 REAR 的值初始化为 -1,该值表示该数组当前为空。

    编写一个ArrayQueue类如下:

    class ArrayQueue {
    	private int maxSize; // 数组的最大容量
    	private int front; // 队列头
    	private int rear; // 队列尾
    	private int[] arr; // 存放数据, 模拟队列
     
    	// 创建构造器,初始化
    	public ArrayQueue(int arrMaxSize) {
    		maxSize = arrMaxSize;
    		arr = new int[maxSize];
    		front = -1; // front 是指向队列头的前一个位置
    		rear = -1;  // rear  是指向队列尾的数据(最后一个数据)
    	}
     
    	// 判断队列是否已满
    	public boolean isFull() {
    		return rear == maxSize - 1;
    	}
     
    	// 判断队列是否为空
    	public boolean isEmpty() {
    		return rear == front;
    	}
     
    	// 添加数据
    	public void addQueue(int n) {
    		if (isFull()) {
    			System.out.println("队列已满,不能再添加数据了!");
    			return;
    		}
    		rear++; // 让rear 后移
    		arr[rear] = n;
    	}
     
    	// 获取数据
    	public int getQueue() {
    		if (isEmpty()) {
    			// 通过抛出异常
    			throw new RuntimeException("队列为空,无数据可取!");
    		}
    		front++; // front后移
    		return arr[front];
     
    	}
     
    	// 显示队列的所有数据
    	public void showQueue() {
            if (isEmpty()) {
    			System.out.println("队列空的,没有数据~~");
    			return;
    		}
    		for (int i = 0; i < arr.length; i++) {
    			System.out.printf("arr[%d]=%d\n", i, arr[i]);
    		}
    	}
     
    	// 显示队列的头部指向的下一个
    	public int headQueue() {
    		if (isEmpty()) {
    			throw new RuntimeException("队列为空,没有数据~~");
    		}
    		return arr[front + 1];
    	}
    }

    编写测试方法:

    		//创建一个队列
    		ArrayQueue queue = new ArrayQueue(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': //依次取出数据
    				try {
    					int res = queue.getQueue();
    					System.out.printf("取出的数据是%d\n", res);
    				} catch (Exception e) {
    					// TODO: handle exception
    					System.out.println(e.getMessage());
    				}
    				break;
    			case 'h': //查看队列头指向
    				try {
    					int res = queue.headQueue();
    					System.out.printf("队列头的数据是%d\n", res);
    				} catch (Exception e) {
    					// TODO: handle exception
    					System.out.println(e.getMessage());
    				}
    				break;
    			case 'e': //退出程序
    				scanner.close();
    				loop = false;
    				break;
    			default:
    				break;
    			}
    		}
    		
    		System.out.println("程序退出~~");
    	}

    以上是“java如何实现队列queue数据结构”这篇文章的所有内容,感谢各位的阅读!希望分享的内容对大家有帮助,更多相关知识,欢迎关注亿速云行业资讯频道!

    向AI问一下细节

    免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

    AI