这是我完成它的方式,真正重要的是你要确保当你从一个栈中弹出并且它变为空时,它开始从另一个栈中弹出(我们必须确保它从栈的末尾弹出),我们可以通过将一个栈的内容排空到另一个栈中来实现这一点,并在那里继续弹出。
public class NewDeque {
这是最初的回答。
Stack<E> frontstack;
Stack<E> endstack;
public NewDeque() {
frontstack = new Stack<>();
endstack = new Stack<>();
}
void addFirst(E e) {
frontstack.push(e);
}
E delFirst() {
if (frontstack.isEmpty()) {
while (!endstack.isEmpty()) {
frontstack.push(endstack.pop());
}
return frontstack.pop();
}
return frontstack.pop();
}
void addLast(E e) {
endstack.push(e);
}
E delLast() {
if (endstack.isEmpty()) {
while (!frontstack.isEmpty()) {
endstack.push(frontstack.pop());
}
return endstack.pop();
}
return endstack.pop();
}
int size() {
return frontstack.size() + endstack.size();
}
boolean isEmpty() {
return (size() == 0) ? true : false;
}
E get(int i) {
if (i < endstack.size()) {
return endstack.get(endstack.size() - i - 1);
} else {
return frontstack.get(i - endstack.size());
}
}
static void print(NewDeque<Integer> ds) {
for (int i = 0; i < ds.size(); i++) {
System.out.print(" " + ds.get(i) + " ");
}
}
一个有趣的方法是按照以下方式进行
enqueue(q, x)
1) Push element x to stack1. This very simple, the problem is dequeue
dequeue(q)
1) If stacks1 and stack2 are empty then error "UNDERFLOW"
2) If stack2 is empty, then
while (stack1 is not empty) do
push all element from satck1 to stack2.
end while;
3) Pop the element from stack2 and return it.