使用数组实现队列

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
package com.jxust.test;
public class Queue<E>{
/*
分析:
特点
先进先出 --> 每次出队列的是第一个元素
实现容器 --> 数组
队列的行为
1. 进队列
---> in()
2. 出队列
---> out()
3. 队列的大小
--->size()
4. 队列扩容
--->ensureCapacity()
*/
private Object[] topArray;
private int length;
// 队列的长度
// 初始化数组
public Queue(){
topArray = new Object[0];
length = topArray.length;
}
// 返回队列的大小
public int size(){
if(length > 0) return length;
else return -1;
}
// 入队
public void in(E element){
ensureCapacity(1);
topArray[length-1] = element;
}
// 出队
public synchronized E out(){
if(length < 0 ) throw new IndexOutOfBoundsException("Queue is empty");
E result = (E) topArray[0];
ensureCapacity(-1);
return result;
}
private void ensureCapacity(int len){
Object[] oldArray = topArray;
Object[] newArray = new Object[length + len];
if(len > 0){
// 扩容
for(int i = 0 ; i < length ; i++){
newArray[i] = oldArray[i];
}
}else {
// 缩容
for(int i = 1 ; i < length ; i++){
newArray[i-1] = oldArray[i];
}
}
topArray = newArray;
length = topArray.length;
}
// 获取队列中指定位置的元素
public E getElement(int index){
if(index < 0 || index > length) throw new IndexOutOfBoundsException("Queue not");
return (E) topArray[index];
}
}