我的代码:Java的双向队列执行:无法找到方法addlast仅逻辑错误()
注意:喜欢的readInt()和readString()函数是普林斯顿大学的algs4.jar包的一部分。
import java.util.Iterator;
import java.util.NoSuchElementException;
import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;
public class Deque <Item> implements Iterable <Item> {
private Node <Item> front;
private Node <Item> back;
private int numberOfItems;
private class Node <Item> {
Item item;
Node <Item> next;
Node <Item> prev;
}
public Deque() {
front = null;
back = null;
numberOfItems = 0;
}
public boolean isEmpty() {
return (numberOfItems == 0);
}
public int size() {
return numberOfItems;
}
public void addFirst(Item item) {
if (item == null) {
// When a null element is entered
throw new java.lang.NullPointerException("Item cannot be null");
}
Node <Item> newnode = new Node <Item>();
newnode.item = item;
if (numberOfItems == 0) {
// When there are no elements
front = newnode;
back = newnode;
} else {
// When there are >=1 elements
newnode.prev = front;
newnode.next = null;
front.next = newnode;
front = newnode;
}
numberOfItems++;
}
public void addLast(Item item) {
if (item == null) {
// When a null element is entered
throw new java.lang.NullPointerException("Item cannot be null");
}
Node <Item> newnode = new Node <Item>();
newnode.item = item;
if (numberOfItems == 0) {
// When there are no elements
front = newnode;
back = newnode;
} else {
// When there are >=1 elements
newnode.next = back;
newnode.prev = null;
back.prev = newnode;
back = newnode;
}
numberOfItems++;
}
public Item removeFirst() {
if (numberOfItems == 0) {
// When the deque is empty
throw new NoSuchElementException("No item to remove");
}
Item oldfirst = front.item;
if (numberOfItems == 1) {
front = null;
back = null;
} else {
front = front.prev;
}
numberOfItems--;
return oldfirst;
}
public Item removeLast() {
if (numberOfItems == 0) {
// When deque is empty
throw new NoSuchElementException("No item to remove");
}
Item oldlast = back.item;
if (numberOfItems == 1) {
front = null;
back = null;
} else {
back = back.next;
}
numberOfItems--;
return oldlast;
}
public Iterator <Item> iterator() {
return new ListIterator();
}
private class ListIterator implements Iterator <Item> {
private Node <Item> current = front;
public boolean hasNext() {
return (current != null);
}
public void remove() {
throw UnsupportedOperationException("remove is unsupported");
}
public Item next() {
Item item = current.item;
current = current.prev;
return item;
}
}
public static void main(String[] args) {
Deque <String> deq = new Deque();
String word;
while (!StdIn.isEmpty()) {
String cmd = StdIn.readString();
if (cmd.equals("af")) {
word = StdIn.readString();
deq.addFirst(word);
} else if (cmd.equals("al")) {
word = StdIn.readString();
deq.addFirst(word);
} else if (cmd.equals("rf")) {
deq.removeFirst();
} else if (cmd.equals("rl")) {
deq.removeLast();
} else if (cmd.equals("noi")) {
StdOut.println(deq.size());
}
}
}
}
我实现双端队列为链接节点的集合。每个节点都有三个特征 - 内容,下一个项目的链接和前一个项目的链接。前面和后面的类变量分别是第一个和最后一个元素的指针。
当我用我的测试客户端运行程序时,发现addLast(Item)这个方法将项目插入前端而不是后端。
这是怎么发生的?我的逻辑有什么问题?
我的猜测是你交换了'front'和'back'节点的角色。你应该始终检查你的逻辑,因为所有的方法都可能存在类似的问题。 –