1、改进的链表（增加tail）
增加tail，指向链表尾部节点。这样在head和tail添加节点都很容易。
从tail端删除节点并不容易，因为无法找到tail之前的那个节点。在head端删除节点容易。
根据以上特性， head端作为队首， tail端最为队尾。 从head端删除元素，从tail端插入元素。
这里不使用虚拟头节点dummyHead，要注意链表为空时，head和tail都将指向空。
2、自定义队列
使用链表实现自定义队列
public class LinkedListQueue<E> implements IQueue<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;
//尾结点
private Node tail;
//队列元素个数
private int size;
public LinkedListQueue(){
head = null;
tail = null;
size = 0;
}
public int getSize() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
//入队(在队尾入队)
public void enqueue(E e) {
if(tail == null){
tail = new Node(e);
head = tail;
}else {
tail.next = new Node(e);;
tail = tail.next;
}
size++;
}
//在队首出队
public E dequeue() {
if(isEmpty()){
throw new IllegalArgumentException("Can't dequeue from an empty queue.");
}
//序号删除的节点
Node deleteNode = head;
head = head.next;
deleteNode.next = null;
//如果队列里只有1个元素，此时head为空，那么tail也为空。
if(head == null){
tail = null;
}
size --;
return deleteNode.e;
}
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： 队首 ");
Node cur = head;
while (cur != null){
res.append(cur + "->");
cur = cur.next;
}
res.append("NULL 队尾");
return res.toString();
}
public static void main(String[] args) {
LinkedListQueue<Integer> queue = new LinkedListQueue<Integer>();
for(int i = 0; i < 10; i++){
queue.enqueue(i);
System.out.println(queue);
if(i % 3 == 2){
queue.dequeue();
System.out.println("移除一个队首元素=> " + queue);
}
}
}
}
测试自定义队列
public static void main(String[] args) {
LinkedListQueue<Integer> queue = new LinkedListQueue<Integer>();
for(int i = 0; i < 10; i++){
queue.enqueue(i);
System.out.println(queue);
if(i % 3 == 2){
queue.dequeue();
System.out.println("移除一个队首元素=> " + queue);
}
}
}
输出结果如下：
移除一个队首元素=> 队列Queue： 队首 1->2->NULL 队尾 队列Queue： 队首 1->2->3->NULL 队尾 队列Queue： 队首 1->2->3->4->NULL 队尾 队列Queue： 队首 1->2->3->4->5->NULL 队尾 移除一个队首元素=> 队列Queue： 队首 2->3->4->5->NULL 队尾 队列Queue： 队首 2->3->4->5->6->NULL 队尾 队列Queue： 队首 2->3->4->5->6->7->NULL 队尾 队列Queue： 队首 2->3->4->5->6->7->8->NULL 队尾 移除一个队首元素=> 队列Queue： 队首 3->4->5->6->7->8->NULL 队尾 队列Queue： 队首 3->4->5->6->7->8->9->NULL 队尾
3、三种队列数字队列，循环队列，链表队列的比较
public static void main(String[] args) {
int opCount = 100000;
ArrayQueue<Integer> arrayQueue = new ArrayQueue<Integer>();
double time1 = testQueue(arrayQueue, opCount);
System.out.println("数组队列ArrayQueue, time: " + time1 + "秒");
LoopQueue<Integer> loopQueue = new LoopQueue<Integer>();
double time2 = testQueue(loopQueue, opCount);
System.out.println("循环队列LoopQueue, time: " + time2 + "秒");
LinkedListQueue<Integer> linkedListQueue = new LinkedListQueue<Integer>();
double time3 = testQueue(linkedListQueue, opCount);
System.out.println("链表队列LinkedListQueue, time: " + time3 + "秒");
}
输出结果：
数组队列ArrayQueue, time: 3.85538871秒 循环队列LoopQueue, time: 0.012212114秒 链表队列LinkedListQueue, time: 0.013916293秒
可以看出，循环队列和链表队列耗时相差不多。