一個用Java實現的雙向佇列,可以分別在頭尾插入和刪除節點

NO IMAGE

分析,雙向佇列的內部實現是一個雙向連結串列,可以分別從頭尾插入和刪除節點。

通常使用一個first指向頭 last指向尾。然後分別維護各種next和prev指標。通常情況要考慮邊界條件,即當佇列本身為空的時候插入新節點如何維護first和last的指向

刪除節點的時候,若佇列變為空又應該如何維護first和last指標。非常繁瑣而且容易寫錯,不過使用的空間最少,程式碼如下

import java.util.Iterator;
import java.util.NoSuchElementException;
import edu.princeton.cs.algs4.StdOut;
public class Deque<Item> implements Iterable<Item> {
private int n;
private Node first;
private Node last;
private class Node {
private Item item;
private Node next;
private Node prev;
}
public Deque() {
n = 0;
first = null;
last = null;
}
public boolean isEmpty() {
return first == null;
}
public int size() {
return n;
}
public void addFirst(Item item) {
if (item == null)
throw new NullPointerException("can't add null element!");
Node oldfirst = first;
first = new Node();
first.item = item;
first.prev = null;
// it is and empty queue..
if (oldfirst == null) {
last = first;
first.next = null;
}
else {
first.next = oldfirst;
oldfirst.prev = first;
}
n  ;
}
public void addLast(Item item) {
if (item == null)
throw new NullPointerException("can't add null element!");
Node oldlast = last;
last = new Node();
last.item = item;
last.next = null;
if (oldlast == null) {
first = last;
last.prev = null;
} else {
last.prev = oldlast;
oldlast.next = last;
}
n  ;
}
public Item removeFirst() {
if (isEmpty())
throw new NoSuchElementException(
"Can't remove from empty deque");
Item item = first.item;
first = first.next;
n--;
if (n == 0)
last = null;
else
first.prev = null;
return item;
}
public Item removeLast() {
if (isEmpty())
throw new NoSuchElementException(
"Stack underflow");
Item item = last.item;
last = last.prev;
n--;
if (n == 0)
first = null;
else
last.next = null;
return item;
}
public Iterator<Item> iterator() {
return new DequeIterator();
}
private class DequeIterator implements Iterator<Item> {
private Node current = first;
public boolean hasNext() {
return current != null;
}
public void remove() {
throw new UnsupportedOperationException(
"remove is not supported!");
}
public Item next() {
if (!hasNext())
throw new NoSuchElementException();
Item item = current.item;
current = current.next;
return item;
}
}
public static void main(String[] args) {
Deque<String> dq = new Deque<String>();
dq.addFirst("A");
dq.addFirst("B");
dq.addFirst("C");
dq.addLast("Q");
dq.addLast("E");
dq.addLast("D");
for (String s : dq) {
StdOut.println(s);
}
StdOut.println("Remove first"   dq.removeFirst());
StdOut.println("Remove last"   dq.removeLast());
for (String s : dq) {
StdOut.println(s);
}
}
}

另一種方法是引入一個哨兵節點nil, 初始化時nil的prev和next分別指向自身。用於判斷佇列是否為空

加入新元素以後只需要操作新增節點,nil 和 nil的下一個節點。不需要考慮邊界情況(因為沒有nullpointer)

該方法僅多使用了一個節點的空間,但是程式碼看起來更加簡潔如下

import java.util.Iterator;
import java.util.NoSuchElementException;
import edu.princeton.cs.algs4.StdOut;
import edu.princeton.cs.algs4.StdRandom;
public class Deque<Item> implements Iterable<Item> {
private int n;
private Node nil;
private class Node {
private Item item;
private Node next;
private Node prev;
}
public Deque() {
n = 0;
nil = new Node();
nil.next = nil;
nil.prev = nil;
}
public boolean isEmpty() {
return nil.next == nil;
}
public int size() {
return n;
}
public void addFirst(Item item) {
if (item == null)
throw new NullPointerException("can't add null element!");
Node first = new Node();
first.item = item;
first.prev = nil;
first.next = nil.next;
nil.next.prev = first;
nil.next = first;
n  ;
}
public void addLast(Item item) {
if (item == null)
throw new NullPointerException("can't add null element!");
Node last = new Node();
last.item = item;
last.next = nil;
last.prev = nil.prev;
nil.prev.next = last;
nil.prev = last;
n  ;
}
public Item removeFirst() {
if (isEmpty())
throw new NoSuchElementException(
"Can't remove from empty deque");
Node del = nil.next;
Item item = del.item;
del.next.prev = nil;
nil.next = del.next;
n--;
return item;
}
public Item removeLast() {
if (isEmpty())
throw new NoSuchElementException(
"Stack underflow");
Node del = nil.prev;
Item item = del.item;
del.prev.next = nil;
nil.prev = del.prev;
n--;
return item;
}
public Iterator<Item> iterator() {
return new DequeIterator();
}
private class DequeIterator implements Iterator<Item> {
private Node current = nil.next;
public boolean hasNext() {
return current != nil;
}
public void remove() {
throw new UnsupportedOperationException(
"remove is not supported!");
}
public Item next() {
if (!hasNext())
throw new NoSuchElementException();
Item item = current.item;
current = current.next;
return item;
}
}
public static void main(String[] args) {
Deque<Integer> dq = new Deque<Integer>();
for (int i = 0; i < 10; i  ) {
int r = StdRandom.uniform(1, 65535);
StdOut.println("Random add and remove node for "   r);
for (int j = 0; j < r; j  ) {
if (StdRandom.uniform() > 0.5)
dq.addFirst(StdRandom.uniform(0, 10));
else
dq.addLast(StdRandom.uniform(0, 10));
}
for (int n : dq)
StdOut.println(n); 
for (int j = 0; j < r; j  ) {
if (StdRandom.uniform() > 0.5)
dq.removeFirst();
else
dq.removeLast();
}
}
StdOut.println("Done!");
}
}