站長(zhǎng)資訊網(wǎng)本篇文章給大家?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教程
0. 學(xué)習(xí)目標(biāo)
我們已經(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ì)得到原始順序)。具體操作如下圖所示：
[算法]
?入隊(duì)
enqueue：
???將元素推入棧stack_1
?出隊(duì)dequeue：
???如果棧stack_2不為空：
?????stack_2棧頂元素出棧
???否則：
?????將所有元素依次從stack_1彈出并壓入stack_2
?????stack_2棧頂元素出棧
[代碼]
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ì)并返回。具體操作如下圖所示：
[算法]
?算法運(yùn)行過(guò)程需要始終保持其中一個(gè)隊(duì)列為空，用作臨時(shí)隊(duì)列
?入棧push：在非空隊(duì)列中插入元素data。
???若隊(duì)列queue_1為空：
?????將data插入 隊(duì)列queue_2中
???否則：
?????將data插入 隊(duì)列queue_1中
?出棧pop：將隊(duì)列中的前n?1 個(gè)元素插入另一隊(duì)列，刪除并返回最后一個(gè)元素
???若隊(duì)列queue_1不為空：
?????將隊(duì)列queue_1的前n?1 個(gè)元素插入queue_2，然后queue_1的最后一個(gè)元素出隊(duì)并返回
???若隊(duì)列queue_2不為空：
?????將隊(duì)列queue_2的前 n?1 個(gè)元素插入queue_1，然后queue_2的最后一個(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)行判斷。
[算法]
?棧
stack中所有元素依次出棧，并插入隊(duì)列queue中
?隊(duì)列queue中所有元素出隊(duì)，并入棧stack
? while 棧stack不為空：
???棧頂元素e1出棧，并插入隊(duì)列queue中
???如果棧stack不為空：
?????棧頂元素e2出棧，并插入隊(duì)列queue中
?????如果|e1-e2|!=1：
???????返回False，跳出循環(huán)
?隊(duì)列queue中所有元素出隊(duì)，并入棧stack
[代碼]
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)重排操作，如下圖所示：
[算法]
?如果隊(duì)列
queue中的元素?cái)?shù)為偶數(shù)：
???half=queue.size//2
?否則：
???half=queue.size//2+1
?1. 將隊(duì)列queue的前半部分元素依次出隊(duì)并入棧stack
?2. 棧stack中元素出棧并入隊(duì)queue
?3. 將隊(duì)列queue中在步驟 1中未出隊(duì)的另一部分元素依次出隊(duì)并插入隊(duì)尾
?4. 將隊(duì)列queue的前半部分元素依次出隊(duì)并入棧stack
?5. 將棧stack和隊(duì)列queue中的元素交替彈出并入隊(duì)
?6. 如果棧stack非空：
???棧stack中元素出棧并入隊(duì)
[代碼]
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 步，如下圖所示：
[算法]
?1. 將隊(duì)列
queue的前m個(gè)元素依次出隊(duì)并入棧stack
?2. 棧stack中元素出棧并入隊(duì)queue
?3. 將隊(duì)列queue中在步驟 1中未出隊(duì)的另一部分元素依次出隊(duì)并插入隊(duì)尾
[代碼]
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)。
推薦學(xué)習(xí)：python教程
