玩转数据结构（七）基于链表的队列

浅浅的花香味﹌ 2022-05-21 08:38 161阅读 0赞

基于链表实现的队列，需要三个元素：头指针head、尾指针tail、计数的size。

### 1、实现的Queue<E>接口 ###

public interface Queue<E> {
        int getSize();
        void enqueue(E e);
        E dequeue();
        E getFront();
        boolean isEmpty();
    }

### 2、实现代码 ###

public class LinkedListQueue<E> implements Queue<E> {
        private class Node {//内部类：链表结点的定义
            private E e;
            private Node next;
    
            public Node() {
                this(null, null);
            }
    
            public Node(E e) {
                this(e, null);
            }
    
            public Node(E e, Node next) {
                this.e = e;
                this.next = next;
            }
    
            @Override
            public String toString() {
                return e.toString();
            }
        }
    
        private Node head;//链表头指针
        private Node tail;//链表尾指针
        private int size;//计数
    
        public LinkedListQueue() {
            head = null;
            tail = null;
            size = 0;
        }
    
        @Override
        public int getSize() {
            return size;
        }
    
        @Override
        public void enqueue(E e) {
            //说明此时队列为空
            if(tail == null) {
                tail = new Node(e);
                head = tail;//两个指针均指向第一个头结点
            } else {//队列不为空
                Node node = new Node(e);
                tail.next = node;
                tail = node;
            }
    
            size++;
        }
    
        @Override
        public E dequeue() {
            if(isEmpty()) {
                throw new IllegalArgumentException("cannot dequeue from an empty queue");
            }
    
            Node resNode = head;
            head = head.next;
            resNode.next = null;
            size--;
    
            return resNode.e;
        }
    
        @Override
        public E getFront() {
            if(isEmpty()) {
                throw new IllegalArgumentException("cannot dequeue from an empty queue");
            }
            return head.e;
        }
    
        @Override
        public boolean isEmpty() {
            return size == 0;
        }
    
        @Override
        public String toString() {
            StringBuilder str = new StringBuilder();
            str.append(String.format("LinkedListQueue: size=%d ", this.getSize()));
            str.append("front [");
            Node cur = head;
            while(cur != null) {
                str.append(cur.e + "->");
                cur = cur.next;
            }
            str.append("NULL");
            str.append("] tail");
            return str.toString();
        }
    }

### 2、测试代码 ###

public static void main(String[] args) {
            LinkedListQueue<Integer> linkedListQueue = new LinkedListQueue<Integer>();
            for (int i = 0; i < 10; i++) {
                linkedListQueue.enqueue(i);
                System.out.println(linkedListQueue);
    
                if(i % 3 == 2) {
                    linkedListQueue.dequeue();
                    System.out.println(linkedListQueue);
                }
            }
        }

### 3、结果 ###

LinkedListQueue: size=1 front [0->NULL] tail
    LinkedListQueue: size=2 front [0->1->NULL] tail
    LinkedListQueue: size=3 front [0->1->2->NULL] tail
    LinkedListQueue: size=2 front [1->2->NULL] tail
    LinkedListQueue: size=3 front [1->2->3->NULL] tail
    LinkedListQueue: size=4 front [1->2->3->4->NULL] tail
    LinkedListQueue: size=5 front [1->2->3->4->5->NULL] tail
    LinkedListQueue: size=4 front [2->3->4->5->NULL] tail
    LinkedListQueue: size=5 front [2->3->4->5->6->NULL] tail
    LinkedListQueue: size=6 front [2->3->4->5->6->7->NULL] tail
    LinkedListQueue: size=7 front [2->3->4->5->6->7->8->NULL] tail
    LinkedListQueue: size=6 front [3->4->5->6->7->8->NULL] tail
    LinkedListQueue: size=7 front [3->4->5->6->7->8->9->NULL] tail

### 4、时间复杂度分析 ###

因为这是基于链表实现的队列，因此入队和出队操作的时间复杂度均为O（1）