※ 引述《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)

大師

大師