資訊專(zhuān)欄INFORMATION COLUMN
摘要：下面是入棧時(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() -- 返回棧是否為空
Implement the following operations of a stack using queues.
push(x) -- Push element x onto stack.
pop() -- Removes the element on top of the stack.
top() -- Get the top element.
empty() -- Return whether the stack is empty.
示例:
MyStack stack = new MyStack(); stack.push(1); stack.push(2); stack.top(); // 返回 2 stack.pop(); // 返回 2 stack.empty(); // 返回 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ì)列操作即可。
你可以假設(shè)所有操作都是有效的（例如, 對(duì)一個(gè)空的棧不會(huì)調(diào)用 pop 或者 top 操作）
Notes:
You must use only standard operations of a queue -- which means only push to back, peek/pop from front, size, and is empty operations are valid.
Depending on your language, queue may not be supported natively. You may simulate a queue by using a list or deque (double-ended queue), as long as you use only standard operations of a queue.
You may assume that all operations are valid (for example, no pop or top operations will be called on an empty stack).
解題思路：方法一（兩個(gè)隊(duì)列）：
? 隊(duì)列先進(jìn)后出，棧后進(jìn)先出。用隊(duì)列實(shí)現(xiàn)棧，可以用兩個(gè)隊(duì)列完成題解：
? 出入棧：
? 入棧時(shí)用 queue1 來(lái)存入節(jié)點(diǎn)；出棧時(shí)queue1 內(nèi)節(jié)點(diǎn)順序出隊(duì)列并入隊(duì)列到 queue2，直到queue1剩最后一個(gè)元素時(shí)即為棧頂元素，彈出即可；
? 取棧頂元素：
? 用一個(gè) top 指針一直指向棧頂元素，top() 方法查詢(xún)棧頂元素時(shí)直接返回 top 指針即可。
方法二（一個(gè)隊(duì)列）：
? 只用一個(gè)隊(duì)列，只需要在入棧時(shí)反轉(zhuǎn)隊(duì)列即可：
入棧存入到隊(duì)列queue 節(jié)點(diǎn)1入棧：queue：1 反轉(zhuǎn)隊(duì)列0次：queue：1 節(jié)點(diǎn)2入棧queue：1->2 反轉(zhuǎn)隊(duì)列1次： queue：1->2 --> queue：2->1 節(jié)點(diǎn)2入棧queue：2->1->3 反轉(zhuǎn)隊(duì)列2次： queue：2->1->3 ---> queue：1->3->2 ---> queue：3->2->1 ......
這樣不管什么時(shí)候出隊(duì)順序都是按照出棧的順序。
Java：方法一
class MyStack {
Queue queue1;
Queue queue2;
private int top;//指向棧頂元素
public MyStack() {
queue1 = new LinkedList<>();
queue2 = new LinkedList<>();
}
public void push(int x) {
queue1.offer(x);
top = x;//新加入元素為棧頂元素
}
public int pop() {
while (queue1.size() > 1) {//條件為隊(duì)列1的元素個(gè)數(shù)大于一
top = queue1.poll();//用top暫存元素，當(dāng)循環(huán)結(jié)束時(shí)，top剛好是棧頂元素
queue2.add(top);
}
//隊(duì)列1與隊(duì)列2交換
Queue tmp = queue2;
queue2 = queue1;
queue1 = tmp;
return queue2.poll();//返回隊(duì)列2的隊(duì)列頭元素，隊(duì)列2也只有一個(gè)元素
}
public int top() {
return top;
}
public boolean empty() {
return queue1.isEmpty();//隊(duì)列1決定了棧是否為空
}
}
方法二：
每次入隊(duì)時(shí)反轉(zhuǎn)隊(duì)列即可，只有入棧需要特殊操作，出棧、取棧頂元素、是否空都按照隊(duì)列正常出隊(duì)列、取隊(duì)列頭元素、是否空方法操作。下面是入棧時(shí)代碼：
QueuePython：queue = new LinkedList<>(); public void push(int x) { queue.add(x); int sz = queue.size();//獲得隊(duì)列長(zhǎng)度 while (sz > 1) {//反轉(zhuǎn)次數(shù)為隊(duì)列長(zhǎng)度減一 queue.add(queue.remove());//反轉(zhuǎn) sz--; } }
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 MyStack:
def __init__(self):
self.stack = []
def push(self, x: int) -> None:
self.stack.append(x)
def pop(self) -> int:
return self.stack.pop(-1)
def top(self) -> int:
return self.stack[-1]
def empty(self) -> bool:
return not self.stack
歡迎關(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://m.hztianpu.com/yun/76084.html
摘要：題目要求使用隊(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...
摘要：雙隊(duì)列法復(fù)雜度時(shí)間空間思路和類(lèi)似，我們也可以用兩個(gè)隊(duì)列來(lái)模擬棧的操作。當(dāng)時(shí)，我們將數(shù)字進(jìn)非空的隊(duì)列就行了。操作和一樣，區(qū)別在于我們拿到最后一個(gè)數(shù)后，還要再把它進(jìn)另一個(gè)隊(duì)列中。 雙隊(duì)列法 復(fù)雜度 時(shí)間 O(N) 空間 O(N) 思路 和Implement Queue using Stack類(lèi)似，我們也可以用兩個(gè)隊(duì)列來(lái)模擬棧的操作。當(dāng)push時(shí)，我們將數(shù)字offer進(jìn)非空的隊(duì)列就行了。當(dāng)p...
摘要：月下半旬攻略道題，目前已攻略題。目前簡(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ū)別...
摘要：微信公眾號(hào)記錄截圖記錄截圖目前關(guān)于這塊算法與數(shù)據(jù)結(jié)構(gòu)的安排前。已攻略返回目錄目前已攻略篇文章。會(huì)根據(jù)題解以及留言?xún)?nèi)容，進(jìn)行補(bǔ)充，并添加上提供題解的小伙伴的昵稱(chēng)和地址。本許可協(xié)議授權(quán)之外的使用權(quán)限可以從處獲得。 Create by jsliang on 2019-07-15 11:54:45 Recently revised in 2019-07-15 15:25:25 一 目錄 不...
摘要：在線網(wǎng)站地址我的微信公眾號(hào)完整題目列表從年月日起，每天更新一題，順序從易到難，目前已更新個(gè)題。這是項(xiàng)目地址歡迎一起交流學(xué)習(xí)。 這篇文章記錄我練習(xí)的 LeetCode 題目，語(yǔ)言 JavaScript。 在線網(wǎng)站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公眾號(hào)： showImg(htt...
閱讀 3385·2023-04-26 02:42
閱讀 866·2021-10-09 09:41
閱讀 3494·2021-09-06 15:02
閱讀 811·2019-08-26 10:45
閱讀 549·2019-08-23 15:53
閱讀 816·2019-08-22 18:10
閱讀 618·2019-08-22 18:01
閱讀 3582·2019-08-22 17:34
