[해커랭크] Queue using Two Stacks (C++)

문제 링크: www.hackerrank.com/challenges/queue-using-two-stacks/problem?h_r=profile

Queue using Two Stacks | HackerRank

1. 주의할 점

- Dequeue를 진행할때 마다 여분 스택을 이용하여 스택 전체를 옮기고 빼고 다시 옮기는 일이 없도록 한다 -> TLE 발생

 

2. 구현

- Enqueue를 수행하는 Stack S, Dequeue에 활용될 Stack os를 사용한다. OS에는 Stack S에 담겨있던 원소들이 역순으로 채워진다

- Front라는 변수를 통해 Queue의 Front에 위치한 수를 저장한다

- Enqueue가 수행될 때, S와 OS가 비었으면 Front를 해당 값으로 지정한다. 입력 받은 값은 S에 push한다

- Dequeue가 수행되는 경우, OS가 비었는지 확인한다. OS는 Stack S를 역순으로 담았기 때문에 비어있지 않다면 OS의 Top을 Pop한다.

- OS가 비었다면, S에 담겨있는 내용 전부를 OS로 옮긴다(S의 Top -> OS에 push). 이후, OS의 Top을 Pop한다

- 이제 Front를 갱신시켜야 한다

- 만약 OS가 비어있지 않다면, OS의 Top을 Front로 지정한다

- OS가 비었다면, 2가지의 경우가 존재한다.

- 첫 째, S의 크기를 확인하여 S의 크기 또한 0이라면 Queue가 비었으므로 Front를 0으로 초기화한다

- 둘 째, S가 비어있지 않다면, S에 들어있는 모든 원소들을 OS로 옮긴 이후, OS의 Top을 Front로 지정한다

 

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <stack>
using namespace std;

int main() {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */  
    int query,a,b,front;
    stack<int> s, os;        //스택, 반대로 채워넣을 os
    cin>>query;
    for(int t=0;t<query;t++){
        cin>>a;
        if(a==1){       //enqueue
            cin>>b;
            s.push(b);
            if(os.empty() && s.size()==1)
                front = b;
        }
        else if(a==2){      //dequeue
            if(!os.empty())        //거꾸로 뒤집은 Stack이 비어있지 않은 경우
                os.pop();          
            else{       //빈 경우
                while(!s.empty()){
                    int val = s.top();
                    s.pop();
                    os.push(val);
                }
                os.pop();
            }
            if(os.empty()){
                if(s.empty())
                    front = 0;
                else{
                    while(!s.empty()){
                        int val = s.top();
                        s.pop();
                        os.push(val);
                    }
                    front = os.top();
                }
            }
            else 
                front = os.top();
        }
        else       //print front
            cout << front<<'\n';
        
    } 
    return 0;
}