Python キュー関連のアプリケーションと演習を一緒に分析しましょう

この記事では、python に関する関連知識を提供します。主に、2 つのスタックを使用してキューを実装する方法や、キューを実装する 2 つのスタックを使用する方法など、キュー関連のアプリケーション演習を紹介します。スタック内の要素の連続性など。皆様のお役に立てれば幸いです。

推奨学習: python チュートリアル

0. 学習目標

キューの関連概念を学習しました。このセクションの主な目的は、キュー関連の演習を通じてキューの理解をさらに深め、同時にキューを使用して問題を解決できるようにすることです。いくつかの複雑な問題に対する解決策の時間計算量。

1. 2 つのスタックを使用してキューを実装します。

[質問] 2 つのスタックが与えられた場合、スタックの基本操作のみを使用してキューを実装します。

[アイデア] この問題を解決する鍵は、スタックの反転機能にあります。スタックにプッシュされた一連の要素は、スタックからポップされると逆の順序で返されます。 。したがって、2 つのスタックを使用すると、同じ順序で要素を返すことができます (元の順序を取得するために、要素の逆の順序が再度逆転されます)。具体的な操作を次の図に示します。

[アルゴリズム]

Enqueueenqueue:
要素をスタックにプッシュ stack_1
デキュー dequeue:
スタック stack_2 が空でない場合：
stack_2 スタックから最上位の要素をポップします
それ以外の場合:
stack_1 からすべての要素をポップし、 stack_2
stack_2 にプッシュします。 スタックから最上位の要素をポップします

[code]

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

[時間と空間の計算量] 時間計算量キューに入るのは $OD(1)\#\#\; です$#、スタック stack_2 が空でない場合、デキューの時間計算量は になります。 O( 1)、スタック stack_2 が空の場合 stack_1 から stack_2 に転送される要素を削除する必要がありますが、stack_2 に転送される要素の数はデキューされる要素の数と等しいため、デキューの償却時間計算量は O(1) です 。

2. 2 つのキューを使用したスタックの実装

[質問] 2 つのキューが与えられた場合、キューの基本操作のみを使用してスタックを実装します。

[アイデア] キューには順序を逆転する機能がないため、要素がキューに登録された順序が要素がデキューされる順序になります。したがって、キューに入れられた最後の要素を取得したい場合は、まず以前の要素をすべてデキューする必要があります。したがって、2 つのキューを使用してスタックを実装するには、キューの 1 つ store_queue を使用して要素を保存し、もう 1 つのキュー temp_queue を使用して一時出力を順番に保存する必要があります。最後の要素を取得します。チーム要素。 push 操作は、指定された要素をストレージ キュー store_queue にエンキューします。pop 操作は、最初にストレージ キュー store_queue から最後の要素を削除します。キューの外にあるすべての要素は一時キュー temp_queue に転送され、ストレージ キュー store_queue の最後の要素がデキューされて返されます。具体的な動作を以下の図に示します。

#[アルゴリズム]

 算法运行过程需要始终保持其中一个队列为空，用作临时队列
 入栈 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]。

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

[算法]

 如果队列 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 步，如下图所示：

[算法]

 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 中国語 Web サイトの他の関連記事を参照してください。