Implement Queue using Stacks
[抄题]:
[思维问题]:
[一句话思路]:
取头部、取出来的时候,用一个output来倒序
[输入量]:空: 正常情况:特大:特小:程序里处理到的特殊情况:异常情况(不合法不合理的输入):
[画图]:
[一刷]:
- this.queue = new LinkedList<Integer>(); queue的本质是链表,右边要写成linkedlist
[总结]:
[复杂度]:Time complexity: O() Space complexity: O()
[英文数据结构,为什么不用别的数据结构]:
[其他解法]:
[Follow Up]:
[题目变变变]:
class MyQueue {
Stack<Integer> input = new Stack();
Stack<Integer> output = new Stack(); public MyQueue() {
this.input = new Stack<Integer>();
this.output = new Stack<Integer>();
} /** Push element x to the back of queue. */
public void push(int x) {
input.push(x);
} /** Removes the element from in front of queue and returns that element. */
public int pop() {
peek();
return output.pop();
} /** Get the front element. */
public int peek() {
if (output.empty()) {
while (!input.empty()) {
output.push(input.pop());
}
}
return output.peek();
} /** Returns whether the queue is empty. */
public boolean empty() {
if(output.empty() && input.empty()) {
return true;
}
return false;
}
}
Implement Stack using Queues
[抄题]:
[思维问题]:
[一句话思路]:
[输入量]:空: 正常情况:特大:特小:程序里处理到的特殊情况:异常情况(不合法不合理的输入):
[画图]:
[一刷]:
- this.queue = new LinkedList<Integer>(); 右边是LinkedList
- Queue的push要先把新元素加进去。不然怎么去挤谁呢……
- queue的操作语言是poll, add。stack是push/pop
- 判断空都写isempty
[二刷]:
- 取top时要用peek方法,直接用poll取出来的不一定是最大的
- 一开始只需要初始化数据结构,不需要新建对象:Queue<Integer> queue;
[总结]:
[复杂度]:Time complexity: O() Space complexity: O()
[英文数据结构,为什么不用别的数据结构]:
[其他解法]:
[Follow Up]:
[题目变变变]:
class MyStack {
Queue<Integer> queue;
/** Initialize your data structure here. */
public MyStack() {
this.queue = new LinkedList<Integer>();
} /** Push element x onto stack. */
public void push(int x) {
queue.add(x);
for (int i = 0; i < queue.size() - 1; i++) {
queue.add(queue.poll());
}
} /** Removes the element on top of the stack and returns that element. */
public int pop() {
return queue.poll();
} /** Get the top element. */
public int top() {
return queue.peek();
} /** Returns whether the stack is empty. */
public boolean empty() {
if (queue.isEmpty()) {
return true;
}
return false;
}
}