[BOJ/C++] 단계별로 풀어보기 - 스택, 큐, 덱 1

2026.03.06일차 입니다.
개강 전 다른 토이 프로젝트 진행하느라 또 늦었습니다.
해당 토이 프로젝트는 현재 1차 완성 상태이며 2차 완성 이후 블로그에 올릴 생각입니다.
아무튼 스택, 큐, 덱 1 풀어보았습니다.

요약

제미나이를 사용한 요약본입니다.

• 자료구조 3종 정복: Stack(후입선출), Queue(선입선출), Deque(양방향)의 개념과 C++ STL 활용법을 완벽히 마스터함.
• 문제 해결 인사이트: 괄호 쌍 검사(Stack), 카드/요세푸스(Queue), 풍선 터뜨리기(Deque) 등 상황에 맞는 최적의 자료구조 선택 능력을 배양함.
• 구현 디테일 & 최적화: getline()의 종류별 차이 숙지, 불필요한 연산 제거(2164번), 복잡한 구조 단순화(24511번)를 통해 코드 효율성을 높임.

28278번 스택 2

문제 링크
스택을 배워보는 문제입니다. 그 전에 스택에 대하여 배워보겠습니다.

스택(Stack)

이미지 출처
스택이란 마지막에 저장한 데이터를 먼저 꺼내는 후입선출(LIFO, Last-In, First-Out) 방식의 자료구조입니다.
접시를 쌓는 것처럼 한쪽 끝에서만 입출력이 이루어지며 뒤로 가기 등에 사용되는 구조입니다.
Push 연산으로 데이터를 삽입하고 Pop 연산으로 데이터를 삭제할 수 있습니다.
Push, Pop 모두 스택 상단인 Top에서 이루어집니다.

C++에는 <stack>이라는 헤더 파일이 존재하며 해당 헤더파일을 포함하면 C++의 STL 중 하나인 stack을 사용할 수 있습니다.

#include <stack>
stack<int> s;

다음과 같은 형태로 선언할 수 있으며 push, pop, top, empty, size 등 다양한 연산이 존재합니다.
각 연산들에 대해서는 문제를 풀며 알아보겠습니다.

해당 문제에서 등장하는 연산은 총 5가지입니다.
1 X: 정수 X를 스택에 넣는다.
push 연산입니다. 스택의 Top에 삽입 연산을 진행합니다.
2: 스택에 정수가 있다면 맨 위의 정수를 빼고 출력한다.
pop 연산입니다. 스택의 Top에 있는 원소를 제거하는 연산입니다.
3: 스택에 들어있는 정수의 개수를 출력한다.
size 연산으로 원소의 개수를 반환합니다.
4: 스택이 비어있으면 1, 아니면 0을 출력한다.
empty 연산으로 스택 내에 원소가 존재하는지를 판단합니다.
5: 스택에 정수가 있다면 맨 위의 정수를 출력한다.
top 연산입니다. 스택의 가장 위에 있는 원소를 반환합니다.

#include <iostream>
#include <stack>
using namespace std;
int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    stack<int> s; int n; cin >> n; while (n--) {
        int f; cin >> f; switch (f) {
        case 1: int x; cin >> x; s.push(x); break;
        case 2:
            if (s.empty()) cout << -1 << '\n';
            else { cout << s.top() << '\n'; s.pop(); } break;
        case 3: cout << s.size() << '\n'; break;
        case 4: cout << s.empty() << '\n'; break;
        case 5: cout << (s.empty() ? -1 : s.top()) << '\n'; break;
        }
    }
}

정답 코드는 다음과 같습니다.

10773번 제로

문제 링크
0이 나오면 전에 들어간 수를 삭제합니다. 전에 들어간 수를 삭제하는 전형적인 스택 문제입니다.

#include <iostream>
#include <vector>
#include <numeric>
using namespace std;
int main() {
    int k; cin >> k; vector<int> v; 
    while (k--) { int n; cin >> n; if (n) v.push_back(n); else v.pop_back(); }
    cout << accumulate(v.begin(), v.end(), 0);
}

저는 이 문제를 vector의 push_back(), pop_back()을 사용하여 stack처럼 구현해보았습니다.
또한 vector에 저장된 모든 값의 합을 구하기 위해 <numeric> 헤더의 accumulate 함수를 사용하였습니다.
accumulate(시작, 끝, 초기값, [연산]) 형식으로 작성합니다.
연산은 작성하지 않으면 기본적으로 합산이 진행됩니다.

9012번 괄호

문제 링크
모든 괄호가 쌍이라면 통과입니다.

(((

이런 식으로 괄호가 쌓여있을 때

((()

닫히는 괄호가 들어오면 맨 뒤에 있던 괄호와 쌍이 되어 사라집니다.
따라서 한 곳에서만 삽입, 삭제가 이루어지는 것을 볼 수 있고 해당 문제 또한 스택을 이용하여 풀 수 있는 것을 알 수 있습니다.

#include <iostream>
#include <stack>
#include <string>
using namespace std;
int main() {
    int t; cin >> t; while (t--) {
        string s1; stack<char> s2; cin >> s1;
        for (char c : s1) {
            if (s2.empty()) s2.push(c);
            else {
                if (s2.top() == '(' && c == ')') s2.pop();
                else s2.push(c);
            }
        } cout << (s2.empty() ? "YES" : "NO") << '\n';
    }
}

여는 괄호가 나오면 push, 닫는 괄호가 나왔고 top이 여는 괄호라면 쌍이 되어 pop을 진행합니다.
스택에 원소가 없다면 push를 진행한다는 뜻은 여는 괄호를 삽입하는 것도 있지만,
맨 처음에 닫는 괄호가 나왔을 시 짝 지어지는 괄호를 찾을 수 없으므로 스택에 삽입하여 해당 문자열이 오답으로 판단되게 합니다.

4949번 균형잡힌 세상

문제 링크
9012번 문제와 비슷한 문제이지만 괄호의 종류가 1개에서 2개로 늘었고 괄호가 아닌 문자들이 포함되어 있습니다.
하지만 위의 코드를 응용하여 쉽게 풀 수 있습니다.

#include <iostream>
#include <stack>
#include <string>
using namespace std;
int main() {
    while (1) {
        string s; getline(cin, s); if (s == ".") break;
        stack<int> t; for (char c : s) { 
            if (c == '(' || c == '[') t.push(c);
            else if (c == ')') {
                if (t.empty() || t.top() != '(') { t.push(c); break; }
                else t.pop();
            }
            else if (c == ']') {
                if (t.empty() || t.top() != '[') { t.push(c); break; }
                else t.pop();
            } 
        } cout << (t.empty() ? "yes" : "no") << '\n';
    }
}

문자열 구분 조건은 공백이 아닌 줄바꿈입니다.
따라서 공백이 아닌 줄바꿈을 단위로 입력 받을 수 있는 getline() 함수가 필요합니다.
getline() 함수는 두 가지가 있습니다. 코드에 대한 설명 이후 아래서 설명하도록 하겠습니다.
열린 괄호라면 스택에 넣습니다.
닫힌 괄호이고 스택의 탑이 해당 괄호와 쌍이라면 pop을 진행합니다.
쌍이 아니거나 스택이 비어있다는 것은 해당 괄호와 쌍인 괄호가 존재하지 않는다는 뜻입니다.
따라서 이후 오답으로 판단하기 위해 push 합니다.

cin.getline()

char* 형의 문자열을 받을 수 있습니다.

#include <iostream>
using namespace std;
int main() { char t[10]; cin.getline(t, 10); }

cin.getline(char*, 범위)은 범위를 지정하여 입력 받습니다.
범위를 지정할 때 마지막 칸은 \n이 들어가므로 사용할 칸 + 1칸의 여유를 두고 사용해야 합니다.
char* 형의 문자열을 입력 받기 때문에 string의 경우에는 에러가 발생합니다.

getline()

<string> 헤더 내에도 getline() 함수가 존재하며 해당 코드에서 사용한 함수가 이 함수입니다.

#include <iostream>
#include <string>
using namespace std;
int main() { string t; getline(cin, t); }

string형을 받을 수 있으며 getline(cin, string) 형태로 사용합니다.
string형을 사용하기 때문에 char* 형을 사용하는 cin.getline()과는 다르게 범위를 지정하지 않아도 됩니다.
또한 \n를 구분자로 받아들인 뒤 버퍼에서 삭제해 string 내에는 \n이 남지 않습니다.

도키도키 간식드리미

문제 링크
스택에 관한 마지막 문제입니다.
스택과 배열, 두 가지 자료구조를 사용하여 풀어야 하는 문제입니다.

처음 줄을 서있는 공간은 일반 배열입니다.
번호를 입력 받아 입력 받은 순서대로 나가는데, 선입선출 방식이라 다시 보니 큐로 구현하는 것이 더 나았을 것 같습니다.
잠깐 대기할 수 있는 공간은 마지막에 들어간 사람이 먼저 나가는 선입후출의 스택입니다.
따라서 조건에 따라 배열에서 바로 나가거나, 배열에서 스택을 거친 뒤 나가는 방식으로 해당 문제를 풀 수 있겠습니다.
아래는 정답 코드입니다.

#include <iostream>
#include <vector>
#include <stack>
using namespace std;
int main() {
    int n, i = 0, c = 1; cin >> n;
    vector<int> v(n); for (int j = 0; j < n; ++j) cin >> v[j];
    stack<int> s; while (i < n || !s.empty()) {
        if (!s.empty() && s.top() == c) { s.pop(); c++; }
        else if (i < n) {
            if (v[i] == c) { c++; i++; }
            else s.push(v[i++]);
        } else break;
    } cout << (c - 1 == n ? "Nice" : "Sad");
}

배열은 배열 내의 원소를 직접 삭제하는 게 아닌 인덱스 i를 통해 제어하였습니다.
인덱스 i는 현재 배열의 위치를 저장합니다.
또 c는 받을 학생의 번호를 나타냅니다.
반복 조건은 배열과 스택 모두 비어있다면 모든 학생이 간식을 받았다는 뜻이므로 종료합니다.
배열을 직접 삭제하는 것이 아닌 인덱스로 제어하고 있으므로 배열이 비는 조건은 i < n으로 설정합니다.

반복문 안을 살펴보면 두 조건이 있습니다.
스택의 top이 현재 순서라면 스택을 빠져나오고 현재 순서를 증가시킵니다.
스택이 비어있는데 top에 접근하면 오류가 발생하므로 top을 가져오기 전 스택이 비어있지는 않은지 판단합니다.

!s.empty() && s.top() == c

해당 순서대로 조건을 작성했다면 스택이 비어있을 때 !s.empty()가 0을 반환하면서 && 특성상 뒤의 s.top() == c을 계산하지 않고 바로 0을 반환합니다.

i < n라면, 즉 현재 인덱스가 배열 내의 인덱스라면 배열이 아직 비어있지 않다는 뜻으로 배열을 확인해야 합니다.
배열의 맨 앞 학생이 현재 순서라면 인덱스를 증가시켜 학생이 나간 것처럼 합니다.
그리고 현재 순서를 증가시킵니다.
현재 순서가 아니라면 맨 앞 학생을 스택으로 옮깁니다. 동시에 인덱스도 진행시켜야 합니다

그 어디에도 해당하지 않는다면, 즉 배열이 비었고 스택의 top이 현재 순서가 아닌 상황입니다.
해당 상황에서는 더 진행하더라도 스택에 남은 모든 사람이 간식을 받을 수 없습니다.
따라서 반복문을 종료합니다.

반복문이 정상적으로 종료되었다면 현재 순서가 총 인원 + 1 명에 스택은 비어있을 것입니다.
총 인원 + 1인 이유는 마지막 학생이 나가며 현재 순서가 증가 되기 때문입니다.

c - 1 == n ? "Nice" : "Sad"

따라서 해당 조건으로 판단할 수 있지만

s.empty() ? "Nice" : "Sad"

이 조건으로 작성하여도 정답입니다.
제 개인적인 생각으로는 아래 조건이 좀 더 직관적으로 보입니다.

추가로 큐를 통해서도 구현해보았습니다.

#include <iostream>
#include <stack>
#include <queue>
using namespace std;
int main() {
    queue<int> q; int n, c= 1; cin >> n; for (int i = 0; i < n; ++i) { int t; cin >> t; q.push(t); }
    stack<int> s; while (!q.empty() || !s.empty()) {
        if (!s.empty() && s.top() == c) { s.pop(); c++; }
        else if (!q.empty()) {
            if (q.front() == c) { q.pop(); c++; }
            else { s.push(q.front()); q.pop(); }
        } else break;
    } cout << (c - 1 == n ? "Nice" : "Sad");
}

로직은 배열을 사용한 로직과 전부 동일하므로 따로 설명은 하지 않겠습니다.
큐에 대한 설명은 아래서 하도록 하겠습니다.

18258번 큐 2

문제 링크
큐를 배워보는 문제입니다. 큐에 대해서 짧게 설명을 해보자면

큐(Queue)

이미지 출처
큐란 가장 먼저 들어온 데이터가 가장 먼저 나가는 선입선출(FIFO, First-In, First-Out) 자료구조로 대기열에 주로 사용됩니다.
데이터 추가는 Enqueue라고 하며 Rear라는 맨 뒤에서 진행됩니다.
데이터 삭제는 Dequeue라고 하며 Front라는 맨 앞에서 진행됩니다.

C++에는 <queue>이라는 헤더 파일이 존재하며 해당 헤더파일을 포함하면 C++의 STL 중 하나인 queue 사용할 수 있습니다.

#include <queue>
stack<queue> q;

다음과 같은 형태로 선언할 수 있으며 push, pop, front, back, empty, size 등 다양한 연산이 존재합니다.
각 연산들에 대해서는 문제를 풀며 알아보겠습니다.

해당 문제에 등장하는 연산은 총 6가지입니다.

1. push X: 정수 X를 큐에 넣는 연산이다.
2. pop: 큐에서 가장 앞에 있는 정수를 빼고, 그 수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
3. size: 큐에 들어있는 정수의 개수를 출력한다.
4. empty: 큐가 비어있으면 1, 아니면 0을 출력한다.
5. front: 큐의 가장 앞에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
6. back: 큐의 가장 뒤에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.

이 연산들 모두 c++의 queue의 기본 함수 이름과 동일하기 때문에 함수에 관해서는 따로 설명하지 않고 넘어가도록 하겠습니다.

#include <iostream>
#include <queue>
#include <string>
using namespace std;
int main() {
    ios::sync_with_stdio(0); cin.tie(NULL);
    queue<int> q; int n; cin >> n; while (n--) {
        string s; cin >> s; 
        if (s == "push") { int t; cin >> t; q.push(t); }
        else if (s == "pop") { 
            if (q.empty()) cout << "-1\n";
            else { cout << q.front() << '\n'; q.pop(); }
        }
        else if (s == "size") { cout << q.size() << '\n'; }
        else if (s == "empty") { cout << q.empty() << '\n'; }
        else if (s == "front") { 
            if (q.empty()) cout << "-1\n"; 
            else cout << q.front() << '\n'; 
        }
        else if (s == "back") { 
            if (q.empty()) cout << "-1\n";
            else cout << q.back() << '\n'; 
        }
    }
}

정답 코드는 다음과 같습니다.

2164번 카드2

문제 링크
큐를 다루는 문제입니다.
홀수 턴이라면 pop, 짝수턴이라면 가장 위에 있는 카드를 push, 이후 pop을 진행하는 문제입니다.

정답 코드를 소개하기 전 처음 제가 작성한 코드입니다.

while (q.size() != 1) { if (c % 2 == 0) q.push(q.front()); q.pop(); c++; }

턴을 기록하며 짝수 턴에만 push 연산을 진행합니다.
하지만 결론적으로 해당 조건문은 필요하지 않습니다.
예를 들어 보도록 하겠습니다. 만약 카드의 초기 상태가 다음과 같다면

1 2

제일 위에 있는 카드를 버리면(pop) 다음과 같습니다.

2

최종적으로 남은 카드는 2지만 다음 턴을 진행한다면

2 2

front의 카드를 push

2

이후 pop을 진행하면 해당 턴을 진행하기 전과 결과가 같습니다.
따라서

while (q.size() != 1) { q.pop(); q.push(q.front()); q.pop(); } 

이렇게 작성하여도 같은 결과가 나오게 됩니다.
매 턴마다 홀수인지를 검사하지 않으므로 홀짝을 검사하는 코드보다 4s 빠릅니다.

#include <iostream>
#include <queue>
using namespace std;
int main() {
    int n; cin >> n; queue<int> q; for (int i = 1; i <= n; ++i) q.push(i);
    while (q.size() != 1) { q.pop(); q.push(q.front()); q.pop(); } cout << q.front();
}

정답 코드는 다음과 같습니다.

11866번 요세푸스 문제 0

문제 링크
k번째로 계속 이동하며 그 위치에 있는 사람을 없앱니다.
k 전까지는 front를 push, pop 하다가 k번째에 출력 후 pop 해주면 됩니다.

#include <iostream>
#include <queue>
using namespace std;
int main() {
    int n, k; cin >> n >> k; queue<int> q; for (int i = 1; i <= n; ++i) q.push(i);
    cout << '<'; while (!q.empty()) {
        for (int i = 0; i < k - 1; ++i) { q.push(q.front()); q.pop(); }
        cout << q.front(); if (q.size() > 1) cout << ", "; q.pop();
    } cout << '>';
}

문제에서 요구하는 출력 형식 때문에 중간 중간 , 를 출력해야 합니다.

28279번 덱 2

문제 링크
덱을 배우는 문제입니다.

덱(deque)

이미지 출처
덱 또는 데크는 Double-Ended Queue의 약자입니다.
쉽게 말해 스택과 큐를 합쳐 놓은 형태로 양방향 데이터 추가, 삭제가 가능한 유연한 구조를 하고 있습니다.

C++에는 <deque>이라는 헤더 파일이 존재하며 해당 헤더파일을 포함하면 C++의 STL 중 하나인 deque을 사용할 수 있습니다.

#include <deque>
deque<int> s;

다음과 같은 형태로 선언할 수 있으며 push_front/back, pop_front/back, front, back, empty, size 등 다양한 연산이 존재합니다.
queue 기본 함수와 비슷하나 양방향 삽입/삭제에 대해 차이점이 존재합니다.
각 연산들에 대해서는 코드를 보면 이해될 것이므로 더 설명하지는 않겠습니다.

#include <iostream>
#include <deque>
using namespace std;
int main() {
    ios::sync_with_stdio(0); cin.tie(NULL);
    int n; cin >> n; deque<int> dq; while (n--) {
        int c; cin >> c; switch (c) {
        case 1: int x; cin >> x; dq.push_front(x); break;
        case 2: int y; cin >> y; dq.push_back(y); break;
        case 3: if (dq.empty()) cout << "-1\n"; else { cout << dq.front() << '\n'; dq.pop_front(); } break;
        case 4: if (dq.empty()) cout << "-1\n"; else { cout << dq.back() << '\n'; dq.pop_back(); } break;
        case 5: cout << dq.size() << '\n'; break;
        case 6: cout << dq.empty() << '\n'; break;
        case 7: cout << (dq.empty() ? -1 : dq.front()) << '\n'; break;
        case 8: cout << (dq.empty() ? -1 : dq.back()) << '\n'; break;
        }
    }
}

정답 코드입니다.

2346번 풍선 터뜨리기

문제 링크
앞뒤로 데이터를 움직여야 하는 문제로 덱을 사용하는 것이 적절한 문제입니다.

먼저 풍선에 적힌 숫자가 담긴 덱, 풍선의 번호가 담긴 덱 두 개를 준비합니다.

매 턴마다 맨 앞, front의 풍선을 pop 하겠습니다.
숫자는 출력하고 번호만큼 push를 진행합니다.

현재 상태입니다.
따라서 이제 4번 풍선을 pop 해야 합니다.

앞의 두 풍선을 push_back 하면 4번이 앞으로 오므로 4번을 pop 할 수 있게 됩니다.

4번이 front이므로 pop_front, 이후 해당 숫자인 -3만큼 움직이겠습니다.

음수인 경우에는 뒤의 것을 앞으로, push_front를 진행합니다.
세 개가 있으므로 세 개를 push_front 합니다.

해당 작업을 덱이 빌 때까지 반복하면 됩니다.
살펴본 과정에서 숫자가 양수라면 앞의 것 n-1개를 push_back, 음수라면 뒤의 것 n개를 push_front 하고 있다는 것을 알 수 있습니다.
이를 기반으로 구현한 코드는 다음과 같습니다.

#include <iostream>
#include <deque>
using namespace std;
int main() {
    int n; cin >> n; deque<int> idx; for (int i = 1; i <= n; ++i) idx.push_back(i);
    deque<int> num; for (int i = 0; i < n; ++i) { int t; cin >> t; num.push_back(t); }
    while (1) {
        cout << idx.front() << ' '; idx.pop_front();
        int t = num.front(); num.pop_front();
        if (idx.empty()) break;
        if (t > 0) { 
            for (int i = 0; i < t - 1; ++i) {
                idx.push_back(idx.front()); idx.pop_front();
                num.push_back(num.front()); num.pop_front();
            }
        } else {
            for (int i = 0; i < -t; ++i) {
                idx.push_front(idx.back()); idx.pop_back();
                num.push_front(num.back()); num.pop_back();
            }
        }
    }
}

24511번 queuestack

문제 링크
한 구조 내에 queue의 성질을 띈 데이터, stack의 성질을 띈 데이터가 섞여 있습니다.
하지만 queue 성질을 띈 데이터만 신경 쓰면 되는 어렵지 않은 문제입니다.

queue는 선입선출으로 데이터가 들어가면 값이 교환됩니다.

하지만 stack은 후입선출으로 들어온 데이터가 다시 나갑니다.

따라서 예제의 첫 번째 원소 삽입 상태는 다음과 같은데

스택은 모두 무시하면 큐의 일반적인 삽입/삭제와 동일해집니다.

#include <iostream>
#include <deque>
using namespace std;
int main() {
    ios::sync_with_stdio(0); cin.tie(NULL);
    int n, m; cin >> n; bool* a = new bool[n]; for (int i = 0; i < n; ++i) cin >> a[i];
    deque<int> dq; for (int i = 0; i < n; ++i) { int b; cin >> b; if (!a[i]) dq.push_back(b); }
    cin >> m; for (int i = 0; i < m; ++i) {
        int c; cin >> c; dq.push_front(c); cout << dq.back() << ' '; dq.pop_back();
    }
}

따라서 큐인 경우에만 덱에 삽입하고 스택은 무시합니다.
이후 들어오는 수들을 push_front, pop_back 하면 됩니다.