推 JIWP: 大師 01/29 14:06
→ Rushia: 你這不是用stack吧 比較像dequeue的api 01/29 14:09
→ JerryChungYC: 窩不知道 :( 所以應該是要用s1 s2那個做法嗎 01/29 14:13
→ Rushia: 對阿 stack只能從頂端放元素 不能像你這樣從底部pop 01/29 14:13
https://leetcode.com/problems/implement-queue-using-stacks
232. Implement Queue using Stacks
利用 2 個堆疊 (stacks) 實作先進先出 (FIFO)
實作 class MyQueue
void push(int x): 將 x 放到佇列末端
int pop(): 移除最前面的元素並 return 該元素
int peek(): Return 最前面的元素
boolean empty(): 佇列為空時 Return True 反之 False
Example 1:
Input
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
Output
[null, null, null, 1, 1, false]
Explanation
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (左方是佇列前面)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false
條件:
1 <= x <= 9
push, pop, peek, empty 最多呼叫 100 次
所有的 pop, peek 都是有效的
Python3 code:
---------------------------------------------
class MyQueue:
def __init__(self):
self.s1 = []
def push(self, x: int) -> None:
self.s1.append(x)
def pop(self) -> int:
return self.s1.pop(0)
def peek(self) -> int:
return self.s1[0]
def empty(self) -> bool:
return not self.s1
----------------------------------------------
用pop(0)好像是O(n) 看其他人做法是再用一個s2
每次push先把s1全部pop()到s2， push(x)後再全pop()回來 然後peek改成[-1]
可能是這題太簡單的關係 結果沒什麼差異
話說程式碼要分享的話推薦丟哪啊 之前提到的自動把程式載到電腦裡的
其他語言應該也能做 不過目前只做python3就是了
https://i.imgur.com/Knc8t7L.png
主要會用到大概就 t 跟 s 吧
c 是在 s 之前做的 不過能直接搜尋題目後就用不太到了
目前用 a 逐題看有沒有漏的 不過也只看到30題就是了
有對TreeNode跟ListNode另做一個py檔來import
目錄結構
leetcode/
│ 232.html
│ 232.py
│ problem.py
│ ListNode.py
│ TreeNode.py
└── all/
│ 1.py
│ ListNode.py
│ TreeNode.py
會在all也放兩個py檔是因為不知道為什麼無法import上層的
用 from ..ListNode import ListNode, list_to_LL
vscode不會畫線 但執行就會報錯
https://i.imgur.com/GgOfPIV.png
其實這些型別平常根本不會寫就是了
找到能上傳的地方再傳 還是直接丟github
像這是今天的
https://i.imgur.com/CQqg0pJ.png
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 125.227.251.109 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1706508246.A.174.html