用链表实现无界队列

 1/**
 2 * 使用链表实现一个无界队列
 3 *
 4 * @author wangy
 5 * @version 1.0
 6 * @date 2021/6/28 / 15:09
 7 */
 8public class ListQueue {
 9    // index
10    private Node head;
11
12    private Node tail;
13
14    private int size;
15
16    public ListQueue() {
17    }
18
19    int size() {
20        return size;
21    }
22
23    int enQueue(int e) {
24        Node node = new Node(e);
25        // empty
26        if (size == 0) {
27            head = tail = node;
28        } else {
29            tail.next = node;
30            tail = node;
31        }
32        ++size;
33        return e;
34    }
35
36    int deQueue() {
37        if (size == 0) throw new RuntimeException("xx为空");
38        int e = head.n_data;
39        head = head.next;
40        // head = null, 链表元素全部弹出
41        if (head == null) tail = null;
42        --size;
43        return e;
44    }
45
46    // O(n)
47    void printAll() {
48        // 打印链表
49        System.out.print("[");
50        Node pos = head;
51        for (int i = 0; i < size; i++) {
52            if (i == size - 1) {
53                System.out.print(pos.n_data);
54            } else {
55                System.out.print(pos.n_data + ", ");
56            }
57            pos = pos.next;
58        }
59        System.out.println("]");
60    }
61
62    public static void main(String[] args) {
63        ListQueue lq = new ListQueue();
64        lq.enQueue(1);
65        lq.enQueue(2);
66//        lq.enQueue(3);
67        lq.enQueue(4);
68
69        lq.deQueue();
70        lq.deQueue();
71        lq.printAll();
72
73    }
74
75    /************************* 单链表 ************************/
76
77    private class Node {
78        private int n_data;
79        private Node next;
80
81        public Node(int n_data) {
82            this.n_data = n_data;
83            this.next = null;
84        }
85    }
86}