如何实现队列这种数据结构
零 队列这种数据结构的特征
- 依然是一种线性数据结构；
- 规定只能在两端操作的数据结构，不能操作中间元素；
- 先进先出，First In First Out；
一 队列的实现思路
我们在前面自己动手实现了一个支持泛型类的数组，那么我们就可以考虑通过数组这种线性数据结构来实现一个队列。当然，我们也可以用链表实现一个队列。
先定义一个支持泛型的队列的接口，包含入队操作、出队操作、查看队首元素、查看队列的大小、队列是否为空的几个接口方法。外带2个构造方法。
然后，定义一个底层用数组实现的栈，来实现这个接口。
二 队列代码实现
1定义队列接口的代码
public interface Queue<E>{
//入队操作
void enqueue(E e);
//出队操作
E dequeue();
//查看队首元素
E getFront();
//队列是否为空
boolean isEmpty();
//查看队列长度，实际是查看队列中有几个元素
int getSize();
}2动态数组实现队列接口
public class ArrayQueue<E> implements Queue<E>{
//底层用动态数组来实现，将其定义为成员变量
private Array<E> array;
public ArrayQueue(int capacity){
array=new Array<>(capacity);
}
public ArrayQueue(){
array = new Array<>();
}
@Override
public void enqueue(E e){
array.addLast(e);
}
@Override
public E dequeue(){
//此操作的时间复杂度是O(n),因为底层动态数组的删除第1个元素之后，后面的元素会向前移动
return array.removeFirst();
}
@Override
public E getFront(){
return array.getFirst();
}
@Override
public int getSize(){
return array.getSize();
}
@Override
public boolean isEmpty(){
return array.isEmpty();
}
@Override
public String toString(){
StringBuilder stringBuilder = new StringBuilder();
stringBuilder.append("Queue: head[");
for(int i=0;i<array.getSize();i++){
stringBuilder.append(array.get(i));
if(i != array.getSize()-1){
stringBuilder.append(" , ");
}
}
stringBuilder.append("]tail");
return stringBuilder.toString();
}
public static void main(String[] args){
ArrayQueue<Integer> arrayQueue = new ArrayQueue<>();
System.out.println(arrayQueue.getSize());
System.out.println(arrayQueue.isEmpty());
for (int i = 0; i < 5; i++) {
arrayQueue.enqueue(i);
}
System.out.println(arrayQueue.dequeue());
System.out.println(arrayQueue.getFront());
System.out.println(arrayQueue.getSize());
System.out.println(arrayQueue.isEmpty());
System.out.println(arrayQueue);
}
}
//结果：
0
true
0
1
4
false
Queue head [1 , 2 , 3 , 4] tail三 复杂度分析
入队enqueue： O(1)，因为是在队尾添加元素；
出队dequeue：O(n)，因为底层动态数组删除第一个元素之后，后面的所有元素会逐一向前移动；
查看队首元素getFront()：O(1)，底层数组直接查看第一个元素；
查看队列元素个数getSize()：O(1)，调用底层数组的getSize()；
队列判空isEmpty()：O(1)，调用底层数组的isEmpty()；
由于出队的复杂度是O(n)，效率不是很好，并且当前实现机制下，随着不断的出队、入队操作，每次出队操作，都将导致底层数组元素向前移动，这个性能不是很理想。接下来，我们看看能否实现一个出队复杂度也是O(1)的队列呢？
2条评论
Pingback:
Pingback: