→ MurasakiSion: 大師 12/16 09:51
推 Rushia: 大師 12/16 09:56
推 NTHUlagka: 好強 12/16 12:29
※ 引述《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)
--
蛤?
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.251.237.225 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1671155439.A.718.html