思路

  1. 先進先出
  2. 紀錄開始與結尾元素

實作

測試方法


public class Queue_List2 {
    static class Node {
        Integer val;
        Node next;

        public Node(Integer val) {
            this.val = val;
        }
    }

    Integer[] nums;
    Node node_front = null;
    Node node_end = null;

    public Queue_List2(Integer[] nums) {
        this.nums = nums;
    }

    public void build_queue(){
        for (int i = 0 ; i < nums.length; i++) {
            offer(nums[i]);
        }
    }

public static void main(String[] args) {
    Integer[] nums = new Integer[]{1,2,3,4,5};
    Queue_List2 queue_list = new Queue_List2(nums);
    queue_list.build_queue();

    // full - extend the storage size
    queue_list.offer(6);

    Integer num = queue_list.poll();
    num = queue_list.poll();
    num = queue_list.poll();
    num = queue_list.poll();
    num = queue_list.poll();
    num = queue_list.poll();

    // empty
    num = queue_list.poll();

    System.out.println();
}

具體

offer

public void offer(Integer val) {
    if (node_front == null) { // empty
        node_front = new Node(val);
        node_end = node_front;
    }else {
        Node node_new = new Node(val);
        node_end.next = node_new; // 把新的節點接在結尾節點後面
        this.node_end = node_new; // 更新最後節點
    }
}

poll

public Integer poll() {
    if (node_front == null) { // empty
        return null;
    }

    Node node = node_front;
    node_front = node_front.next; // 更新開始節點

    if (node_front == null) { // empty
        node_end = null;
    }

    return node.val;
}