java队列的数组实现
程序员文章站
2024-03-18 08:06:58
...
public class 数组Queue {
public static void main(String[] args) {
MyQueue queue = new MyQueue();
queue.init(5);
queue.endQueue(1);
queue.endQueue(2);
queue.endQueue(3);
queue.endQueue(4);
queue.endQueue(5);
int size = queue.getLength();
for(int i=0;i<size;i++){
Object e = queue.outQueue();
System.out.println(e);
}
System.out.println(queue.isEmpty());
}
interface IQueue {
void init(int l);
void destroy();
void clear();
boolean endQueue(Object e);
boolean isEmpty();
Object getHead();
int getLength();
Object outQueue();
}
static class MyQueue implements IQueue {
int head;
int tail;
int size;
Object[] array;
int len;
@Override
public void init(int l) {
head = 0;
tail = 0;
this.len = l;
array = new Object[len];
}
@Override
public void destroy() {
array = null;
}
@Override
public void clear() {
head = 0;
tail = 0;
for (int i = 0; i < len; i++) {
array[i] = null;
}
}
@Override
public boolean endQueue(Object e) {
//队列满时 不能加入
if (size >= len) {
return false;
}
//如果此时数组为空
if (head == tail) {
head = 0;
array[size] = e;
tail = 1;
size++;
return true;
}else{
array[tail] = e;
tail = tail + 1;
size++;
return true;
}
}
@Override
public boolean isEmpty() {
if(head == tail){
return true;
}
return false;
}
@Override
public Object getHead() {
return array[0];
}
@Override
public int getLength() {
return size;
}
/**
* 数组型队列
* <p>
* 同样需要一个头指针,一个尾指针 当头指针=尾指针=0时候为空
* 需要实现分配一个固定大小的数组
* 正常情况下下,尾指针永远指向队尾元素的下一个位置,比如说队尾元素在0 尾指针则在1
* <p>
* 注意!:数组型队列有很大的劣势,容易造成存储空间浪费,而且不易扩容。
* 比如说,最大空间为6的数组队列, 进去了6个了元素,然后从队头出去了5个元素,此时,仍然不能插入新的元素
* 因为队尾指针仍然指向第6个元素,其仍然占据了最后一个位置,而队头是不允许插入的。这样造成前面5个位置浪费。
* <p>
* 解决方法:
* 1.元素移动位置,出队一个 后面的元素往前挪。 缺点:每次出队都需要移动位置 很麻烦 效率也低
* 2.动态扩容, 缺点:浪费了前面的空间
* 3.最佳解决方案:构造环形队列
*/
@Override
public Object outQueue() {
if(head == tail){
return null;
}
Object e = array[head];
head = head +1;
size--;
return e;
}
}
}
上一篇: java队列的数组实现
下一篇: Java 数组实现的队列