資訊專欄INFORMATION COLUMN
摘要：注意的方法是和，實(shí)際上我們應(yīng)該實(shí)現(xiàn)的是和或者和，的實(shí)現(xiàn)和是一樣的，但將改為時(shí)，我們要先把到的元素保存，然后再?gòu)棾鲚敵鰲?，然后返回這個(gè)保存的元素。
Implement Queue using Stacks
雙棧法 復(fù)雜度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.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).
時(shí)間 入隊(duì)O(1) 出隊(duì)O(N) 空間 O(N)
思路隊(duì)列和棧都是順序插入的，區(qū)別在于隊(duì)列的出口方向和棧的出口方向是相反的，利用這個(gè)性質(zhì)，如果我們將元素按照順序插入棧后，再一個(gè)個(gè)彈出并反向插入另一個(gè)棧，那么這第二個(gè)棧的出口順序就和隊(duì)列是一樣的了。所以我們構(gòu)造兩個(gè)棧，所有新加的元素都加入輸入棧，一旦要出隊(duì)列時(shí)，我們便將輸入棧的元素都反向加入輸出棧，再輸出。需要注意的是，如果輸出棧不為空時(shí)，說(shuō)明當(dāng)前要輸出的元素還在輸出棧中，所以我們就暫時(shí)不用將輸入棧的元素加入輸出棧（而且加入后也會(huì)導(dǎo)致順序錯(cuò)誤）。
注意Leetcode的方法是pop和push，實(shí)際上我們應(yīng)該實(shí)現(xiàn)的是poll和offer（或者enqueue和dequeue），offer的實(shí)現(xiàn)和push是一樣的，但將pop改為poll時(shí)，我們要先把peek到的元素保存，然后再?gòu)棾鲚敵鰲?，然后返回這個(gè)保存的元素。
代碼class MyQueue {
Stack input = new Stack();
Stack output = new Stack();
// Push element x to the back of queue.
public void push(int x) {
input.push(x);
}
// Removes the element from in front of queue.
public void pop() {
int x = peek();
output.pop();
}
// Get the front element.
public int peek() {
if(output.isEmpty()){
while(!input.isEmpty()){
output.push(input.pop());
}
}
return output.peek();
}
// Return whether the queue is empty.
public boolean empty() {
return input.isEmpty() && output.isEmpty();
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/64510.html
摘要：題目使用棧實(shí)現(xiàn)隊(duì)列的下列操作將一個(gè)元素放入隊(duì)列的尾部。用棧實(shí)現(xiàn)隊(duì)列，可以用兩個(gè)棧完成題解。入隊(duì)列時(shí)用存入節(jié)點(diǎn)，出隊(duì)列時(shí)內(nèi)節(jié)點(diǎn)順序出棧壓入中。這類編程語(yǔ)言就壓根不需要用隊(duì)列實(shí)現(xiàn)?；蛴脳?shí)現(xiàn)隊(duì)列這種問題，因?yàn)闂：完?duì)列本身就必須借助實(shí)現(xiàn)。 題目： 使用棧實(shí)現(xiàn)隊(duì)列的下列操作： push(x) -- 將一個(gè)元素放入隊(duì)列的尾部。 pop() -- 從隊(duì)列首部移除元素。 peek() -- 返回隊(duì)...
摘要：題目要求通過(guò)隊(duì)列實(shí)現(xiàn)一個(gè)棧的功能。棧的為壓入棧頂，出棧，棧頂元素，棧是否為空。重復(fù)上述的操作。但是當(dāng)需要彈出元素時(shí)，則從桶彈出。這樣，下次加入的元素必然全部位于桶后的所有元素，而桶中的元素也能保證位輸入順序。極大的減少了不必要的入棧出棧。 題目要求 Implement the following operations of a queue using stacks. push(x) ...
摘要：下面是入棧時(shí)代碼獲得隊(duì)列長(zhǎng)度反轉(zhuǎn)次數(shù)為隊(duì)列長(zhǎng)度減一反轉(zhuǎn)語(yǔ)言沒有棧和隊(duì)列數(shù)據(jù)結(jié)構(gòu)，只能用數(shù)組或雙端隊(duì)列實(shí)現(xiàn)。這類編程語(yǔ)言就壓根不需要用隊(duì)列實(shí)現(xiàn)?；蛴脳?shí)現(xiàn)隊(duì)列這種問題，因?yàn)闂：完?duì)列本身就必須借助實(shí)現(xiàn)。 題目： 使用隊(duì)列實(shí)現(xiàn)棧的下列操作： push(x) -- 元素 x 入棧 pop() -- 移除棧頂元素 top() -- 獲取棧頂元素 empty() -- 返回棧是否為空 Impl...
摘要：題目要求使用隊(duì)列來(lái)模擬實(shí)現(xiàn)一個(gè)棧。棧是指先進(jìn)后出的數(shù)據(jù)結(jié)構(gòu)，而隊(duì)列則是先進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)。隊(duì)列的包括在隊(duì)列尾插入數(shù)據(jù)，輸出隊(duì)列頭的數(shù)據(jù)，查看隊(duì)列的長(zhǎng)度，隊(duì)列是否為空。 題目要求 Implement the following operations of a queue using stacks. push(x) -- Push element x to the back of que...
摘要：月下半旬攻略道題，目前已攻略題。目前簡(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 題。 一 目錄 不折騰的前端，和咸魚有什么區(qū)別...
閱讀 1933·2021-11-24 09:39
閱讀 2650·2021-10-14 09:43
閱讀 3364·2021-10-08 10:10
閱讀 2372·2021-09-22 15:54
閱讀 2380·2019-08-29 17:20
閱讀 1601·2019-08-28 18:14
閱讀 2403·2019-08-26 13:28
閱讀 1146·2019-08-26 12:16
