題目簡(jiǎn)介
232.用棧實(shí)現(xiàn)隊(duì)列 https://leetcode.cn/problems/implement-queue-using-stacks/
請(qǐng)你僅使用兩個(gè)棧實(shí)現(xiàn)先入先出隊(duì)列朗伶。隊(duì)列應(yīng)當(dāng)支持一般隊(duì)列支持的所有操作（push尤泽、pop猫妙、peek赋咽、empty）：
實(shí)現(xiàn) MyQueue 類：
void push(int x) 將元素 x 推到隊(duì)列的末尾
int pop() 從隊(duì)列的開(kāi)頭移除并返回元素
int peek() 返回隊(duì)列開(kāi)頭的元素
boolean empty() 如果隊(duì)列為空绎狭，返回 true 院尔；否則凳鬓，返回 false
說(shuō)明：
你只能使用標(biāo)準(zhǔn)的棧操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的影钉。
你所使用的語(yǔ)言也許不支持棧。你可以使用 list 或者 deque（雙端隊(duì)列）來(lái)模擬一個(gè)棧录粱，只要是標(biāo)準(zhǔn)的棧操作即可腻格。
225. 用隊(duì)列實(shí)現(xiàn)棧 https://leetcode.cn/problems/implement-stack-using-queues/
請(qǐng)你僅使用兩個(gè)隊(duì)列實(shí)現(xiàn)一個(gè)后入先出（LIFO）的棧，并支持普通棧的全部四種操作（push啥繁、top菜职、pop 和 empty）。
實(shí)現(xiàn) MyStack 類：
void push(int x) 將元素 x 壓入棧頂旗闽。
int pop() 移除并返回棧頂元素酬核。
int top() 返回棧頂元素。
boolean empty() 如果棧是空的适室，返回 true 嫡意；否則，返回 false 捣辆。
注意：
你只能使用隊(duì)列的基本操作 —— 也就是 push to back蔬螟、peek/pop from front、size 和 is empty 這些操作汽畴。
你所使用的語(yǔ)言也許不支持隊(duì)列旧巾。 你可以使用 list （列表）或者 deque（雙端隊(duì)列）來(lái)模擬一個(gè)隊(duì)列 , 只要是標(biāo)準(zhǔn)的隊(duì)列操作即可。
初見(jiàn)思路
- 老朋友了整袁，主要兩點(diǎn)思路：兩個(gè)棧一個(gè)出一個(gè)入菠齿；負(fù)責(zé)出的棧為空的時(shí)候把負(fù)責(zé)入的棧全量倒入
class MyQueue:
def __init__(self):
self.stack_in = list()
self.stack_out = list()
def push(self, x: int) -> None:
self.stack_in.append(x)
def pop(self) -> int:
if not self.stack_out:
self.move_elems()
head_elem = self.stack_out[-1]
self.stack_out.pop(-1)
return head_elem
def peek(self) -> int:
if not self.stack_out:
self.move_elems()
return self.stack_out[-1]
def empty(self) -> bool:
return len(self.stack_in)==0 and len(self.stack_out)==0
def move_elems(self) -> None:
while self.stack_in:
self.stack_out.append(self.stack_in[-1])
self.stack_in.pop(-1)
- 說(shuō)實(shí)話Python的deque很強(qiáng)，寫這種題目很難學(xué)到啥有用的東西
from collections import deque
class MyStack:
def __init__(self):
self.q_1 = deque()
def push(self, x: int) -> None:
self.q_1.append(x)
def pop(self) -> int:
return self.q_1.pop()
def top(self) -> int:
return self.q_1[-1]
def empty(self) -> bool:
return not self.q_1
復(fù)盤思路
對(duì)于225坐昙，假設(shè)我們不能使用雙端隊(duì)列的pop()方法, 我們就是一個(gè)普通的隊(duì)列绳匀，只能左邊彈出首元素:
from collections import deque
class MyStack:
def __init__(self):
self.queue_in = deque()
self.queue_out = deque()
def push(self, x: int) -> None:
self.queue_in.append(x)
def pop(self) -> int:
if self.empty():
return None
self.move_elems()
self.queue_in, self.queue_out = self.queue_out, self.queue_in # 核心在這
return self.queue_out.popleft()
def top(self) -> int:
if self.empty():
return None
self.move_elems()
self.queue_in, self.queue_out = self.queue_out, self.queue_in
temp = self.queue_out.popleft() # 假設(shè)不能獲取，我們備份
self.queue_in.append(temp) # 放到尾部
return temp
def empty(self) -> bool:
return len(self.queue_in) == 0 # not self.queue_in
def move_elems(self) -> None:
for i in range(len(self.queue_in) - 1):
self.queue_out.append(self.queue_in.popleft())
重點(diǎn)難點(diǎn)
https://programmercarl.com/0232.%E7%94%A8%E6%A0%88%E5%AE%9E%E7%8E%B0%E9%98%9F%E5%88%97.html
https://programmercarl.com/0232.%E7%94%A8%E6%A0%88%E5%AE%9E%E7%8E%B0%E9%98%9F%E5%88%97.html
今日收獲
- 棧和隊(duì)列的基本操作
