队列
队列是一个有序列表，可以用数组或链表来实现
遵循先进先出的原则
数组模拟队列 front指向队列头的前一个位置，rear指向队列尾的，front会随着数据输出而改变，rear指向 初始化时rear和front都是-1 当取出数据front上移而rear不动 当front == rear(-1) 队列为空
当rear == maxSize - 1 队列满
普通队列代码
public class Queue {
public static void main(String
[] args
) {
ArrayQueue arrayQueue
= new ArrayQueue(3);
arrayQueue
.add(5);
arrayQueue
.add(4);
arrayQueue
.add(3);
System
.out
.println(arrayQueue
.pop());
System
.out
.println(arrayQueue
.pop());
System
.out
.println(arrayQueue
.pop());
}
}
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;
rear
= -1;
}
public boolean ifFull(){
return rear
== maxSize
- 1;
}
public boolean ifEmpty(){
return rear
== front
;
}
public void add(int num
){
if(ifFull()){
throw new RuntimeException("队列满");
}
arr
[++rear
] = num
;
}
public int pop(){
if(ifEmpty()){
throw new RuntimeException("队列为空");
}
return arr
[++front
];
}
public void showQueue(){
if(ifEmpty()){
throw new RuntimeException("队列为空");
}
for(int i
= front
+1; i
<= rear
; i
++){
System
.out
.println(arr
[i
]);
}
}
public int head(){
if(ifEmpty()){
throw new RuntimeException("队列为空");
}
return arr
[front
+1];
}
}
环形队列
front指向队列中第一个元素，也就是说arr[front]就是队列的第一个元素，front的初始值=0rear指向队列的最后一个元素的后一个位置，rear的初始值=0当(rear+1) % maxSize = front，队列满rear = front 队列空队列中有效数据的个数：(rear+maxSize-front)%maxSize留了一个空间不放数据
代码
public class CircleArrayQueue {
public static void main(String
[] args
) {
CircleArray circleArray
= new CircleArray(4);
circleArray
.add(5);
circleArray
.add(4);
circleArray
.add(3);
circleArray
.showQueue();
}
}
class CircleArray {
private int maxSize
;
private int front
;
private int rear
;
private int[] arr
;
public CircleArray(int arrMaxSize
) {
maxSize
= arrMaxSize
;
arr
= new int[maxSize
];
front
= 0;
rear
= 0;
}
public boolean ifFull() {
return (rear
+ 1) % maxSize
== front
;
}
public boolean ifEmpty() {
return rear
== front
;
}
public void add(int num
) {
if (ifFull()) {
throw new RuntimeException("队列满");
}
arr
[rear
] = num
;
rear
= (rear
+1) % maxSize
;
}
public int pop() {
if (ifEmpty()) {
throw new RuntimeException("队列为空");
}
int value
= arr
[front
];
front
= (front
+1) % maxSize
;
return value
;
}
public void showQueue() {
if (ifEmpty()) {
throw new RuntimeException("队列为空");
}
for (int i
= front
; i
< front
+ size(); i
++) {
System
.out
.println(arr
[i
%maxSize
]);
}
}
public int head() {
if (ifEmpty()) {
throw new RuntimeException("队列为空");
}
return arr
[front
];
}
public int size(){
return (rear
+ maxSize
- front
) % maxSize
;
}
}
