[BaekJoon] 24511번 - queuestack [Java][C++]

문제 링크

---

1. 문제 풀이

queuestack이라는 자료구조는 큐 또는 스택 $N$ 개로 이루어져 있고, 각 큐 또는 스택마다 하나의 원소가 있으며 앞에서 pop 된 것을 뒤에 넣고 다시 pop을 한 후 뒤로 넣는 과정이 반복된다. 스택의 경우 최근에 삽입한 원소를 다시 꺼내기 때문에 queuestack에서 스택들은 연산에 사실상 아무 역할도 하지 않는다. 따라서 큐만 가지고 연산을 해도 동일한 결과가 나오며 큐들로 해당 연산을 진행해보면 가장 마지막 큐의 원소가 꺼내지고 나머지 원소들은 한 칸씩 밀리는 구조라는 것을 볼 수 있다.

따라서 덱 자료구조를 활용해 큐에 넣을 원소들을 하나의 덱에 쭉 넣어주고 새로 삽입하는 원소는 덱 앞에 삽입하고 꺼낼 원소는 덱 뒤에서 꺼내면 된다.

---

2. 코드

1. 풀이 [Java]

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;

        int N = Integer.parseInt(br.readLine());

        boolean[] isQueue = new boolean[1 + N];
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            int flag = Integer.parseInt(st.nextToken());
            if (flag == 0) {
                isQueue[i] = true;
            }
        }

        Deque<Integer> dq = new ArrayDeque<>();
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            int x = Integer.parseInt(st.nextToken());
            if (isQueue[i]) {
                dq.offerLast(x);
            }
        }

        int M = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < M; i++) {
            int x = Integer.parseInt(st.nextToken());
            dq.offerFirst(x);

            sb.append(dq.pollLast()).append(" ");
        }

        System.out.println(sb);
    }
}

2. 풀이 [C++]

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<int> isQueue(n);
    for (int& x : isQueue) cin >> x;

    deque<int> dq;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        if (isQueue[i] == 0) dq.push_back(x);
    }

    int m;
    cin >> m;

    for (int i = 0; i < m; i++) {
        int x;
        cin >> x;

        dq.push_front(x);
        cout << dq.back() << ' ';
        dq.pop_back();
    }
}

---