Implement Queue by Linked List II(lintcode 493)

Description

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

1. push_front(item). Add a new item to the front of queue.
2. push_back(item). Add a new item to the back of the queue.
3. pop_front(). Move the first item out of the queue, return it.
4. 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

Interface

public class Dequeue {

    public Dequeue() {
        // do initialize if necessary
    }

    public void push_front(int item) {
        // Write your code here
    }

    public void push_back(int item) {
        // Write your code here
    }

    public int pop_front() {
        // Write your code here
    }

    public int pop_back() {
        // Write your code here
    }
}

Solution

class Node {
    public int val;
    public Node prev, next;
    public Node(int val) {
        this.val = val;
        prev = next = null;
    }
}

public class Dequeue {
    public Node head, tail;

    public Dequeue() {
        // do initialize if necessary
        head = tail = null;
    }

    public void push_front(int item) {
        // Write your code here
        if (head == null) {
            head = tail = new Node(item);
        } else {
            Node newHead = new Node(item);
            newHead.next = head;
            head.prev = newHead;
            head = newHead;
        }
    }

    public void push_back(int item) {
        // Write your code here
        if (tail == null) {
            head = tail = new Node(item);
        } else {
            Node newTail = new Node(item);
            newTail.prev = tail;
            tail.next = newTail;
            tail = tail.next;
        }
    }

    public int pop_front() {
        // Write your code here
        if (head != null) {
            int ret = head.val;
            head = head.next;
            if (head == null) {
                tail = null;
            } else {
                head.prev = null;
            }
            return ret;
        }
        return -1;
    }

    public int pop_back() {
        // Write your code here
        if (tail != null) {
            int ret = tail.val;
            tail = tail.prev;
            if (tail == null) {
                head = null;
            } else {
                tail.next = null;
            }
            return ret;
        }
        return -1;
    }
}