Python中如何用棧實(shí)現(xiàn)隊(duì)列，很多新手對此不是很清楚，為了幫助大家解決這個難題，下面小編將為大家詳細(xì)講解，有這方面需求的人可以來學(xué)習(xí)下，希望你能有所收獲。

公司主營業(yè)務(wù)：成都做網(wǎng)站、網(wǎng)站建設(shè)、外貿(mào)營銷網(wǎng)站建設(shè)、移動網(wǎng)站開發(fā)等業(yè)務(wù)。幫助企業(yè)客戶真正實(shí)現(xiàn)互聯(lián)網(wǎng)宣傳，提高企業(yè)的競爭能力。創(chuàng)新互聯(lián)建站是一支青春激揚(yáng)、勤奮敬業(yè)、活力青春激揚(yáng)、勤奮敬業(yè)、活力澎湃、和諧高效的團(tuán)隊(duì)。公司秉承以“開放、自由、嚴(yán)謹(jǐn)、自律”為核心的企業(yè)文化，感謝他們對我們的高要求，感謝他們從不同領(lǐng)域給我們帶來的挑戰(zhàn)，讓我們激情的團(tuán)隊(duì)有機(jī)會用頭腦與智慧不斷的給客戶帶來驚喜。創(chuàng)新互聯(lián)建站推出穆棱免費(fèi)做網(wǎng)站回饋大家。

用棧實(shí)現(xiàn)隊(duì)列

題目：

使用棧實(shí)現(xiàn)隊(duì)列的下列操作：

• push(x) – 將一個元素放入隊(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

說明:

• 你只能使用標(biāo)準(zhǔn)的棧操作 – 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。

• 你所使用的語言也許不支持棧。你可以使用 list 或者 deque（雙端隊(duì)列）來模擬一個棧，只要是標(biāo)準(zhǔn)的棧操作即可。

• 假設(shè)所有操作都是有效的 （例如，一個空的隊(duì)列不會調(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ì)列，可以用兩個棧完成題解。入隊(duì)列時用 stack1 存入節(jié)點(diǎn)，出隊(duì)列時 stack1 內(nèi)節(jié)點(diǎn)順序出棧壓入 stack2 中。

例如 1, 2, 3 元素順序入隊(duì)列 
即存入棧stack1：[1, 2, 3]
出隊(duì)列時順序應(yīng)為：1->2->3
但是棧先進(jìn)先出，出棧順序?yàn)椋?->2->1
與出隊(duì)列順序不相符
借助另一個棧stack2
stack1內(nèi)的元素順序出棧并壓入stack2
stack1：[1, 2, 3] ---> stack2：[3, 2, 1]
此時stack2出棧順序：1->2->3
與出隊(duì)列順序相符

【注意】：在出隊(duì)列時無需著急將 stack1 中的節(jié)點(diǎn)順序壓入 stack2。因?yàn)橐獙?shí)現(xiàn)的隊(duì)列是先進(jìn)后出，可以將 stack2 中的節(jié)點(diǎn)全部彈出之后 再將 stack1 內(nèi)節(jié)點(diǎn)順序壓入stack2，這樣可以將出棧的時間復(fù)雜度攤還到 O(1)。

Java：

class MyQueue {
 private Stack<Integer> stack1;
 private Stack<Integer> 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語言沒有棧和隊(duì)列數(shù)據(jù)結(jié)構(gòu)，只能用數(shù)組 List 或雙端隊(duì)列 deque 實(shí)現(xiàn)。

這類編程語言就壓根不需要 用隊(duì)列實(shí)現(xiàn)?；蛴脳?shí)現(xiàn)隊(duì)列這種問題，因?yàn)闂：完?duì)列本身就必須借助List、deque實(shí)現(xiàn)。

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

class MyQueue:
 def __init__(self):
 self.queue = []
 def push(self, x: int) -> None:
 self.queue.append(x)
 def pop(self) -> int:
 #彈出第一個元素
 return self.queue.pop(0)
 def peek(self) -> int:
 #返回第一個元素
 return self.queue[0]
 def empty(self) -> bool:
 return not self.queue

看完上述內(nèi)容是否對您有幫助呢？如果還想對相關(guān)知識有進(jìn)一步的了解或閱讀更多相關(guān)文章，請關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道，感謝您對創(chuàng)新互聯(lián)的支持。

分享標(biāo)題：Python中如何用棧實(shí)現(xiàn)隊(duì)列
當(dāng)前鏈接：http://chinadenli.net/article2/gjcgic.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供移動網(wǎng)站建設(shè)、網(wǎng)站營銷、靜態(tài)網(wǎng)站、網(wǎng)站設(shè)計(jì)、響應(yīng)式網(wǎng)站、微信公眾號

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)