一.简介

  之前用数组实现了时间复杂度为O(n)的数组队列和时间复杂度为O(1)的循环队列，队列是一种需要经常插入或删除的数据结构，所以链表也会是一种比较合适的队列实现方式。

二.链表队列代码实现

/**
* 链表队列 时间复杂度O(1)
*/
public class LinkedListQueue<E> implements Queue<E> {

 /**
  * 入队 时间复杂度O(1)
  */
 @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++;
 }

 /**
  * 出队 时间复杂度O(1)
  */
 @Override
 public E dequeue() {
   if (isEmpty()) {
     throw new IndexOutOfBoundsException();
   }
   Node ret = head;
   head = head.next;
   ret.next = null;
   if (head == null) {
     tail = null;
   }
   size--;
   return ret.e;
 }

 /**
  * 查看队列第一个元素 时间复杂度O(1)
  */
 @Override
 public E getFront() {
   if (isEmpty()) {
     throw new IndexOutOfBoundsException();
   }
   return head.e;
 }

 @Override
 public int getSize() {
   return size;
 }

 @Override
 public boolean isEmpty() {
   return tail == null;
 }

 @Override
 public String toString() {
   StringBuilder builder = new StringBuilder();
   Node cur = head;
   builder.append("head:");
   while (cur != null) {
     builder.append(cur.e).append(" ");
     cur = cur.next;
   }
   builder.append(" tail");
   return builder.toString();
 }

 private class Node {

   public E e;
   public Node next;

   public Node(E e) {
     this(e, null);
   }

   public Node(E e, Node next) {
     this.e = e;
     this.next = next;
   }

   public Node() {
     this(null, null);
   }
 }

 private int size;
 private Node head;
 private Node tail;

 public LinkedListQueue() {
   size = 0;
   head = null;
   tail = null;
 }


}

三.时间复杂度分析

• 测试代码

import java.util.Random;

public class Main {

    // 测试使用q运行opCount个enqueueu和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) / 1000000000.0;
    }

    public static void main(String[] args) {

        int opCount = 100000;
        //数组队列
        ArrayQueue<Integer> arrayQueue = new ArrayQueue<>();
        double time1 = testQueue(arrayQueue, opCount);
        System.out.println("ArrayQueue, time: " + time1 + " s");
       //循环队列
        LoopQueue<Integer> loopQueue = new LoopQueue<>();
        double time2 = testQueue(loopQueue, opCount);
        System.out.println("LoopQueue, time: " + time2 + " s");
        //链表队列
        LinkedListQueue<Integer> linkedListQueue = new LinkedListQueue<>();
        double time3 = testQueue(linkedListQueue, opCount);
        System.out.println("LinkedListQueue, time: " + time3 + " s");
    }
}

• 测试结果

ArrayQueue, time: 2.594156423 s
LoopQueue, time: 0.012509621 s
LinkedListQueue, time: 0.006957591 s

• 结果分析
  1.ArrayQueue 是一个时间复杂度总体为O(n)的数据结构所以耗时远远超过O(1)时间复杂度的LoopQueue和LinkedListQueue
  2.LoopQueue在100000次操作的结果上所耗的时间小于LinkedListQueue，但这并不是绝对的，影响LoopQueue的操作主要是数组的扩容，而影响LinkedListQueue的操作主要是对象的创建， 当需要操作越多，new 操作就越耗时，因为jvm需要不断找寻空间开辟新的对象

结论：LinkedListStack和ArrayStack复杂度都是O(1)，差异不大