如何用链表来实现队列
零说明
我们前面用链表实现了栈，只需用链表头充当栈顶，每次入栈时，调用链表的addFirst()，出栈时调用链表的removeFirst()即可。比较方便实现的原因是，栈的操作基本都在栈顶。而链表的addFirst()/removeFirst()也都是在链表头，完美匹配。
那么，如果想要用链表来实现先进先出的队列，该怎么实现呢？
一实现思路
由于队列需要在队首、队尾两端操作，所以，我们需要在链表的基础上除了头指针，还需要引入1个尾指针，用于指向最后1个结点。这样对于队列的入队操作，我们只需要让尾指针后移，反之，对于出队操作，我们让头指针后移即可。
二代码实现
1创建队列接口
public interface Queue<E>{
void enqueue(E e);
E dequeue();
E getFront();
int getSize();
boolean isEmpty();
}2用链表实现队列接口
/**
* @Author:asher
* @Date:2021/4/24 16:10
* @Description:PACKAGE_NAME
* @Version:1.0
*/
public class LinkedListImplementQueue<E> implements Queue<E>{
//先定义内部类Node
private class Node{
private E e;
private 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 LinkedListImplementQueue() {
head = null;
tail = null;
size = 0;
}
//实现队列接口中的方法
@Override
public int getSize() {
return size;
}
@Override
public boolean isEmpty() {
return head == tail;
}
@Override
public void enqueue(E e) {
//如果队列为空,tail=null,则此时head也一定=NULL
if (tail == null) {
Node node = new Node(e);
//尾指针指向新结点，头指针也指向这个新结点
tail = node;
head = tail;
} else {
Node node = new Node(e);
tail.next = node;
//尾指针tail，向后移动一个位置.head则不用做任何处理
tail = tail.next;
}
size++;
}
@Override
public E dequeue() {
//如果队列为空
if (head == null) {
throw new IllegalArgumentException("Queue is Empty.cannot dequeue.");
} else {
Node retNode = head;
//头指针后移
head = head.next;
//待返回结点和链表脱离关系
retNode.next = null;
//如果队列此时只有1个元素，出队之后，则head变为空.那么，尾指针tail就应该=null,
if (head == null) {
//只有1个元素的情况下，出队之前，head和tail都指向那个元素
tail = null;
}
size--;
return retNode.e;
}
}
@Override
public E getFront() {
if (head == null) {
throw new IllegalArgumentException("Queue is empty.cannot getFront().");
} else {
return head.e;
}
}
@Override
public String toString() {
StringBuilder stringBuilder = new StringBuilder();
stringBuilder.append("Queue: size: "+size+" head:");
Node curr = head;
while (curr!= null) {
stringBuilder.append(curr+"->");
curr = curr.next;
}
stringBuilder.append("NULL tail");
return stringBuilder.toString();
}
public static void main(String[] args) {
LinkedListImplementQueue<Integer> linkedListImplementQueue = new LinkedListImplementQueue<>();
for (int i = 0; i < 10; i++) {
linkedListImplementQueue.enqueue(i);
System.out.println(linkedListImplementQueue);
if (i % 3 == 2) {
linkedListImplementQueue.dequeue();
System.out.println(linkedListImplementQueue);
}
}
}
}
//结果：
Queue: size: 1 head:0->NULL tail
Queue: size: 2 head:0->1->NULL tail
Queue: size: 3 head:0->1->2->NULL tail
Queue: size: 2 head:1->2->NULL tail
Queue: size: 3 head:1->2->3->NULL tail
Queue: size: 4 head:1->2->3->4->NULL tail
Queue: size: 5 head:1->2->3->4->5->NULL tail
Queue: size: 4 head:2->3->4->5->NULL tail
Queue: size: 5 head:2->3->4->5->6->NULL tail
Queue: size: 6 head:2->3->4->5->6->7->NULL tail
Queue: size: 7 head:2->3->4->5->6->7->8->NULL tail
Queue: size: 6 head:3->4->5->6->7->8->NULL tail
Queue: size: 7 head:3->4->5->6->7->8->9->NULL tail三数组队列VS循环队列VS链表队列
前面，我们用数组实现了队列，由于数组队列出队时执行的是removeFirst()，导致元素迁移，性能不够好。
于是，我们引入了循环队列，这样出队时时间复杂度也是O(1)。
现在，也实现了用链表实现的队列。
我们可以在前面的数组实现的普通队列和循环队列比较的基础上，再加入链表队列的对比。
public class QueueTest {
private static long test(Queue queue, int count) {
long beginTime=System.currentTimeMillis();
for (int i = 0; i < count; i++) {
queue.enqueue(i);
}
for (int i = 0; i < count; i++) {
queue.dequeue();
}
long endTime = System.currentTimeMillis();
return (endTime-beginTime);
}
public static void main(String[] args) {
int count=100000;
long t1 = test(new ArrayQueue(), count);
long t2 = test(new CircularQueue(), count);
long t3 = test(new LinkedListImplementQueue(), count);
System.out.println("ArrayQueue:" + t1);
System.out.println("CircularQueue:" + t2);
System.out.println("LinkedListQueue:" + t3);
}
}
//结果
ArrayQueue:4609
CircularQueue:13
LinkedListQueue:12四 小结
至此，我们通过4种方式实现了队列：
数组实现的普通队列；
循环队列；
用栈这种数据结构实现队列；
链表实现队列。
