# 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 {

public Dequeue() {
tail = null;
}

public void push_front(int item) {
Node node = new Node(item);
tail = node;
} else {
}
}

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

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

public int pop_front() {
} 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 {