[백준/c++] 24511번: queuestack

문제 링크 - https://www.acmicpc.net/problem/24511

[문제]


[풀이]

  • 자료구조가 stack인경우 : LIFO이므로, 뒤에 push되고 뒤에서 pop되므로 삽입된 원소가 그대로 나간다.
  • 자료구조가 queue인경우 : FIFO 이므로 뒤에 push되고, 앞에서 pop 되므로 queue내에서 보면 자리가 하나씩 밀리는 꼴이다.
  • 즉 stack일 경우는 들어오는 원소가 그대로 나가므로, 기존에 있던 원소는 무시하고 새로 들어오는 원소만 넣어주면 되고, queue일 경우는 원래 있던 원소를 밀어주는 방식이므로, 원래있던 원소들을 미리 넣어준 상태에서, 새로 들어온 원소들을 앞으로 넣어준다.
    -코드에서 bool flag를 통해 기존 자료구조가 queue인지 stack인지 체크하여 queue일때만 원소를 deque에 넣어주었다.
  • 원소 1개가 들어올때마다, 원소 1개를 반환해야 한다.
  • 앞에서 push하고 뒤에서 pop하는 방식이므로, 자료구조 deque를 사용한다.

[코드]

//24511번: queuestack
#include <iostream>
#include <deque>

using namespace std;

deque<int> dq;
int n,m;
bool flag[100001]; //0:queue, 1:stack

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    cin>>n;
    for(int i=0; i<n; i++){
        cin>>flag[i];
    }
    for(int i=0; i<n; i++){
        int x;
        cin>>x;
        if(flag[i]==0) //queue일때만 deque에 원소 삽입
        dq.push_back(x);
    }
    cin>>m;
    for(int i=0; i<m; i++){
        int y;
        cin>>y;
        dq.push_front(y);
        cout<<dq.back()<<" ";
        dq.pop_back();
        
    }
    //전부 stack일 경우, dq에 미리 넣는 과정없이  새 dq에 push_front, pop_back과정 반복하면 됨.

}

좋은 웹페이지 즐겨찾기