My code:
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
class MyStack {
private Queue<Integer> q = new LinkedList<Integer>();
// Push element x onto stack.
public void push(int x) {
q.offer(x);
}
// Removes the element on top of the stack.
public void pop() {
if (q.isEmpty())
return;
ArrayList<Integer> temp = new ArrayList<Integer>(q.size());
int len = q.size();
for (int i = 0; i < len; i++) {
temp.add(q.poll());
}
for (int i = 0; i < len - 1; i++)
q.offer(temp.get(i));
}
// Get the top element.
public int top() {
if (q.isEmpty())
return - 1;
ArrayList<Integer> temp = new ArrayList<Integer>(q.size());
int len = q.size();
for (int i = 0; i < len; i++) {
temp.add(q.poll());
}
int ret = temp.get(temp.size() - 1);
for (int i = 0; i < len; i++)
q.offer(temp.get(i));
return ret;
}
// Return whether the stack is empty.
public boolean empty() {
return q.isEmpty();
}
public static void main(String[] args) {
MyStack test = new MyStack();
test.push(1);
System.out.println(test.top());
}
}
昨天跟人吹牛，导致今天早上连简单题都做不出来了。
不是做不出来，而是脑子用不动了。感觉昨天用脑过度了。然后又没睡好。
这道题目有个注意点是我没考虑到的，虽然是简单题。
ArrayList<Integer> t = new ArrayList<Integer>(10);
那么， t.size() 等于多少？
我误认为了10
其实不是，还是0.
ArrayList 之前总结过。
这个10，表示申请了一个Object[]数组，长度为10.
但是，不代表 arraylist size = 10.
size 仍然是0.
他和object数组长度是无关的，他等于，object 数组中有效元素的个数。
刚开始初始化的时候，数组里面都是null，所以size = 0
**
总结： ArrayList size 的具体意义
**
Anyway, Good luck, Richardo!
My code:
class MyStack {
private Queue<Integer> q = new LinkedList<Integer>();
// Push element x onto stack.
public void push(int x) {
q.offer(x);
int size = q.size();
while (size > 1) {
q.offer(q.remove());
size--;
}
}
// Removes the element on top of the stack.
public void pop() {
q.poll();
}
// Get the top element.
public int top() {
return q.peek();
}
// Return whether the stack is empty.
public boolean empty() {
return q.isEmpty();
}
}
我以为有更好的方法，没想到还是如此：
push O(n)
pop O(1)
然后可以用Queue来完成。
reference：
https://leetcode.com/articles/implement-stack-using-queues/#approach-1-two-queues-push-o1-pop-on
还有种O(1)的方法，太偏门了。
https://discuss.leetcode.com/topic/15961/o-1-purely-with-queues
Anyway, Good luck, Richardo! -- 09/11/2016
