การย้อนกลับคิวโดยใช้การเรียกซ้ำ


ระดับความยาก สะดวกสบาย
คิว Recursion Scripter ทางเทคนิค

ในการย้อนกลับคิวโดยใช้ปัญหาการเรียกซ้ำเราได้ให้ไฟล์ คิวเขียนอัลกอริทึมแบบเรียกซ้ำเพื่อย้อนกลับคิวโดยใช้การเรียกซ้ำ

ตัวอย่าง

อินพุต
10 -> 9 -> 3 -> 11 -> 5
เอาท์พุต
5 -> 11 -> 3 -> 9 -> 10

อินพุต
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8
เอาท์พุต
8 -> 7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1

อัลกอริทึมสำหรับการกลับคิวโดยใช้การเรียกซ้ำ

ขอให้เราจินตนาการว่าฟังก์ชัน reverse (คิว) เป็นฟังก์ชันวนซ้ำที่ย้อนกลับคิวที่กำหนดให้ คำจำกัดความสามารถเข้าใจได้จากตัวอย่าง

คิว = 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8
ย้อนกลับ (1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8) = ย้อนกลับ (2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8) -> 1
ย้อนกลับ (2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8) = ย้อนกลับ (3 -> 4 -> 5 -> 6 -> 7 -> 8) -> 2
ย้อนกลับ (3 -> 4 -> 5 -> 6 -> 7 -> 8) = ย้อนกลับ (4 -> 5 -> 6 -> 7 -> 8) -> 3
ย้อนกลับ (4 -> 5 -> 6 -> 7 -> 8) = ย้อนกลับ (5 -> 6 -> 7 -> 8) -> 4
ย้อนกลับ (5 -> 6 -> 7 -> 8) = ย้อนกลับ (6 -> 7 -> 8) -> 5
ย้อนกลับ (6 -> 7 -> 8) = ย้อนกลับ (7 -> 8) -> 6
ย้อนกลับ (7 -> 8) = ย้อนกลับ (8) -> 7
ย้อนกลับ (8) = ย้อนกลับ () -> 8
reverse () = คิวว่าง

ดังนั้น
ย้อนกลับ (8) = 8
ย้อนกลับ (7 -> 8) = 8 -> 7
ย้อนกลับ (6 -> 7 -> 8) = 8 -> 7 -> 6
ย้อนกลับ (5 -> 6 -> 7 -> 8) = 8 -> 7 -> 6 -> 5
ย้อนกลับ (4 -> 5 -> 6 -> 7 -> 8) = 8 -> 7 -> 6 -> 5 -> 4
ย้อนกลับ (3 -> 4 -> 5 -> 6 -> 7 -> 8) = 8 -> 7 -> 6 -> 5 -> 4 -> 3
ย้อนกลับ (2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8) = 8 -> 7 -> 6 -> 5 -> 4 -> 3 -> 2
ย้อนกลับ (1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8) = 8 -> 7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1

การย้อนกลับคิวโดยใช้การเรียกซ้ำ

กรณีฐานของการเรียกซ้ำ: การย้อนกลับของคิวว่างคือคิวว่าง

  1. หากคิวว่างเปล่าให้ส่งคืนมิฉะนั้นจะแสดงองค์ประกอบแรกของคิวและเก็บไว้ในตัวแปรโดยพูดว่า curr
  2. เรียกใช้วิธีการย้อนกลับซ้ำในคิวที่เหลือ
  3. วิธีการย้อนกลับจะย้อนกลับคิวที่เหลือผลักองค์ประกอบ curr ไปที่คิว
  4. คิวจะกลับด้านพิมพ์องค์ประกอบ

รหัส JAVA สำหรับการย้อนกลับคิวโดยใช้การเรียกซ้ำ

import java.util.LinkedList;
import java.util.Queue;

public class ReversingAQueueUsingRecursion {
    private static void reverseQueue(Queue<Integer> queue) {
        // Base case
        // reverse of an empty queue is an empty queue
        if (queue.isEmpty()) {
            return;
        }

        // remove an element from queue and store it in a variable, say curr
        int curr = queue.poll();
        // recursively call the reverseQueue method on remaining queue
        reverseQueue(queue);
        // add the removed element to the end of the reversed queue
        queue.add(curr);
    }

    public static void main(String[] args) {
        // Example 1
        Queue<Integer> q1 = new LinkedList<>();
        q1.add(10);
        q1.add(9);
        q1.add(3);
        q1.add(11);
        q1.add(5);
        reverseQueue(q1);
        for (Integer i : q1) {
            System.out.print(i + " ");
        }
        System.out.println();

        // Example 2
        Queue<Integer> q2 = new LinkedList<>();
        q2.add(1);
        q2.add(2);
        q2.add(3);
        q2.add(4);
        q2.add(5);
        q2.add(6);
        q2.add(7);
        q2.add(8);
        reverseQueue(q2);
        for (Integer i : q2) {
            System.out.print(i + " ");
        }
        System.out.println();
    }
}
5 11 3 9 10 
8 7 6 5 4 3 2 1

รหัส C ++ สำหรับการย้อนกลับคิวโดยใช้การเรียกซ้ำ

#include<bits/stdc++.h> 
using namespace std; 

void reverseQueue(queue<int> &q) {
    // Base case
    // reverse of an empty queue is an empty queue
    if (q.empty()) {
        return;
    }
    
    // remove an element from queue and store it in a variable, say curr
    int curr = q.front();
    q.pop();
    // recursively call the reverseQueue method on remaining queue
    reverseQueue(q);
    // add the removed element to the end of the reversed queue
    q.push(curr);
}

int main() {
    // Example 1
    queue<int> q1;
    q1.push(10);
    q1.push(9);
    q1.push(3);
    q1.push(11);
    q1.push(5);
    reverseQueue(q1);
    while (!q1.empty()) {
        cout<<q1.front()<<" ";
        q1.pop();
    }
    cout<<endl;
    
    // Example 2
    queue<int> q2;
    q2.push(1);
    q2.push(2);
    q2.push(3);
    q2.push(4);
    q2.push(5);
    q2.push(6);
    q2.push(7);
    q2.push(8);
    reverseQueue(q2);
    while (!q2.empty()) {
        cout<<q2.front()<<" ";
        q2.pop();
    }
    cout<<endl;
    
    return 0;
}
5 11 3 9 10 
8 7 6 5 4 3 2 1

การวิเคราะห์ความซับซ้อน

ความซับซ้อนของเวลา = O (n)
ความซับซ้อนของพื้นที่ = O (n)เนื่องจากการเรียกซ้ำซึ่งใช้แนวคิดสแต็ก
โดยที่ n คือจำนวนองค์ประกอบในคิว

อ้างอิง