数据结构与算法之队列

队列

1. 队列介绍
   案例：银行排队
   1> 队列是一个有序列表，可以使用数组或是链表来实现。
   2>遵循先入先出的原则。即：现存入队列的数据，要先取出。
   
2. 数组模拟队列
   1> 队列本身是有序列表，若使用数组的结构来存储队列的数据，则队列数组的声明如下，其中maxSize是该队列的最大容量。
   2> 因为队列的输入，输出分别从前后端来处理，因此需要两个变量front及rear分别记录队列的前后端的下标，front会随着数据的输出而改变，而rear则是随着输入而改变。（rear是队列最后【含】，front是队列最前元素【不含】）
3. 思路分析
   当我们将数据存入队列时称为”addQueue”， addQueue的处理需要两步
   1> 将尾指针往后移：rear+1，当frontrear【空】
   2> 若尾针rear小于队列的最大下表maxSize-1，则将数据存入rear所指的数组元素中，否则无法存入数据。rearmaxSize-1【队列满】
4. 代码实现

5.	package com.queue;
6.	
7.	import java.util.Scanner;
8.	
9.	public class ArrayQueueDemo {
10.	
11.		public static void main(String[] args) {
12.			// TODO 自动生成的方法存根
13.	        //测试一把
14.			//创建一个队列
15.			ArrayQueue queue=new ArrayQueue(3);
16.			char key =' ';//接受用户输入
17.			Scanner scanner = new Scanner(System.in);//扫描器
18.			boolean loop = true;
19.			while(loop) {
20.			//输出一个菜单
21.			System.out.println("s(show):显示队列");
22.			System.out.println("e(exit):退出程序");
23.			System.out.println("a(add):添加数据到队列");
24.			System.out.println("g(get):从队列取出数据");
25.			System.out.println("h(head):查看队列头的数据");
26.			key = scanner.next().charAt(0);//接受一个字符
27.			switch (key) {
28.			case 's':
29.				queue.showQueue();
30.				break;
31.			case 'a':
32.				System.out.println("输出一个数");
33.				int value = scanner.nextInt();
34.				queue.addQueue(value);
35.				break;
36.			case 'g'://取数据
37.				try {
38.					int res = queue.getQueue();
39.					System.out.printf("取出的数据是%d\n",res);
40.				} catch (Exception e) {
41.					// TODO: handle exception
42.					System.out.println(e.getMessage());
43.				}
44.				break;
45.			case 'h'://查看队列头数据
46.				try {
47.					int res = queue.headQueue();
48.					System.out.printf("队列头的数据是%d\n",res);
49.				} catch (Exception e) {
50.					// TODO: handle exception
51.					System.out.println(e.getMessage());
52.				}
53.				break;
54.			case 'e'://退出
55.				scanner.close();
56.				loop = false;
57.				break;
58.			default:
59.				break;
60.			}
61.			}
62.			 System.out.println("程序退出");
63.		}
64.	}
65.	//使用数组模拟队列，编写一个ArrayQueue类
66.	class ArrayQueue{
67.		private int maxSize;//表示数组的最大容量
68.		private int front;//队列头
69.		private int rear;//队列尾
70.		private int[] arr;//该数组用于存放数据，模拟队列
71.		
72.		//创建队列的构造器
73.		public ArrayQueue(int arrMaxSize) {
74.			maxSize = arrMaxSize;
75.			arr =new int [maxSize];
76.			front = -1;//指向队列头部，分析出front是指向队列头的前一个位置
77.			rear =-1;//指向队列的尾部，包含队列尾
78.		}
79.		//判断队列是否满
80.		public boolean isFull() {
81.			return rear == maxSize - 1;
82.		}
83.		//判断队列是否为空
84.		public boolean isEmpty() {
85.			return rear ==front;
86.		}
87.		//添加数据到队列
88.		public void addQueue(int n) {
89.			//判断队列是否满
90.			if(isFull()) {
91.				System.out.println("队列满，不能加入");
92.				return;
93.			}
94.			rear++;//让rear后移
95.			arr[rear] = n;
96.		}
97.		//获取队列数据，出队列
98.		public int getQueue() {
99.			//判断是否为空
100.			if(isEmpty()) {
101.				//通过异常处理
102.				throw new RuntimeException("队列空，不能取");
103.			}
104.			front++;//front后移
105.			return arr[front];
106.		}
107.		//显示所有队列的数据
108.		public void showQueue() {
109.			//遍历
110.			if(isEmpty()) {
111.				System.out.println("队列空的，没有数据");
112.				return;
113.			}
114.			for (int i = 0;i<arr.length;i++) {
115.				System.out.printf("arr[%d]=%d\n",i,arr[i]);
116.			}
117.		}
118.		//显示队列的头数据，注意不是取数据
119.		public int headQueue() {
120.			//判断
121.			if(isEmpty()) {
122.				throw new RuntimeException("队列空的，没有数据");
123.				
124.			}
125.			return arr[front + 1];
126.		}
127.	}