建站
咨詢
售后
建站咨詢
新聞中心
本篇文章給大家?guī)?lái)了關(guān)于python的相關(guān)知識(shí)，其中主要介紹了隊(duì)列相關(guān)的應(yīng)用于習(xí)題，包括了怎么使用兩個(gè)棧來(lái)實(shí)現(xiàn)一個(gè)隊(duì)列，怎么使用兩個(gè)隊(duì)列實(shí)現(xiàn)一個(gè)棧，棧中元素連續(xù)性判斷等等，希望對(duì)大家有幫助。
推薦學(xué)習(xí)：python教程
我們已經(jīng)學(xué)習(xí)了隊(duì)列的相關(guān)概念以及其實(shí)現(xiàn)，同時(shí)也了解了隊(duì)列在實(shí)際問(wèn)題中的廣泛應(yīng)用，本節(jié)的主要目的是通過(guò)隊(duì)列的相關(guān)習(xí)題來(lái)進(jìn)一步加深對(duì)隊(duì)列的理解，同時(shí)能夠利用隊(duì)列降低一些復(fù)雜問(wèn)題解決方案的時(shí)間復(fù)雜度。
1. 使用兩個(gè)棧實(shí)現(xiàn)一個(gè)隊(duì)列
[問(wèn)題] 給定兩個(gè)棧，僅使用棧的基本操作實(shí)現(xiàn)一個(gè)隊(duì)列。
[思路] 解決此問(wèn)題的關(guān)鍵在于棧的反轉(zhuǎn)特性，入棧的一系列元素在出棧時(shí)會(huì)以相反的順序返回。因此，使用兩個(gè)棧就可以實(shí)現(xiàn)元素以相同的順序返回(反轉(zhuǎn)的元素序列再次反轉(zhuǎn)后就會(huì)得到原始順序)。具體操作如下圖所示：
[算法]
[代碼]
class Queue:
def __init__(self):
self.stack_1 = Stack()
self.stack_2 = Stack()
def enqueue(self, data):
self.stack_1.push(data)
def dequeue(self):
if self.stack_2.isempty():
while not self.stack_1.isempty():
self.stack_2.push(self.stack_1.pop())
return self.stack_2.pop()
[時(shí)空復(fù)雜度] 入隊(duì)時(shí)間復(fù)雜度為 O(1)，如果棧 stack_2 不為空，那么出隊(duì)的時(shí)間復(fù)雜度為 O(1)，如果棧 stack_2 為空，則需要將元素從 stack_1 轉(zhuǎn)移到 stack_2，但由于 stack_2 中轉(zhuǎn)移的元素?cái)?shù)量和出隊(duì)的元素?cái)?shù)量是相等的，因此出隊(duì)的攤銷(xiāo)時(shí)間復(fù)雜度為 O(1)。
2. 使用兩個(gè)隊(duì)列實(shí)現(xiàn)一個(gè)棧
[問(wèn)題] 給定兩個(gè)隊(duì)列，僅使用隊(duì)列的基本操作實(shí)現(xiàn)一個(gè)棧。
[思路] 由于隊(duì)列并不具備反轉(zhuǎn)順序的特性，入隊(duì)順序即為元素的出隊(duì)順序。因此想要獲取最后一個(gè)入隊(duì)的元素，需要首先將之前所有元素出隊(duì)。因此為了使用兩個(gè)隊(duì)列實(shí)現(xiàn)棧，我們需要將其中一個(gè)隊(duì)列 store_queue 用于存儲(chǔ)元素，另一個(gè)隊(duì)列 temp_queue 則用來(lái)保存為了獲取最后一個(gè)元素而保存臨時(shí)出隊(duì)的元素。push 操作將給定元素入隊(duì)到存儲(chǔ)隊(duì)列 store_queue 中；pop 操作首先把存儲(chǔ)隊(duì)列 store_queue 中除最后一個(gè)元素外的所有元素都轉(zhuǎn)移到臨時(shí)隊(duì)列 temp_queue 中，然后存儲(chǔ)隊(duì)列 store_queue 中的最后一個(gè)元素出隊(duì)并返回。具體操作如下圖所示：
[算法]
[代碼]
class Stack:
def __init__(self):
self.queue_1 = Queue()
self.queue_2 = Queue()
def isempty(self):
return self.queue_1.isempty() and self.queue_2.isempty()
def push(self, data):
if self.queue_2.isempty():
self.queue_1.enqueue(data)
else:
self.queue_2.enqueue(data)
def pop(self):
if self.isempty():
raise IndexError("Stack is empty")
elif self.queue_2.isempty():
while not self.queue_1.isempty():
p = self.queue_1.dequeue()
if self.queue_1.isempty():
return p
self.queue_2.enqueue(p)
else:
while not self.queue_2.isempty():
p = self.queue_2.dequeue()
if self.queue_2.isempty():
return p
self.queue_1.enqueue(p)
[時(shí)空復(fù)雜度] push 操作的時(shí)間復(fù)雜度為O(1)，由于 pop 操作時(shí)，都需要將所有元素從一個(gè)隊(duì)列轉(zhuǎn)移到另一隊(duì)列，因此時(shí)間復(fù)雜度O(n)。
3. 棧中元素連續(xù)性判斷
[問(wèn)題] 給定一棧 stack1，棧中元素均為整數(shù)，判斷棧中每對(duì)連續(xù)的數(shù)字是否為連續(xù)整數(shù)(如果棧有奇數(shù)個(gè)元素，則排除棧頂元素)。例如，輸入棧 [1, 2, 5, 6, -5, -4, 11, 10, 55]，輸入為 True，因?yàn)榕懦龡ｍ斣?55 后，(1, 2)、(5, 6)、(-5, -4)、(11, 10) 均為連續(xù)整數(shù)。
[思路] 由于棧中可能存在奇數(shù)個(gè)元素，因此為了正確判斷，首次需要將棧中元素反轉(zhuǎn)，棧頂元素變?yōu)闂５祝缓笠来纬鰲?，進(jìn)行判斷。
[算法]
[代碼]
def check_stack_pair(stack):
queue = Queue()
flag = True
# 反轉(zhuǎn)棧中元素
while not stack.isempty():
queue.enqueue(stack.pop())
while not queue.isempty():
stack.push(queue.dequeue())
while not stack.isempty():
e1 = stack.pop()
queue.enqueue(e1)
if not stack.isempty():
e2 = stack.pop()
queue.enqueue(e2)
if abs(e1-e2) != 1:
flag = False
break
while not queue.isempty():
stack.push(queue.dequeue())
return flag
[時(shí)空復(fù)雜度] 時(shí)間復(fù)雜度為 O(n)，空間復(fù)雜度為 O(n)。
4. 重新排列隊(duì)列中元素順序
[問(wèn)題] 給定一個(gè)整數(shù)隊(duì)列 queue，將隊(duì)列的前半部分與隊(duì)列的后半部分交錯(cuò)來(lái)重新排列元素。例如輸入隊(duì)列為 [1, 2, 3, 4, 5, 6, 7, 8, 9]，則輸出應(yīng)為 [1, 6, 2, 7, 3, 8, 4, 9, 5]。
[思路] 通過(guò)獲取隊(duì)列的前半部分，然后利用棧的反轉(zhuǎn)特性，可以實(shí)現(xiàn)重排操作，如下圖所示：
[算法]
[代碼]
def queue_order(queue):
stack = Stack()
size = queue.size if size % 2 == 0:
half = queue.size//2
else:
half = queue.size//2 + 1
res = queue.size - half for i in range(half):
stack.push(queue.dequeue())
while not stack.isempty():
queue.enqueue(stack.pop())
for i in range(res):
queue.enqueue(queue.dequeue())
for i in range(half):
stack.push(queue.dequeue())
for i in range(res):
queue.enqueue(stack.pop())
queue.enqueue(queue.dequeue())
if not stack.isempty():
queue.enqueue(stack.pop())
[時(shí)空復(fù)雜度] 時(shí)間復(fù)雜度為O(n)，空間復(fù)雜度為 O(n)。
5. 反轉(zhuǎn)隊(duì)列中前 m 個(gè)元素的順序
[問(wèn)題] 給定一個(gè)整數(shù) m 和一個(gè)整數(shù)隊(duì)列 queue，反轉(zhuǎn)隊(duì)列中前 k 個(gè)元素的順序，而其他元素保持不變。如 m=5，隊(duì)列為 [1, 2, 3, 4, 5, 6, 7, 8, 9]，算法輸出為 [5, 4, 3, 2, 1, 6, 7, 8, 9]。
[思路] 結(jié)合 [問(wèn)題4] 我們可以發(fā)現(xiàn)，此題就是 [問(wèn)題4] 的前 3 步，如下圖所示：
[算法]
[代碼]
def reverse_m_element(queue, m):
stack = Stack()
size = queue.size if queue.isempty() or m>size:
return
for i in range(m):
stack.push(queue.dequeue())
while not stack.isempty():
queue.enqueue(stack.pop())
for i in range(size-m):
queue.enqueue(queue.dequeue())
[時(shí)空復(fù)雜度] 時(shí)間復(fù)雜度為O(n)，空間復(fù)雜度為 O(n)。
當(dāng)前文章：一起來(lái)分析Python隊(duì)列相關(guān)應(yīng)用與習(xí)題
分享地址：http://www.5511xx.com/article/dhjpgje.html
