資訊專(zhuān)欄INFORMATION COLUMN
摘要：題目使用棧實(shí)現(xiàn)隊(duì)列的下列操作將一個(gè)元素放入隊(duì)列的尾部。用棧實(shí)現(xiàn)隊(duì)列，可以用兩個(gè)棧完成題解。入隊(duì)列時(shí)用存入節(jié)點(diǎn)，出隊(duì)列時(shí)內(nèi)節(jié)點(diǎn)順序出棧壓入中。這類(lèi)編程語(yǔ)言就壓根不需要用隊(duì)列實(shí)現(xiàn)?；蛴脳?shí)現(xiàn)隊(duì)列這種問(wèn)題，因?yàn)闂：完?duì)列本身就必須借助實(shí)現(xiàn)。
題目：
使用棧實(shí)現(xiàn)隊(duì)列的下列操作：
push(x) -- 將一個(gè)元素放入隊(duì)列的尾部。
pop() -- 從隊(duì)列首部移除元素。
peek() -- 返回隊(duì)列首部的元素。
empty() -- 返回隊(duì)列是否為空。
Implement the following operations of a queue using stacks.
push(x) -- Push element x to the back of queue.
pop() -- Removes the element from in front of queue.
peek() -- Get the front element.
empty() -- Return whether the queue is empty.
示例:
MyQueue queue = new MyQueue(); queue.push(1); queue.push(2); queue.peek(); // 返回 1 queue.pop(); // 返回 1 queue.empty(); // 返回 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)的棧操作即可。
假設(shè)所有操作都是有效的 （例如，一個(gè)空的隊(duì)列不會(huì)調(diào)用 pop 或者 peek 操作）。
Notes:
You must use only standard operations of a stack -- which means only push to top, peek/pop from top, size, and is empty operations are valid.
Depending on your language, stack may not be supported natively. You may simulate a stack by using a list or deque (double-ended queue), as long as you use only standard operations of a stack.
You may assume that all operations are valid (for example, no pop or peek operations will be called on an empty queue).
解題思路：隊(duì)列先進(jìn)后出，棧后進(jìn)先出。用棧實(shí)現(xiàn)隊(duì)列，可以用兩個(gè)棧完成題解。入隊(duì)列時(shí)用 stack1 存入節(jié)點(diǎn)，出隊(duì)列時(shí) stack1 內(nèi)節(jié)點(diǎn)順序出棧壓入 stack2 中。
例如 1, 2, 3 元素順序入隊(duì)列 即存入棧stack1：[1, 2, 3] 出隊(duì)列時(shí)順序應(yīng)為：1->2->3 但是棧先進(jìn)先出，出棧順序?yàn)椋?->2->1 與出隊(duì)列順序不相符 借助另一個(gè)棧stack2 stack1內(nèi)的元素順序出棧并壓入stack2 stack1：[1, 2, 3] ---> stack2：[3, 2, 1] 此時(shí)stack2出棧順序：1->2->3 與出隊(duì)列順序相符
注意：在出隊(duì)列時(shí)無(wú)需著急將 stack1 中的節(jié)點(diǎn)順序壓入 stack2。因?yàn)橐獙?shí)現(xiàn)的隊(duì)列是先進(jìn)后出，可以將 stack2 中的節(jié)點(diǎn)全部彈出之后 再將 stack1 內(nèi)節(jié)點(diǎn)順序壓入stack2，這樣可以將出棧的時(shí)間復(fù)雜度攤還到 O(1)。
Java：class MyQueue {
private Stack stack1;
private Stack stack2;
public MyQueue() {
stack1 = new Stack<>();
stack2 = new Stack<>();
}
public void push(int x) {
stack1.push(x);
}
public int pop() {
if (stack2.isEmpty()) {
while (!stack1.isEmpty()) {
stack2.push(stack1.pop());
}
}
return stack2.pop();
}
public int peek() {
//stack1節(jié)點(diǎn)順序彈出并壓入stack2
if (stack2.isEmpty()) {//條件是: stack2為空,而不是stack1非空, 這樣攤還復(fù)雜度O(1)
while (!stack1.isEmpty()) {
stack2.push(stack1.pop());//stack1彈出節(jié)點(diǎn)并壓入stack2
}
}
return stack2.peek();
}
public boolean empty() {
return stack1.isEmpty() && stack2.isEmpty();
}
}
Python：
Python語(yǔ)言沒(méi)有棧和隊(duì)列數(shù)據(jù)結(jié)構(gòu)，只能用數(shù)組 List 或雙端隊(duì)列 deque 實(shí)現(xiàn)。
這類(lèi)編程語(yǔ)言就壓根不需要 用隊(duì)列實(shí)現(xiàn)?；蛴脳?shí)現(xiàn)隊(duì)列這種問(wèn)題，因?yàn)闂：完?duì)列本身就必須借助List、deque實(shí)現(xiàn)。
所以這道題在這種語(yǔ)言中這就非常簡(jiǎn)單了，可以說(shuō)是作弊。
class MyQueue:
def __init__(self):
self.queue = []
def push(self, x: int) -> None:
self.queue.append(x)
def pop(self) -> int:
#彈出第一個(gè)元素
return self.queue.pop(0)
def peek(self) -> int:
#返回第一個(gè)元素
return self.queue[0]
def empty(self) -> bool:
return not self.queue
歡迎關(guān)注微.信公.眾號(hào)：愛(ài)寫(xiě)B(tài)ug
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/76013.html
摘要：注意的方法是和，實(shí)際上我們應(yīng)該實(shí)現(xiàn)的是和或者和，的實(shí)現(xiàn)和是一樣的，但將改為時(shí)，我們要先把到的元素保存，然后再?gòu)棾鲚敵鰲?，然后返回這個(gè)保存的元素。 Implement Queue using Stacks Implement the following operations of a queue using stacks. push(x) -- Push element x to th...
摘要：題目要求通過(guò)隊(duì)列實(shí)現(xiàn)一個(gè)棧的功能。棧的為壓入棧頂，出棧，棧頂元素，棧是否為空。重復(fù)上述的操作。但是當(dāng)需要彈出元素時(shí)，則從桶彈出。這樣，下次加入的元素必然全部位于桶后的所有元素，而桶中的元素也能保證位輸入順序。極大的減少了不必要的入棧出棧。 題目要求 Implement the following operations of a queue using stacks. push(x) ...
摘要：在線(xiàn)網(wǎng)站地址我的微信公眾號(hào)完整題目列表從年月日起，每天更新一題，順序從易到難，目前已更新個(gè)題。這是項(xiàng)目地址歡迎一起交流學(xué)習(xí)。 這篇文章記錄我練習(xí)的 LeetCode 題目，語(yǔ)言 JavaScript。 在線(xiàn)網(wǎng)站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公眾號(hào)： showImg(htt...
摘要：月下半旬攻略道題，目前已攻略題。目前簡(jiǎn)單難度攻略已經(jīng)到題，所以后面會(huì)調(diào)整自己，在刷算法與數(shù)據(jù)結(jié)構(gòu)的同時(shí)，攻略中等難度的題目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道題，目前已攻略 100 題。 一 目錄 不折騰的前端，和咸魚(yú)有什么區(qū)別...
摘要：下面是入棧時(shí)代碼獲得隊(duì)列長(zhǎng)度反轉(zhuǎn)次數(shù)為隊(duì)列長(zhǎng)度減一反轉(zhuǎn)語(yǔ)言沒(méi)有棧和隊(duì)列數(shù)據(jù)結(jié)構(gòu)，只能用數(shù)組或雙端隊(duì)列實(shí)現(xiàn)。這類(lèi)編程語(yǔ)言就壓根不需要用隊(duì)列實(shí)現(xiàn)棧或用棧實(shí)現(xiàn)隊(duì)列這種問(wèn)題，因?yàn)闂：完?duì)列本身就必須借助實(shí)現(xiàn)。 題目： 使用隊(duì)列實(shí)現(xiàn)棧的下列操作： push(x) -- 元素 x 入棧 pop() -- 移除棧頂元素 top() -- 獲取棧頂元素 empty() -- 返回棧是否為空 Impl...
閱讀 2863·2021-11-22 11:56
閱讀 3563·2021-11-15 11:39
閱讀 908·2021-09-24 09:48
閱讀 767·2021-08-17 10:14
閱讀 1335·2019-08-30 15:55
閱讀 2762·2019-08-30 15:55
閱讀 1320·2019-08-30 15:44
閱讀 2789·2019-08-30 10:59
