대기열 반전

난이도 쉽게
자주 묻는 질문 수행자 Coursera 배달 팩트 셋 그레이 오렌지 조호 (Zoho)
라슨 & 투 브로 스택조회수 127

시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.

대기열 문제 반전에서 우리는 변발, 쓰기 연산 대기열을 되돌립니다.

입력
대기열 = 10-> 8-> 4-> 23
산출
대기열 = 23-> 4-> 8-> 10

입력
대기열 = 11-> 98-> 31-> 42-> 73-> 6
산출
대기열 = 6-> 73-> 42-> 31-> 98-> 11

입력
대기열 = 1-> 2-> 3-> 4-> 5-> 6-> 7-> 8-> 9
산출
대기열 = 9-> 8-> 7-> 6-> 5-> 4-> 3-> 2-> 1

대기열 반전 알고리즘

대기열은 다음을 사용하여 되돌릴 수 있습니다. 스택,

  1. 대기열에서 모든 요소를 ​​제거하고 스택으로 푸시합니다.
  2. 스택에서 모든 요소를 ​​튀어 나와 대기열로 다시 푸시합니다.
  3. 대기열이 존경받으며 대기열의 요소를 인쇄하십시오.

대기열 반전에 대한 설명

예를 들어,
대기열 = 10-> 8-> 4-> 23

1단계

하나씩 대기열에서 요소를 제거하고 스택으로 푸시합니다.
대기열 = 10-> 8-> 4-> 23 및 스택 = null
반복 1
대기열 = 8-> 4-> 23 및 스택 = 10
반복 2
대기열 = 4-> 23 및 스택 = 8-> 10
반복 3
대기열 = 23 및 스택 = 4-> 8-> 23
반복 4
대기열 = null 및 스택 = 23-> 4-> 8-> 23

2단계

스택에서 모든 요소를 ​​꺼내 대기열로 다시 푸시합니다.
대기열 = null 및 스택 = 23-> 4-> 8-> 10
반복 1
대기열 = 23 및 스택 = 4-> 8-> 10
반복 2
대기열 = 23-> 4 및 스택 = 8-> 10
반복 3
대기열 = 23-> 4-> 8 및 스택 = 10
반복 4
대기열 = 23-> 4-> 8-> 10 및 스택 = null

대기열이 반전됩니다. 자세한 내용은 아래 이미지를 참조하십시오.

대기열 반전

대기열 반전을위한 JAVA 코드

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

public class ReversingAQueue {
    private static void reverseQueue(Queue<Integer> queue) {
        int n = queue.size();

        Stack<Integer> stack = new Stack<>();
        // Remove all the elements from queue and push them to stack
        for (int i = 0; i < n; i++) {
            int curr = queue.poll();
            stack.push(curr);
        }

        // Pop out elements from the stack and push them back to queue
        for (int i = 0; i < n; i++) {
            int curr = stack.pop();
            queue.add(curr);
        }

        // Print the reversed queue
        for (Integer i : queue) {
            System.out.print(i + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        // Example 1
        Queue<Integer> q1 = new LinkedList<>();
        q1.add(10);
        q1.add(8);
        q1.add(4);
        q1.add(23);
        reverseQueue(q1);

        // Example 2
        Queue<Integer> q2 = new LinkedList<>();
        q2.add(11);
        q2.add(98);
        q2.add(31);
        q2.add(42);
        q2.add(73);
        q2.add(6);
        reverseQueue(q2);
    }
}
23 4 8 10 
6 73 42 31 98 11

대기열 반전을위한 C ++ 코드

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

void reverseQueue(queue<int> &queue) {
    int n = queue.size();
    
    stack<int> st;
    // Remove all the elements from queue and push them to stack
    for (int i = 0; i < n; i++) {
        int curr = queue.front();
        queue.pop();
        st.push(curr);
    }
    
    // Pop out elements from the stack and push them back to queue
    for (int i = 0; i < n; i++) {
        int curr = st.top();
        st.pop();
        queue.push(curr);
    }
    
    // Print the reversed queue
    for (int i = 0; i < n; i++) {
        int curr = queue.front();
        queue.pop();
        cout<<curr<<" ";
        queue.push(curr);
    }
    cout<<endl;
}

int main() {
    // Example 1
    queue<int> q1;
    int k1 = 3;
    q1.push(10);
    q1.push(8);
    q1.push(4);
    q1.push(23);
    reverseQueue(q1);

    // Example 2
    queue<int> q2;
    int k2 = 2;
    q2.push(11);
    q2.push(98);
    q2.push(31);
    q2.push(42);
    q2.push(73);
    q2.push(6);
    reverseQueue(q2);
}
23 4 8 10 
6 73 42 31 98 11

복잡성 분석

시간 복잡성 = O (N)
공간 복잡성 = O (N) 
여기서 n은 큐의 노드 수입니다.

참조

균열 시스템 설계 인터뷰
Translate »