队列
队列是一个有序列表，它遵循先进先出的原则。 队列有两种实现方式：数组和链表
数组实现
因为队列是从队尾添加元素，从队首进行删除元素，因此需要两个变量来记录,一个front记录队首位置，一个rear记录队尾的后一个位置，此时需要让数组预留一个位置（为了有效区分队列空与队列满的条件），length保存是数组长度。 例如： 假设数组的长度为4，即 length = 4； front = 0； rear = 0； 然后向队列中添加元素1,2,3,4。
如果不预留一个位置 a. 第一种情况队首没有删除元素，队列已满时 判断队列已经满的条件 rear == front 判断队列为空的条件 rear == front 队列有效个数 (rear + length)-front b. 队首删除元素，队列已满时 队列将数组下标为0的元素删除，向队尾添加一个元素 判断队列已经满的条件 rear == front 判断队列为空的条件 rear == front 队列有效个数 (rear + length)-front 队列满的条件和队列空的条件一样，就无法区分队列空和满预留一个位置，队列实际长度是length-1 a. 第一种情况队首没有删除元素，队列已满时 判断队列已经满的条件 （rear+1)% length == front 判断队列为空的条件 rear == front 队列有效个数 rear - front b. 队首删除元素，队列已满时。 判断队列已经满的条件 rear+1 == front 判断队列已经空的条件 rear == front 队列有效个数 (rear + length)-front 预留一个位置可以有效区分队列已满和队列为空的情况
队列变量
length 数组的长度 front 指向队首 rear 指向队尾 array 存储队列的数组
队列方法：
offer(); 添加一个元素到队列并返回true poll(); 移除队列第一个元素并返回 element(); 返回队列第一个元素 peek(); 返回队列第一个元素
队列实现：
package datastructure
;
public class ArrayQueue {
private Integer front
= 0;
private Integer rear
= 0;
private Integer length
;
private Integer
[] array
;
public ArrayQueue(Integer length
) {
this.length
= length
;
array
= new Integer[length
];
}
public boolean isFull() {
return ((rear
+ 1) % length
) == front
;
}
public boolean isEmpty() {
return rear
== front
;
}
public boolean offer(Integer num
) {
if(isFull()){
return false;
}
array
[rear
] = num
;
rear
= (rear
+ 1) % length
;
return true;
}
public Integer
poll() {
if(isEmpty()) {
throw new RuntimeException("队列为空");
}
int temp
= array
[front
];
front
= (front
+ 1) % length
;
return temp
;
}
public Integer
element() {
if(isEmpty()) {
throw new RuntimeException("队列为空");
}
return array
[front
];
}
public Integer
peek() {
if(isEmpty()){
return null
;
}
return array
[front
];
}
@Override
public String
toString() {
if(isEmpty()) {
return null
;
}
StringBuilder sb
= new StringBuilder();
sb
.append("queue[");
for (int i
= front
; i
< front
+ (rear
+ length
- front
) % length
; i
++) {
if((i
% length
) == ((rear
+ length
) - 1)%length
){
sb
.append(array
[i
%length
]);
}else{
sb
.append(array
[i
%length
] + ", ");
}
}
sb
.append("]");
return sb
.toString();
}
}
class Test{
public static void main(String
[] args
) {
ArrayQueue aq
= new ArrayQueue(4);
for (int i
= 1; i
<= 3; i
++) {
aq
.offer(i
);
}
System
.out
.println(aq
.toString());
System
.out
.println("出队列元素: " + aq
.poll());
System
.out
.println(aq
.toString());
aq
.offer(4);
System
.out
.println(aq
.toString());
System
.out
.println("队首元素: " + aq
.peek());
System
.out
.println(aq
.toString());
System
.out
.println("队首元素: " + aq
.element());
System
.out
.println(aq
.toString());
System
.out
.println("出队列元素: " + aq
.poll());
System
.out
.println(aq
.toString());
System
.out
.println("出队列元素: " + aq
.poll());
System
.out
.println(aq
.toString());
System
.out
.println("出队列元素: " + aq
.poll());
System
.out
.println(aq
.toString());
aq
.offer(5);
System
.out
.println(aq
.toString());
aq
.offer(6);
System
.out
.println(aq
.toString());
}
}
