題目
難度：★★☆☆☆
類型：隊列，棧
使用棧實現(xiàn)隊列的下列操作：
push(x) -- 將一個元素放入隊列的尾部。
pop() -- 從隊列首部移除元素。
peek() -- 返回隊列首部的元素。
empty() -- 返回隊列是否為空。
示例
MyQueue queue = new MyQueue();
queue.push(1);
queue.push(2);
queue.peek(); // 返回 1
queue.pop(); // 返回 1
queue.empty(); // 返回 false
說明:
你只能使用標(biāo)準(zhǔn)的棧操作 -- 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
你所使用的語言也許不支持棧。你可以使用 list 或者 deque（雙端隊列）來模擬一個棧，只要是標(biāo)準(zhǔn)的棧操作即可。
假設(shè)所有操作都是有效的 （例如，一個空的隊列不會調(diào)用 pop 或者 peek 操作）。
解答
- push()：元素入棧成為棧頂，沒有返回值；
- pop()：棧頂元素出棧，返回值為出棧元素；
- length：獲得當(dāng)前棧的長度；
- is_empty：獲得當(dāng)前棧是否為空，如果為空返回True。
首先，我們實例化一個基本棧stack1和一個輔助棧stack2，每次操作后，基本棧中的元素就是隊列中的元素，輔助棧用于暫存基本棧中的元素。隊列的每一個方法這樣實現(xiàn)：
- push()：元素入隊，直接在基本棧stack1中加入元素即可；
- pop()：隊頭元素出隊，將基本棧stack1中的每次元素出隊并依次加入輔助棧stack2中，當(dāng)只剩下一個元素res時，把這個元素拿出來，不加入stack2，然后把輔助棧stack2中的所有元素依次返還基本棧stack1，并返回之前被拿出來的元素res即可。
- top()：獲取隊頭元素，實現(xiàn)方法與pop十分相似，唯一只是res會被再加入到stack2中；
- empty()：判斷隊列是否為空，隊列的狀態(tài)與基本棧queue1完全一致，因此直接返回queue1的is_empty方法即可。
class Stack(object):
def __init__(self):
self.stack = []
def push(self, x): # 入棧
self.stack.append(x)
def pop(self): # 出棧
if self.is_empty: # 注意特殊情況
return None
return self.stack.pop()
@property
def length(self): # 獲取棧中元素
return len(self.stack)
@property
def is_empty(self): # 獲取棧的狀態(tài)：是否為空
return self.length == 0
class MyQueue(object):
def __init__(self):
"""
Initialize your data structure here.
"""
self.stack1 = Stack() # 基本棧
self.stack2 = Stack() # 輔助棧
def push(self, x):
"""
Push element x to the back of queue.
:type x: int
:rtype: None
"""
self.stack1.push(x) # 入棧，即入隊列
def pop(self):
"""
Removes the element from in front of queue and returns that element.
:rtype: int
"""
while self.stack1.length > 1: # 卡住要出棧的最后一個元素
self.stack2.push(self.stack1.pop()) # 其他元素倒進(jìn)輔助棧
res = self.stack1.pop() # 那個被卡住的元素就是所需
while not self.stack2.is_empty: # 只要輔助棧不為空
self.stack1.push(self.stack2.pop()) # 輔助棧中的元素倒回基本棧
return res # 返回棧底元素即為出隊隊頭
def peek(self):
"""
Get the front element.
:rtype: int
"""
while self.stack1.length > 1: # 卡住要出棧的最后一個元素
self.stack2.push(self.stack1.pop()) # 其他元素倒進(jìn)輔助棧
res = self.stack1.pop() # 那個被卡住的元素就是所需
self.stack2.push(res) # 記得把被卡住的元素放回
while self.stack2.length > 0: # 只要輔助棧不為空
self.stack1.push(self.stack2.pop()) # 輔助棧中的元素倒回基本棧
return res # 返回棧底元素即為出隊隊頭
def empty(self):
"""
Returns whether the queue is empty.
:rtype: bool
"""
return self.stack1.is_empty # 隊列的狀態(tài)即為基本棧的狀態(tài)
如有疑問或建議，歡迎評論區(qū)留言~
