用兩個棧實現隊列

題目：用兩個棧來實現一個隊列，完成隊列的Push和Pop操作。隊列中元素為int類型.

首先，棧都是先進后出，但是隊列呢，一般是先進先出。也就是創建兩個棧stack1和stack2，使用兩個“先進后出”的棧實現一個“先進先出”的隊列。

• 兩個棧，其實就是反轉。通過一個具體的例子分析往該隊列插入和刪除元素的過程。首先插入一個元素a，不妨先把它插入到stack1，此時stack1中的元素有{a}，stack2為空。再壓入兩個元素b和c，還是插入到stack1中，此時stack1的元素有{a,b,c}，其中c位于棧頂，而stack2仍然是空的。這個時候我們試著從隊列中刪除一個元素。按照先入先出的規則，由于a比b、c先插入隊列中，最先刪除的元素應該是a。元素a存儲在stack1中，但并不在棧頂，因此不能直接進行刪除操作。注意stack2我們一直沒有使用過，現在是讓stack2發揮作用的時候了。如果我們把stack1中的元素逐個彈出壓入stack2，元素在stack2中的順序正好和原來在stack1中的順序相反。因此經過3次彈出stack1和要入stack2操作之后，stack1為空，而stack2中的元素是{c,b,a}，這個時候就可以彈出stack2的棧頂a了。此時的stack1為空，而stack2的元素為{b,a}，其中b在棧頂。

• 思路是：當stack2中不為空時，在stack2中的棧頂元素是最先進入隊列的元素，可以彈出。如果stack2為空時，我們把stack1中的元素逐個彈出并壓入stack2。由于先進入隊列的元素被壓倒stack1的棧底，經過彈出和壓入之后就處于stack2的棧頂，有可以直接彈出。如果有新元素d插入，我們直接把它壓入stack1即可。

# -*- coding:utf-8 -*-
class Solution:#定義兩個棧def __init__(self):#這個棧壓入數據self.stack1 = []#這個棧彈出數據self.stack2 = []def push(self, node):# write code herereturn self.stack1.append(node)def pop(self):# return xx#如果棧2是空的，那就需要把棧1的元素放入棧2.如果不為空，直接彈出就行if len(self.stack2) == 0:while self.stack1:self.stack2.append(self.stack1.pop())return self.stack2.pop()
復制代碼

包含min函數的棧

題目：定義棧的數據結構，請在類型中實現一個能夠得到棧最小元素的min函數

算法：

• 棧就是數組吧，直接min

# -*- coding:utf-8 -*-
class Solution:def __init__(self):self.stack = []def push(self, node):# write code herereturn self.stack.append(node)def pop(self):# write code hereif self.stack == None:return Nonereturn self.stack.pop(-1)def top(self):# write code hereif self.stack == None:return Nonereturn self.stack[-1]def min(self):# write code herereturn min(self.stack)
復制代碼

棧的壓入、彈出序列

題目：輸入兩個整數序列，第一個序列表示棧的壓入順序，請判斷第二個序列是否為該棧的彈出順序。假設壓入棧的所有數字均不相等。例如序列1,2,3,4,5是某棧的壓入順序，序列4，5,3,2,1是該壓棧序列對應的一個彈出序列，但4,3,5,1,2就不可能是該壓棧序列的彈出序列。（注意：這兩個序列的長度是相等的）

思路：入棧的過程中允許出棧。

尊重知識產權：

CSDN---F3ver1老師 給出入棧序列，同時給出出棧序列，怎么判斷出棧序列是不是正確的

講解：給出入棧序列，同時給出出棧序列，怎么判斷出棧序列是不是正確的？

相信這道題在筆試中經常出現，那么編程如何實現，大致思路如下： 比如現在給出入棧序列，1->2->3->4->5，出棧序列2->3->5->4->1

• 我們首先拿到一個棧，按照入棧順序將第一個元素放入棧中，此時棧中有元素1，棧頂元素1
• 緊接著我們判斷此時棧頂元素是否等于出棧序列的第一個元素，1≠2，繼續入棧新的元素
• 此時2入棧，棧中有1,2，2位于棧頂，再執行和出棧序列第一個元素判斷的操作，2=2，將2出棧，此時出棧序列將2拿走，剩余3->5->4->1
• 此時3入棧，棧中有1,3，3位于棧頂，此時3與出棧序列第一個元素判斷，3=3，將3出棧，出棧序列將3拿走，剩余5->4->1
• 此時4入棧，棧中有1,4，4位于棧頂，此時4與出棧序列第一個元素判斷，4≠5，繼續入棧新元素
• 此時5入棧，棧中共有1,4,5，5位于棧頂，此時5與5相等，5出棧，出棧序列將5拿走，剩余4->1，棧頂元素為4,4與出棧序列第一個元素判斷，4=4，4出棧，同時出棧序列將4拿走，剩余1，棧中只剩最后一個元素1,此時恰好等于最后一個出棧元素1
  • 即可知，在入棧序列為1->2->3->4->5的條件下，出棧序列2->3->5->4->1是一個合法的出棧序列

核心思路在于，判斷棧頂元素是否等于此時出棧序列的第一個元素，若是，則執行出棧操作，同時指針后移，若否，繼續入棧新的元素，繼續執行判斷操作。

# -*- coding:utf-8 -*-
class Solution:def __init__(self):self.stack= []def IsPopOrder(self, pushV, popV):# write code hereif len(pushV) == 0 or len(popV)!= len(pushV):return Falsefor i in pushV:self.stack.append(i)while len(self.stack) and self.stack[-1] == popV[0]:self.stack.pop()popV.pop(0)if len(self.stack):return Falsereturn True
復制代碼

轉載于:https://juejin.im/post/5d1c6a33e51d45108223fcc6

總結

以上是生活随笔為你收集整理的剑指offer-----Python-----栈的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。