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

- 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.

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