※ 引述《Rushia (みけねこ的鼻屎)》之铭言：
: 思路：
: 1.就...资料结构课本里面的东西，利用一个stack暂存顶层元素，拿到底层元素
: 之后再把剩余元素放回原stack即可。
: public int pop() {
: int n = s1.size();
: for (int i = 0; i < n - 1; i++) {
: s2.push(s1.pop());
: }
: int x = s1.pop();
: for (int i = 0; i < n - 1; i++) {
: s1.push(s2.pop());
: }
: return x;
: }
: public int peek() {
: int n = s1.size();
: for (int i = 0; i < n; i++) {
: s2.push(s1.pop());
: }
: int x = s2.peek();
: for (int i = 0; i < n; i++) {
: s1.push(s2.pop());
: }
: return x;
: }
从 s1 转去 s2 的时机应该只需要在 s2 是空的时候就好
因为 s2 里存的元素顺序已经反转过一次了 可以直接操作
例如现在 queue = [a,b,c,d], s1 = [a,b,c,d], s2 = []
把 s1 转去 s2 后 s1 = [], s2 = [d,c,b,a]
之后只要 s2 还有东西， queue.popleft() 就会等同于 s2.pop()
同理 queue.peek() 等于 s2[-1]
这样就不用每次都完整从 s1 转到 s2 再转回来
复杂度会是 amortized O(1)

大师

大师