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.
分析:
这道题目实际是要求实现deque,并不是太难
解法:
class DoublyListNode {
public int val;
public DoublyListNode prev, next;
DoublyListNode(int val) {
this.val = val;
this.prev = null;
this.next = null;
}
}
public class Dequeue {
DoublyListNode first, last;
public Dequeue() {
// do initialize if necessary
}
public void push_front(int item) {
// Write your code here
if (first == null || last == null) {
first = new DoublyListNode(item);
last = first;
} else {
DoublyListNode temp = new DoublyListNode(item);
temp.next = first;
first.prev = temp;
first = temp;
}
}
public void push_back(int item) {
// Write your code here
if (first == null || last == null) {
first = new DoublyListNode(item);
last = first;
} else {
DoublyListNode temp = new DoublyListNode(item);
last.next = temp;
temp.prev = last;
last = temp;
}
}
public int pop_front() {
// Write your code here
int res = -1;
if (this.isEmpty() ) {
return res;
} else if (first == last) {
res = first.val;
first = null;
last = null;
} else {
res = first.val;
first = first.next;
first.prev = null;
}
return res;
}
public int pop_back() {
// Write your code here
int res = -1;
if (this.isEmpty() ) {
return res;
} else if (first == last) {
res = last.val;
first = null;
last = null;
} else {
res = last.val;
last = last.prev;
last.next = null;
}
return res;
}
public boolean isEmpty() {
return first == null || last == null;
}
}