스택을 사용하여 대기열을 다른 대기열로 정렬 할 수 있는지 확인

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

문제 정책

"스택을 사용하여 대기열을 다른 대기열로 정렬 할 수 있는지 확인"문제는 n 개의 요소를 포함하는 대기열이 주어지고 대기열의 요소는 1에서 n까지의 숫자 순열임을 나타냅니다. 스택을 사용하여이 대기열을 다른 대기열에서 오름차순으로 정렬 할 수 있는지 확인하십시오.

예

queue = 8 -> 7 -> 5 -> 6 -> 4 -> 3 -> 2 -> 1

false

 

queue = 4 -> 1 -> 2 -> 3

true

확인 알고리즘 스택을 사용하여 큐를 다른 큐로 정렬 할 수 있는지 확인

처음에는 두 번째 변발 스택이 비어 있고 요소가 첫 번째 대기열에 임의의 순서로 존재합니다.
목표는 종류 스택을 사용하여 두 번째 대기열에 요소를 배치합니다.
큐 2 또는 스택에서 큐 1에 요소를 삽입 할 수 있습니다. 즉, 대기열 1의 앞면이 대기열 2에 추가되거나 스택의 맨 위가 대기열에 추가됩니다.
또한 큐 1의 첫 번째 요소로 2을, 두 번째 요소로 2를 삽입해야합니다.

1. Initialize a variable next as 1, this indicates that this variable should be inserted into queue 2.
2. If the front of the queue 1 or top of the stack is equals to next, remove the front or the top as required and move it to the queue 2, and increment next by 1.
3. Else if none of them is next, remove the front of queue 1 and push it to the stack and if the front of queue 1 is greater than top of stack, return false.
4. If all the elements are present in the queue 2, that is, both queue 1 and stack are empty, then it is possible to sort the queue, return true.

설명

두 번째 예를 살펴 보겠습니다.
대기열 = 4-> 1-> 2-> 3

처음에,
q1 = 4-> 1-> 2-> 3
q2 = 널
스택 = null

핀

암호

스택을 사용하여 큐를 다른 큐로 정렬 할 수 있는지 확인하는 Java 코드

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

class CheckIfAQueueCanBeSortedIntoAnotherQueueUsingAStack {
    private static boolean checkIfPossible(Queue<Integer> q) {
        // Initialize next as 1
        int next = 1;

        Stack<Integer> st = new Stack<>();

        while (!q.isEmpty() || !st.isEmpty()) {
            // if front of queue is next, remove it and increment next
            if (!q.isEmpty() && q.peek() == next) {
                q.poll();
                next++;
            }
            // if top of stack is next, remove it and increment next
            else if (!st.isEmpty() && st.peek() == next) {
                st.pop();
                next++;
            } else {
                // if q is empty return false
                if (q.isEmpty()) {
                    return false;
                } 
                // remove front of queue and push it to top of stack
                else {
                    int front = q.poll();
                    if (st.isEmpty()) {
                        st.push(front);
                    } else {
                        // if front of queue is greater than top of stack, return false
                        if (front > st.peek()) {
                            return false;
                        } else {
                            st.push(front);
                        }
                    }
                }
            }
        }

        // all the elements can be sorted, return true
        return true;
    }

    public static void main(String[] args) {
        // Example 1
        Queue<Integer> q1 = new LinkedList<>();
        q1.add(8);
        q1.add(7);
        q1.add(5);
        q1.add(6);
        q1.add(4);
        q1.add(3);
        q1.add(2);
        q1.add(1);

        System.out.println(checkIfPossible(q1));

        // Example 2
        Queue<Integer> q2 = new LinkedList<>();
        q2.add(4);
        q2.add(1);
        q2.add(2);
        q2.add(3);

        System.out.println(checkIfPossible(q2));
    }
}

false
true

스택을 사용하여 큐를 다른 큐로 정렬 할 수 있는지 확인하는 C ++ 코드

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

bool checkIfPossible(queue<int> &q) {
    stack<int> st;
    
    // Initialize a variable next as 1
    int next = 1;
    
    while (!q.empty() || !st.empty()) {
        // if front of queue is next, remove it and increment next
        if (!q.empty() && q.front() == next) {
            q.pop();
            next++;
        }
        // if top of stack is next, remove it and increment next
        else if (!st.empty() && st.top() == next) {
            st.pop();
            next++;
        } else {
            // if q is empty return false
            if (q.empty()) {
                return false;
            } 
            // remove front of queue and push it to top of stack
            else {
                int front = q.front();
                q.pop();
                if (st.empty()) {
                    st.push(front);
                } else {
                    // if front of queue is greater than top of stack, return false
                    if (front > st.top()) {
                        return false;
                    } else {
                        st.push(front);
                    }
                }
            }
        }
    }
    
    
    return true;
}

int main() {
  // Example 1
    queue<int> q1;
    q1.push(8);
    q1.push(7);
    q1.push(5);
    q1.push(6);
    q1.push(4);
    q1.push(3);
    q1.push(2);
    q1.push(1);

    if (checkIfPossible(q1)) {
        cout<<"true"<<endl;
    } else {
        cout<<"false"<<endl;
    }

    // Example 2
    queue<int> q2;
    q2.push(4);
    q2.push(1);
    q2.push(2);
    q2.push(3);

    if (checkIfPossible(q2)) {
        cout<<"true"<<endl;
    } else {
        cout<<"false"<<endl;
    }
  
  return 0;
}

false
true

복잡성 분석

시간 복잡성

의 위에), 우리가 전체 입력을 통과하면서. 알고리즘은 선형 시간 복잡도를 사용합니다.

공간 복잡성

의 위에), 요소를 큐 또는 스택에 저장했기 때문입니다. 알고리즘은 선형 공간을 차지합니다.