#41159:


xsw20080329@gmail.com (敢不敢讓我過)

學校 : 不指定學校
編號 : 242754
來源 : [163.32.56.83]
最後登入時間 :
2024-10-28 14:31:25
c700. 壞掉的隊列(queue) | From: [163.32.56.65] | 發表日期 : 2024-07-08 11:33

用兩個 stack 模擬 queue,重點觀念是 stack 的輸出順序是反向的,但如果先把 stack 存到另一個 stack 再輸出,根據負負的正定理,新 stack 的輸出順序就會變成正常的,如以下範例

  1. 輸入 = 1 2 3 4 5
  2. 依序 push 進 stack1
  3. stack1 = 1 2 3 4 5
  4. 再將 stack1 依序 pop 出並 push 進 stack2
  5. stack2 = 5 4 3 2 1
  6. 最後將 stack2 依序 pop 輸出
  7. 輸出 = 1 2 3 4 5

也就是說實作時

  • 指令為 push 時,將輸入的東西都存進 stack1,
  • 指令為 pop 時,看 stack2 還有沒有剩餘的元素,有就 pop 出該元素,否則將 stack1 依序 pop 到 stack2
  • 由於本題並不需要輸出任何有關輸入的的元素,所以可以無視它用兩個 int 模擬 stack 的長度來做就行了。
 
ZeroJudge Forum