492. Implement Queue by LinkedList I II

Leave a comment

September 4, 2016 by oneOokay

Implement Queue by LinkedList I:

嗯。。。我写通的是一个double linked list,有点杀鸡用牛刀的感觉,普通的linkedlist的就行了。

一个first node, 一个last node,enqueue的时候放到last node,dequeue的时候从first node那里取。

public class Queue {
private Node first;
private Node last;
private class Node {
int value;
Node next;
public Node(int value){
this.value = value;
next = null;
}
}
public Queue() {
first = null;
last = null;
}

public void enqueue(int item) {
if (first == null) {
last = new Node(item);
first = last;
}else {
Node newNode = new Node(item);
last.next = newNode;
last = newNode;
}
}

public int dequeue() {
int result = first.value;
first = first.next;
return result;
}
}

Implement Queue by LinkedList II:

这个需要double linked list: prev and next.注意一些null处理之类的。。。

public class Dequeue {

private class Node{
int value;
Node next;
Node prev;
public Node(int value) {
this.value = value;
next = null;
prev = null;
}
}

Node first;
Node last;
public Dequeue() {
// do initialize if necessary
first = null;
last = null;
}

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

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

public int pop_front() {
int result = first.value;
Node node = first.next;
if(node != null){
node.prev = null;
}else {
last = null;
}
first = node;
return result;
}

public int pop_back() {
int result = last.value;
Node node = last.prev;
if(node != null) {
node.next = null;
}else {
first = null;
}
last = node;
return result;
}
}

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: