스택을 사용하는 대기열

난이도 쉽게
자주 묻는 질문 수행자 어도비 벽돌 아마존 드 쇼 Flipkart 골드만 삭스 인포에지 InMobi에 MakeMyTrip MAQ Microsoft 모건 스탠리 (Morgan Stanley) 신탁 월마트 연구소
스택조회수 31

대기열에서 스택 문제, 스택 데이터 구조의 표준 기능을 사용하여 큐의 다음 기능을 구현해야합니다.

  1. 대기열에 넣기 : 대기열 끝에 요소 추가
  2. 대기열에서 빼기 : 대기열 시작에서 요소 제거

입력:
대기열에 넣기 (5)
대기열에 넣기 (11)
대기열에 넣기 (39)
Dequeue () // 5 반환
대기열에 넣기 (12)
Dequeue () // 11 반환
Dequeue () // 39 반환
출력:
5
11
39

암호알고리즘

대기열은 두 개의 스택을 사용하여 구현할 수 있습니다. 첫 번째는 대기열에 넣는 작업을 비용이 많이 들게하고 두 번째는 대기열에서 빼기 작업을 비용이 많이 들게하는 방법으로 스택을 사용하여 대기열을 구현할 수 있습니다.

스택을 사용하는 대기열에 대한 방법 1 (대기열에 추가 작업)

두 개의 스택 st1 및 st2를 만듭니다. 시각화 변발 st1에서 st1의 맨 위가 대기열의 맨 앞에 있고 st1에서 아래쪽으로 이동하는 것은 대기열에서 앞으로 이동하는 것과 유사합니다.

대기열에 넣기 (x)

x를 대기열 뒤쪽으로 푸시하는 것은 x를 스택 st1의 맨 아래로 푸시하는 것과 같습니다.

  1. st1에서 모든 요소를 ​​제거하고 st2로 푸시하십시오.
  2. x를 st2로 푸시합니다.
  3. st2에서 모든 요소를 ​​제거하고 st1로 다시 푸시하십시오.

시간 복잡성 = O (n) A

스택을 사용하는 대기열

대기열에서 빼기 ()

대기열의 전면에서 요소를 제거하는 것은 스택 st1의 상단을 제거하는 것과 유사합니다. 따라서 st1이 비어 있지 않으면 st1의 상단을 팝하고 반환합니다.

시간 복잡성 = O (1)

방법 1의 전체 공간 복잡성 = O (N)

스택을 사용하는 대기열 용 JAVA 코드

import java.util.Stack;

public class QueueUsingStacks {
    // Costly Enqueue Operation
    private static Stack<Integer> st1;
    private static Stack<Integer> st2;

    private static void enqueue(int x) {
        // remove all the elements from st1 and push them to st2
        while (!st1.isEmpty()) {
            st2.push(st1.pop());
        }

        // push x to st2
        st2.push(x);

        // remove all the elements from st2 and push them back to st1
        while (!st2.isEmpty()) {
            st1.push(st2.pop());
        }
    }

    private static int dequeue() {
        if (st1.isEmpty()) {
            return -1;
        }

        // if st1 is not empty return and remove the top of st1
        return st1.pop();
    }

    public static void main(String[] args) {
        st1 = new Stack<>();
        st2 = new Stack<>();
        
        // Example
        enqueue(5);
        enqueue(11);
        enqueue(39);
        System.out.println(dequeue());
        enqueue(12);
        System.out.println(dequeue());
        System.out.println(dequeue());
    }
}
5
11
39

C ++ 코드

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

// Costly Enqueue Operation

stack<int> st1;
stack<int> st2;

void enqueue(int x) {
    // remove all the elements from st1 and push them to st2
    while (!st1.empty()) {
        int curr = st1.top();
        st1.pop();
        st2.push(curr);
    }
    
    // push x to st2
    st2.push(x);
    
    // remove all the elements from st2 and push them back to st1
    while (!st2.empty()) {
        int curr = st2.top();
        st2.pop();
        st1.push(curr);
    }
}

int dequeue() {
    if (st1.empty()) {
        return -1;
    }
    
    // if st1 is not empty return and remove the top of st1
    int top = st1.top();
    st1.pop();
    return top;
}

int main() {
    // Example
    enqueue(5);
    enqueue(11);
    enqueue(39);
    cout<<dequeue()<<endl;
    enqueue(12);
    cout<<dequeue()<<endl;
    cout<<dequeue()<<endl;
    
    return 0;
}
5
11
39

스택을 사용하는 대기열에 대한 방법 2 (대기열 제거 작업)

두 개의 스택 st1 및 st2를 만듭니다. st1의 대기열 시각화, st1의 상단은 대기열의 뒤쪽을 나타내며, st1에서 위쪽으로 이동하는 것은 대기열에서 앞으로 이동하는 것과 유사합니다.

대기열에 넣기 (x)

x를 대기열 뒤쪽으로 푸시하는 것은 x를 stack_st1의 맨 위로 푸시하는 것과 유사합니다. 따라서 x를 st1의 맨 위로 밀어 넣으십시오.

시간 복잡성 = O (1)

대기열에서 빼기 ()

대기열의 전면에서 요소를 제거하는 것은 stack_st1의 맨 아래에서 요소를 제거하는 것과 유사합니다. 따라서 st1이 비어 있지 않으면

  1. st1에서 모든 요소를 ​​제거하고 st2로 푸시하십시오.
  2. st2의 상단을 팝하고 가변 상단에 저장합니다.
  3. st2에서 모든 요소를 ​​제거하고 st1로 다시 푸시하십시오.
  4. 돌아 가기

시간 복잡성 = O (N)

스택을 사용하는 대기열

방법 2의 전체 공간 복잡성 = O (N)

JAVA 코드

import java.util.Stack;

public class QueueUsingStacks {
    // Costly Dequeue Operation
    private static Stack<Integer> st1;
    private static Stack<Integer> st2;

    private static void enqueue(int x) {
        // push x to top of st1
        st1.push(x);
    }

    private static int dequeue() {
        if (st1.isEmpty()) {
            return -1;
        }

        // if st1 is not empty
        // remove all the elements from st1 and push them to st2
        while (!st1.isEmpty()) {
            st2.push(st1.pop());
        }

        // pop the top of st2 and store it in a variable top
        int top = st2.pop();

        // remove all the elements from st2 and push them back to st1
        while (!st2.isEmpty()) {
            st1.push(st2.pop());
        }
        
        // return top
        return top;
    }

    public static void main(String[] args) {
        st1 = new Stack<>();
        st2 = new Stack<>();

        // Example
        enqueue(5);
        enqueue(11);
        enqueue(39);
        System.out.println(dequeue());
        enqueue(12);
        System.out.println(dequeue());
        System.out.println(dequeue());
    }
}
5
11
39

C ++ 코드

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

// Costly Dequeue Operation

stack<int> st1;
stack<int> st2;

void enqueue(int x) {
    // push x to top of st1
    st1.push(x);
}

int dequeue() {
    if (st1.empty()) {
        return -1;
    }
    
    // if st1 is not empty
    // remove all the elements from st1 and push them to st2
    while (!st1.empty()) {
        int curr = st1.top();
        st1.pop();
        st2.push(curr);
    }
    
    // pop the top of st2 and store it in a variable top
    int top = st2.top();
    st2.pop();
    
    // remove all the elements from st2 and push them back to st1
    while (!st2.empty()) {
        int curr = st2.top();
        st2.pop();
        st1.push(curr);
    }
    
    // return top
    return top;
}

int main() {
    // Example
    enqueue(5);
    enqueue(11);
    enqueue(39);
    cout<<dequeue()<<endl;
    enqueue(12);
    cout<<dequeue()<<endl;
    cout<<dequeue()<<endl;
    
    return 0;
}
5
11
39

레퍼런스 1     참조 2

Translate »