【Java】数据结构-链表实现队列(完整代码)
本帖最后由 孤樱懶契 于 2021-10-23 22:37 编辑# 链表实现队列的接口
## Queue.java
```java
public interface Queue<E> {
int getSize();
boolean isEmpty();
void enqueue(E e);
E dequeue();
E getFront();
}
```
# 链表实现队列操作执行结果
!(https://gitee.com/gylq/cloudimages/raw/master/img/image-20210626170535468.png)
# 链表实现队列操作（完整代码）
## LinkedListQueue.java（实现队列的操作）
```java
public class LinkedListQueue<E> implements Queue<E> {
private class Node{
public E e;
public Node next;
public Node(E e, Node next){
this.e = e;
this.next = next;
}
public Node(E e) { this(e, null);}
public Node() {this(null, null);}
@Override
public String toString(){ return e.toString(); }
}
private Node head, tail;
private int size;
public LinkedListQueue(){
head = null;
tail = null;
size = 0;
}
@Override
public int getSize(){
return size;
}
@Override
public boolean isEmpty(){
return size == 0;
}
//入队
@Override
public void enqueue(E e){
if(tail == null){
tail = new Node(e);
head = tail;
}
else{
tail.next = new Node(e);
tail = tail.next;
}
size ++;
}
//出队
@Override
public E dequeue(){
if(isEmpty())
throw new IllegalArgumentException("Cannot dequeue from an empty queue.");
Node retNode = head;
head = head.next;
retNode.next = null;
if(head == null)
tail = null;
size --;
return retNode.e;
}
@Override
public E getFront(){
if(isEmpty())
throw new IllegalArgumentException("Queue is empty");
return head.e;
}
@Override
public String toString(){
StringBuilder res = new StringBuilder();
res.append("Queue: front ");
Node cur = head;
while(cur != null){
res.append((cur + "->"));
cur = cur.next;
}
res.append("NULL tail");
return res.toString();
}
public static void main(String[] args){
LinkedListQueue<Integer> queue = new LinkedListQueue<>();
for(int i = 0 ; i < 10 ; i ++){
queue.enqueue(i);
System.out.println(queue);
if(i % 3 == 2){
queue.dequeue();
System.out.println(queue);
}
}
}
}
```
# 我对比了一下数组队列、循环数组队列、链表实现队列的时间输出结果截图
> - ## 明显循环数组队列和列表实现队列的时间相当，数组队列最差。相差100倍左右
!(https://gitee.com/gylq/cloudimages/raw/master/img/image-20210626170306274.png)
# 测试时间代码
```java
import java.util.Random;
public class Main {
// 测试使用q运行opCount个enqueue和dequeue操作所需要的时间，单位：秒
private static double testQueue(Queue<Integer> q, int opCount){
long startTime = System.nanoTime();
Random random = new Random();
for(int i = 0 ; i < opCount; i ++)
q.enqueue(random.nextInt(Integer.MAX_VALUE));
for(int i = 0 ; i < opCount ; i ++)
q.dequeue();
long endTime = System.nanoTime();
return (endTime - startTime) / 100000000.0;
}
public static void main(String[] args){
int opCount = 100000;
LoopQueue<Integer> loopQueue = new LoopQueue<>();
double time1 = testQueue(loopQueue, opCount);
System.out.println("LoopQueue , time: " + time1 + "s");
ArrayQueue<Integer> arrayQueue = new ArrayQueue<>();
double time2 = testQueue(arrayQueue, opCount);
System.out.println("arrayQueue , time: " + time2 + "s");
LinkedListQueue<Integer> linkedListQueue = new LinkedListQueue<>();
double time3 = testQueue(linkedListQueue, opCount);
System.out.println("LinkedListQueue , time: " + time3 + "s");
}
}
``` {:1_893:}厉害 666666
页:
[1]