一起來分析Python隊列相關應用與習題-Python教學-PHP中文網

本篇文章為大家帶來了關於python的相關知識，其中主要介紹了隊列相關的應用於習題，包括了怎麼使用兩個棧來實現一個隊列，怎麼使用兩個佇列實作一個棧，棧中元素連續性判斷等等，希望對大家有幫助。

一起來分析Python隊列相關應用與習題

推薦學習：python教學

#0. 學習目標

我們已經學習了佇列的相關概念以及其實現，同時也了解了隊列在實際問題中的廣泛應用，本節的主要目的是透過隊列的相關習題來進一步加深對隊列的理解，同時能夠利用隊列降低一些複雜問題解決方案的時間複雜度。

1. 使用兩個堆疊實作一個佇列

[問題] 給定兩個堆疊，僅使用堆疊的基本操作實作一個佇列。

[思路] 解決此問題的關鍵在於堆疊的反轉特性，入棧的一系列元素在出棧時會以相反的順序傳回。因此，使用兩個堆疊就可以實現元素以相同的順序返回(反轉的元素序列再次反轉後就會得到原始順序)。具體操作如下圖所示：

一起來分析Python隊列相關應用與習題

[演算法]

入隊enqueue：
將元素推入堆疊stack_1
出隊dequeue：
如果棧stack_2 不為空：
如果堆疊⃀#stack_2 不為空： ⃀⃀⃀⃀⃀ stack_2
堆疊頂元素出棧
否則： 將所有元素依序從stack_1 彈出並壓入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()

登入後複製

[時空複雜度]

入隊時間複雜度為 $O (1) ，如果堆疊 stack_2$ 不為空，那麼出隊的時間複雜度為 $##O (1) ，如果堆疊 stack_2 為空，則需要將元素從$ stack_1 轉移到stack_2，但由於stack_2 中轉移的元素數量和出隊的元素數量是相等的，因此出隊的攤銷時間複雜度為 $O (##1 #) 。 2. 使用兩個佇列實作一個堆疊$

[問題]

給定兩個佇列，僅使用佇列的基本操作實作一個堆疊。

[想法] 由於佇列並未具備反轉順序的特性，入隊順序即為元素的出隊順序。因此想要取得最後一個入隊的元素，需要先將之前所有元素出隊。因此為了使用兩個佇列實作棧，我們需要將其中一個佇列

store_queue

用來儲存元素，另一個佇列temp_queue 則用來儲存為了取得最後一個元素而儲存暫存隊的元素。 push 操作將給定元素入隊到儲存佇列store_queue 中；pop 操作先將儲存佇列store_queue 中除最後一個元素外的所有元素都會轉移到臨時佇列temp_queue 中，然後儲存佇列store_queue 中的最後一個元素出隊並傳回。具體操作如下圖所示：

[演算法] 一起來分析Python隊列相關應用與習題

算法运行过程需要始终保持其中一个队列为空，用作临时队列
入栈 push：在非空队列中插入元素 data。
若队列 queue_1 为空：
将 data 插入队列 queue_2 中
否则：
将 data 插入队列 queue_1 中
出栈 pop：将队列中的前 $n - 1$ 个元素插入另一队列，删除并返回最后一个元素
若队列 queue_1 不为空：
将队列 queue_1 的前 $n - 1$ 个元素插入 queue_2，然后 queue_1 的最后一个元素出队并返回
若队列 queue_2 不为空：
将队列 queue_2 的前 $n - 1$ 个元素插入 queue_1，然后 queue_2 的最后一个元素出队并返回

[代码]

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)

登入後複製

[时空复杂度] push 操作的时间复杂度为 $O (1)$ ，由于 pop 操作时，都需要将所有元素从一个队列转移到另一队列，因此时间复杂度 $O (n)$ 。

3. 栈中元素连续性判断

[问题] 给定一栈 stack1，栈中元素均为整数，判断栈中每对连续的数字是否为连续整数(如果栈有奇数个元素，则排除栈顶元素)。例如，输入栈 [1, 2, 5, 6, -5, -4, 11, 10, 55]，输入为 True，因为排除栈顶元素 55 后，(1, 2)、(5, 6)、(-5, -4)、(11, 10) 均为连续整数。

[思路] 由于栈中可能存在奇数个元素，因此为了正确判断，首次需要将栈中元素反转，栈顶元素变为栈底，然后依次出栈，进行判断。

[算法]

栈 stack 中所有元素依次出栈，并插入队列 queue 中
队列 queue 中所有元素出队，并入栈 stack
while 栈 stack 不为空：
栈顶元素 e1 出栈，并插入队列 queue 中
如果栈 stack 不为空：
栈顶元素 e2 出栈，并插入队列 queue 中
如果 |e1-e2|!=1：
返回 False，跳出循环
队列 queue 中所有元素出队，并入栈 stack

[代码]

def check_stack_pair(stack):
    queue = Queue()
    flag = True
    # 反转栈中元素
    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

登入後複製

[时空复杂度] 时间复杂度为 $O (n)$ ，空间复杂度为 $O (n)$ 。

4. 一起來分析Python隊列相關應用與習題

[问题] 给定一个整数队列 queue，将队列的前半部分与队列的后半部分交错来重新排列元素。例如输入队列为 [1, 2, 3, 4, 5, 6, 7, 8, 9]，则输出应为 [1, 6, 2, 7, 3, 8, 4, 9, 5]。

[思路] 通过获取队列的前半部分，然后利用栈的反转特性，可以实现重排操作，如下图所示：

一起來分析Python隊列相關應用與習題

[算法]

如果队列 queue 中的元素数为偶数：
half=queue.size//2
否则：
half=queue.size//2+1
1. 将队列 queue 的前半部分元素依次出队并入栈 stack
2. 栈 stack 中元素出栈并入队 queue
3. 将队列 queue 中在步骤 1中未出队的另一部分元素依次出队并插入队尾
4. 将队列 queue 的前半部分元素依次出队并入栈 stack
5. 将栈 stack 和队列 queue 中的元素交替弹出并入队
6. 如果栈 stack 非空：
栈 stack 中元素出栈并入队

[代码]

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())

登入後複製

[时空复杂度] 时间复杂度为 $O (n)$ ，空间复杂度为 $O (n)$ 。

5. 反转队列中前 m 个元素的顺序

[问题] 给定一个整数 m 和一个整数队列 queue，反转队列中前 k 个元素的顺序，而其他元素保持不变。如 m=5，队列为 [1, 2, 3, 4, 5, 6, 7, 8, 9]，算法输出为 [5, 4, 3, 2, 1, 6, 7, 8, 9]。

[思路] 结合 [问题4] 我们可以发现，此题就是 [问题4] 的前 3 步，如下图所示：

反转队列中前 m 个元素的顺序

[算法]

1. 将队列 queue 的前 m 个元素依次出队并入栈 stack
2. 栈 stack 中元素出栈并入队 queue
3. 将队列 queue 中在步骤 1中未出队的另一部分元素依次出队并插入队尾

[代码]

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())

登入後複製

[时空复杂度] 时间复杂度为 $O (n)$ ，空间复杂度为 $O (n)$ 。

推薦學習：python教學

以上是一起來分析Python隊列相關應用與習題的詳細內容。更多資訊請關注PHP中文網其他相關文章！