Implement Queue by Linked List II 493

Question

Implement a Queue by linked list. Provide the following basic methods:

push_front(item). Add a new item to the front of queue.

push_back(item). Add a new item to the back of the queue.

pop_front(). Move the first item out of the queue, return it.

pop_back(). Move the last item out of the queue, return it.

Example:

push_front(1)

push_back(2)

pop_back() // return 2

pop_back() // return 1

push_back(3)

push_back(4)

pop_front() // return 3

pop_front() // return 4

Solution

用head和tail记录队列的头尾。两点注意：

1) 要在front插入，所以head为dummy node（其next为队头node），tail为队尾node。

2) 要在back出队，所以用双向链表，这样队尾node出队后tail可以往前移动

代码如下：

class ListNode{
    int val;
    ListNode next;
    ListNode pre;
    public ListNode(int val){
        this.val = val;
    }
}

class Queue{
    ListNode tail;
    ListNode head;

    public Queue(){
        tail = null;
        head = new ListNode(0);
    }

    public void push_front(int value){
        ListNode node = new ListNode(value);
        if(tail == null){
            head.next = node;
            node.pre = head;
            tail = node;
        }else{
            node.next = head.next;
            node.next.pre = node;
            node.pre = head;
            head.next = node;
        }
    }

    public void push_back(int value){
        ListNode node = new ListNode(value);
        if(tail == null){
            head.next = node;
            node.pre = head;
            tail = node;
        }else{
            tail.next = node;
            node.pre = tail;
            tail = tail.next;
        }
    }

    public int pop_front(){
        if(head.next == null){
            return -1;
        }
        int res = head.next.val;
        head.next = head.next.next;
        if(head.next == null){
            tail = null;
            return res;
        }
        head.next.pre = head;
        return res;
    }

    public int pop_back(){
        if(tail == null){
            return -1;
        }
        int res = tail.val;
        if(tail.pre == head){
            tail = null;
            return res;
        }
        tail = tail.pre;
        return res;
    }
}