in LintCode Queue ~ read.

Implement Queue by Linked List II

LintCode-493.Implement Queue by Linked List II

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.

This is a follow-up problem of Implement Queue by Linked List.

class Node {  
    int val;
    Node prev, next;

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

public class Dequeue {  
    private Node head, tail;

    public Dequeue() {
        head = null;
        tail = null;
    }

    public void push_front(int item) {
        Node node = new Node(item);
        if (head == null) {
            head = node;
            tail = node;
        } else {
            node.next = head;
            head.prev = node;
            head = node;
        }
    }

    public void push_back(int item) {
        Node node = new Node(item);

        if (tail == null) {
            tail = node;
            head = node;
        } else {
            tail.next = node;
            node.prev = tail;
            tail = tail.next;
        }
    }

    public int pop_front() {
        if (head != null) {
            Node node = head;
            head = head.next;
            if (head != null) {
                head.prev = null;
            } else {
                tail = null;
            }

            return node.val;
        }

        return -1;
    }

    public int pop_back() {
        if (tail != null) {
            Node node = tail;
            tail = node.prev;

            if (tail != null) {
                tail.next = null;
            } else {
                head = null;
            }

            return node.val;
        }

        return -1;
    }
}

Hope this helps,
Michael