接著上一期跟大家說的用棧實現隊列，這期的

Python學習教程

跟大家講

用隊列實現棧

題目：

使用隊列實現棧的下列操作：

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

注意:

你只能使用隊列的基本操作-- 也就是 push to back, peek/pop from front, size, 和 is empty 這些操作是合法的。

你所使用的語言也許不支持隊列。 你可以使用 list 或者 deque(雙端隊列)來模擬一個隊列 , 只要是標準的隊列操作即可。

你可以假設所有操作都是有效的(例如, 對一個空的棧不會調用 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).

解題思路：

方法一(兩個隊列)：

隊列先進后出，棧后進先出。用隊列實現棧，可以用兩個隊列完成題解：入棧時用 queue1 來存入節點；出棧時queue1 內節點順序出隊列并入隊列到 queue2，直到queue1剩最后一個元素時即為棧頂元素，彈出即可；用一個 top 指針一直指向棧頂元素，top() 方法查詢棧頂元素時直接返回 top 指針即可。

方法二(一個隊列)：

只用一個隊列，只需要在入棧時反轉隊列即可：

入棧存入到隊列queue

節點1入棧：queue：1

反轉隊列0次：queue：1

節點2入棧queue：1->2

反轉隊列1次：

queue：1->2?-->?queue：2->1

節點2入棧queue：2->1->3

反轉隊列2次：

queue：2->1->3?--->?queue：1->3->2?--->?queue：3->2->1

......

這樣不管什么時候出隊順序都是按照出棧的順序。

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)?{//條件為隊列1的元素個數大于一

top?=?queue1.poll();//用top暫存元素，當循環結束時，top剛好是棧頂元素

queue2.add(top);

}

//隊列1與隊列2交換

Queue?tmp?=?queue2;

queue2?=?queue1;

queue1?=?tmp;

return?queue2.poll();//返回隊列2的隊列頭元素，隊列2也只有一個元素

}

public?int?top()?{

return?top;

}

public?boolean?empty()?{

return?queue1.isEmpty();//隊列1決定了棧是否為空

}

}

方法二：

每次入隊時反轉隊列即可，只有入棧需要特殊操作，出棧、取棧頂元素、是否空都按照隊列正常出隊列、取隊列頭元素、是否空方法操作。下面是入棧時代碼：

Queue?queue?=?new?LinkedList<>();

public?void?push(int?x)?{

queue.add(x);

int?sz?=?queue.size();//獲得隊列長度

while?(sz?>?1)?{//反轉次數為隊列長度減一

queue.add(queue.remove());//反轉

sz--;

}

}

Python：

Python語言沒有棧和隊列數據結構，只能用數組 List 或雙端隊列 deque 實現。

這類編程語言就壓根不需要 用隊列實現棧或用棧實現隊列這種問題，因為棧和隊列本身就必須借助List、deque實現。

所以這道題在這種語言中這就非常簡單了，可以說是作弊。

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

更多的

Python學習教程

也會在下期繼續為大家更新！