재귀를 사용하여 대기열 반전

난이도 쉽게
재귀 기술 스크립터조회수 39

재귀 문제를 사용하여 대기열을 되돌릴 때 우리는 변발, 재귀 알고리즘을 작성하여 재귀를 사용하여 큐를 뒤집습니다.

입력
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 (queue) 함수가 주어진 큐를 뒤집는 재귀 함수라고 상상 해보자. 그 정의는 예를 들어 이해할 수 있습니다.

대기열 = 1-> 2-> 3-> 4-> 5-> 6-> 7-> 8
reverse (1-> 2-> 3-> 4-> 5-> 6-> 7-> 8) = reverse (2-> 3-> 4-> 5-> 6-> 7-> 8)-> 1
reverse (2-> 3-> 4-> 5-> 6-> 7-> 8) = reverse (3-> 4-> 5-> 6-> 7-> 8)-> 2
reverse (3-> 4-> 5-> 6-> 7-> 8) = reverse (4-> 5-> 6-> 7-> 8)-> 3
reverse (4-> 5-> 6-> 7-> 8) = reverse (5-> 6-> 7-> 8)-> 4
reverse (5-> 6-> 7-> 8) = reverse (6-> 7-> 8)-> 5
reverse (6-> 7-> 8) = reverse (7-> 8)-> 6
reverse (7-> 8) = reverse (8)-> 7
reverse (8) = reverse ()-> 8
reverse () = 빈 대기열

그래서,
reverse (8) = 8
reverse (7-> 8) = 8-> 7
reverse (6-> 7-> 8) = 8-> 7-> 6
reverse (5-> 6-> 7-> 8) = 8-> 7-> 6-> 5
reverse (4-> 5-> 6-> 7-> 8) = 8-> 7-> 6-> 5-> 4
reverse (3-> 4-> 5-> 6-> 7-> 8) = 8-> 7-> 6-> 5-> 4-> 3
reverse (2-> 3-> 4-> 5-> 6-> 7-> 8) = 8-> 7-> 6-> 5-> 4-> 3-> 2
reverse (1-> 2-> 3-> 4-> 5-> 6-> 7-> 8) = 8-> 7-> 6-> 5-> 4-> 3-> 2-> 1

재귀를 사용하여 대기열 반전

재귀의 기본 사례: 빈 큐의 반대는 빈 큐입니다.

  1. 큐가 비어 있으면 리턴하고, 그렇지 않으면 큐의 첫 번째 요소를 튀어 나와 변수에 저장하십시오 (예 : curr).
  2. 나머지 큐에서 reverse 메서드를 재귀 적으로 호출합니다.
  3. reverse 메서드는 나머지 대기열을 반대로하고 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은 큐의 요소 수입니다.

참조

Translate »