Java,  算法和数据结构

如何用链表来实现队列

零说明

我们前面用链表实现了栈,只需用链表头充当栈顶,每次入栈时,调用链表的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种方式实现了队列:

数组实现的普通队列;

循环队列;

用栈这种数据结构实现队列;

链表实现队列。

留言