队列queue

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

1. 单向队列

  • public boolean isFull();判断队列是否满
    • rear == maxSize - 1
  • public boolean isEmpty(); 判断队列是否为空
    • rear == front
  • public void addQueue(int n);添加数据到队列
  • public int getQueue(); 从队列中删除数据
  • public void showQueue();显示队列的所有数据
  • public int headQueue();显示队列的头数据，只是显示
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
//使用数组模拟队列，编写一个ArrayQueue类(单向)
public 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是指向队列头的前一个位置
		front = -1;
		
		//指向队列尾，指向队列尾的数据（是队列最后一个数据）
		rear = -1;
	}
    
	
	
	//判断队列是否满
	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++;
		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("队列为空，没有数据");
		}
		//front 指向的是，头数据的前一个元素
		return arr[front+1];
	}
	
}

1.1 测试单向队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public class ArrayQueueDemo {

	public static void main(String[] args) {
		//开始测试写的队列
		//新建队列，给定长度
		ArrayQueue queue = new ArrayQueue(4);
		
		//往队列中添加数据
		queue.addQueue(1);
		queue.addQueue(2);
		queue.addQueue(3);
		queue.addQueue(4);
		
		//queue.addQueue(5);队列已经满了，不能添加数据了

		
		//显示队列信息
		queue.showQueue();
		
		
		//取出第一个数据(删除数据，即出队列，先进先出)
		int front = queue.getQueue();
		System.out.println("取出的数据："+front);
		
		int head = queue.headQueue();
		System.out.println("head的数据："+head);
		
	}

}

2. 环形队列

  • front 指向队列的第一个元素 默认初始值 front = 0
  • rear 指向队列的最后一个元素的后一个位置，因为希望空出一个空间作为约定 默认初始值 rear = 0
  • public boolean isFull();判断队列是否满
    • (rear+1)%maxSize == front
  • public boolean isEmpty(); 判断队列是否为空
    • rear == front
  • public void addQueue(int n);添加数据到队列
    • rear=(rear+1)%maxSize; 后移一位
  • public int getQueue(); 从队列中删除数据
  • public void showQueue();显示队列的所有数据
  • public int headQueue();显示队列的头数据，只是显示
  • public int size();得到队列中有效数据的个数
    • (rear-front+maxSize)%maxSize
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
//循环队列queue--循环
public class CircleArrayQueue{
	
	//队列的最大容量
	private int maxSize;
	
	//front 指向队列的第一个元素  默认初始值 front = 0
	private int front;
	
	//rear 指向队列的最后一个元素的后一个位置，因为
	//希望空出一个空间作为约定 默认初始值 rear = 0
	private int rear;
	
	private int[] arr;
	
	
	
	
	//构造器
	public CircleArrayQueue(int arrMaxSize) {
		maxSize = arrMaxSize;
		arr = new int[maxSize];
	}
	
	
	
	//判断队列是否满
	public boolean isFull() {
		return (rear+1)%maxSize == front;
	}
	
	
	//判断队列是否为空
	public boolean isEmpty() {
		return rear == front;
	}
	
	
	//添加数据到队列
	public void addQueue(int num) {
		
		if(isFull()) {
			System.out.println("队列满不能添加数据！");
			return;
		}
		
		//因为rear指向的是队列的最后一个数据的后一个，所以可以直接赋值
		arr[rear]=num;
		
		//需要后移一位
		rear=(rear+1)%maxSize;
		
	}
	
	
	
	//获取队列的数据，出队列
	public int getQueue() {
		
		//判断数据是否为空
		if(isEmpty()) {
			throw new RuntimeException("队列空不能取数据！");
		}
		
		/**
		 * 1、获取第一个数据的值
		 * 2、将front后移
		 * */
		
		int result = arr[front];
		
		front = (front+1)%maxSize;
		
		return result;
	}
	
	
	
	//显示队列
	public void showQueue() {
		
		if(isEmpty()) {
			System.out.println("队列为空！");
			return;
		}
		//思路：从front开始遍历-----遍历多少个元素？
		for (int i = front; i < front+size(); i++) {
			
			System.out.printf("arr[%d]=%d\n",i%maxSize,arr[i%maxSize]);
			
		}
		
	}
	
	
	//得到队列中有效数据的个数
	public int size() {
		/**
		 * front = 1
		 * rear  = 2
		 * maxSize = 3
		 * 因为这个是循环队列，所以要使用取模
		 * 如果不是循环的话--按这个规定得到的结果result = rear -front；
		 * */
		return (rear-front+maxSize)%maxSize;
	}
	
	
	//显示头数据
	public int headQueue() {
		if(isEmpty()) {
			throw new RuntimeException("队列为空！没有head数据");
		}		
		return arr[front];
	}
	
}

2.1 测试循环队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
public class CircleArrayQueueDemo {

	public static void main(String[] args) {
		
		//测试循环队列
		System.out.println("测试数据模拟循环队列！");
		
		//创建一个环形队列
		//队列的长度为4---最多只能储存3个元素
		CircleArrayQueue queue = new CircleArrayQueue(4);
	
		
		Scanner scanner = new Scanner(System.in);
	
		boolean flag =true;
		
		while(flag) {
//			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):查看队列头的数据");
			
			
			//接收用户输入
			String key = scanner.nextLine();
			
			switch (key) {
				
				case "s":
					queue.showQueue();
					break;
					
				case "a":
					System.out.println("请输入一个数");
					int value = scanner.nextInt();
					queue.addQueue(value);
					break;
				case "g":
					try {
						int result = queue.getQueue();
						System.out.printf("取出的数据是：%d\n",result);
					} catch (Exception e) {
						// TODO: handle exception
						System.out.println(e.getStackTrace());
					}
					break;
				case "e":
					scanner.close();
					flag=false;
					break;
					
				default:
					break;
					
			}
		
				
		}
		
		System.out.println("测试程序退出！");
		
	}

}