스택, 큐, 덱 (BOJ 10828/10845/10866)

10828. 스택

스택이란 쌓는다는 의미로, 선입후출의 원칙이 적용되는 자료구조이다.
스택 라이브러리 <stack>에 들어있는 기본 함수들의 사용법은 다음과 같다.

• stack<자료형> s → ‘s’라는 이름의 해당 자료형의 스택을 선언함

• s.push(a) → 스택 s에 a를 밀어넣음 (단, a는 스택 s와 같은 자료형이어야 함)

• s.pop() → 스택 s의 맨 위에 있는 요소를 꺼냄

• s.top() → 스택 s의 맨 위에 있는 요소를 불러옴

• s.size() → 스택 s의 크기를 불러옴 (비어있을 경우 0)

• s.empty() → 스택 s가 비어있는지 여부를 확인함 (비어있을 경우 true, 즉 1)

다음은 BOJ의 몇몇 문제들을 벡터와 페어를 이용한 풀이들이다.

boj_10828 (2022. 11. 10. 풀이)

#include <iostream>
#include <stack>
#include <string>
using namespace std;

stack<int> s;   // 's'라는 이름의 int 자료형의 스택을 선언함
string a[100001];

int main() {
    int n, k;
    cin >> n;

    for(int i=0; i<n; i++) {
        cin >> a[i];
        if (a[i] == "push") {
            cin >> k;
            s.push(k);  // 스택 s에 정수 k를 밀어넣음
        }
        else if (a[i] == "pop") {
            // 만약 스택 s가 비어있다면, -1을 출력함
            if (s.empty() == true) cout << -1 << "\n";
            // 만약 스택 s가 비어있지 않다면, 
            else {
                cout << s.top() << "\n";    // 스택 s의 맨 위에 있는 요소를 불러와 출력함
                s.pop();    // 스택 s의 맨 위에 있는 요소를 꺼냄
            }
        }
        else if (a[i] == "top") {
            // 만약 스택 s가 비어있다면, -1을 출력함
            if (s.empty() == true) cout << -1 << "\n";
            // 만약 스택 s가 비어있지 않다면, 스택 s의 맨 위에 있는 요소를 불러와 출력함
            else cout << s.top() << "\n";
        }
        else if (a[i] == "size") cout << s.size() << "\n";  // 스택 s의 크기를 출력함
        else if (a[i] == "empty") {
            if (s.empty() == true) cout << 1 << "\n";
            else cout << 0 << "\n";
        }
    }
    return 0;
}

10845. 큐

큐는 일렬로 늘어선 모양새를 뜻하며, 선입선출의 원칙이 적용되는 자료구조이다.
큐 라이브러리 <queue>에 들어있는 기본 함수들의 사용법은 다음과 같다.

• queue<자료형> q → ‘q’라는 이름의 해당 자료형의 큐를 선언함
• q.push(a) → 큐 q에 a를 밀어넣음 (단, a는 큐 q와 같은 자료형이어야 함)
• q.pop() → 큐 q의 맨 앞에 있는(가장 먼저 들어간) 요소를 꺼냄
• q.front() → 큐 q의 맨 앞에 있는(가장 먼저 들어간) 요소를 불러옴
• q.back() → 큐 q의 맨 뒤에 있는(가장 나중에 들어간) 요소를 불러옴
• q.size() → 큐 q의 크기를 불러옴 (비어있을 경우 0)
• q.empty() → 큐 q가 비어있는지 여부를 확인함 (비어있을 경우 true, 즉 1)

boj_10845 (2022. 11. 10. 풀이)

#include <iostream>
#include <string>
#include <queue>
using namespace std;

string a;
queue<int> q;

int main() {
    int n, k;
    cin >> n;

    for(int i=0; i<n; i++) {
        cin >> a;
        if (a == "push") {
            cin >> k;
            q.push(k);  // 큐 q에 정수 k를 밀어넣음
        } else if (a == "pop") {
            // 만약 큐 q가 비어있다면, -1을 출력함
            if (q.empty()) cout << -1 << "\n";
            // 만약 큐 q가 비어있지 않다면, 
            else {
                cout << q.front() << "\n";  // 큐 q의 맨 앞에 있는 요소를 불러와 출력함
                q.pop();    // 큐 q의 맨 앞에 있는 요소를 꺼냄
            }
        } else if (a == "front") {
            // 만약 큐 q가 비어있다면, -1을 출력함
            if (q.empty()) cout << -1 << "\n";
            // 만약 큐 q가 비어있지 않다면, 큐 q의 맨 앞에 있는 요소를 불러와 출력함
            else cout << q.front() << "\n";
        } else if (a == "back") {
            // 만약 큐 q가 비어있다면, -1을 출력함
            if (q.empty()) cout << -1 << "\n";
            // 만약 큐 q가 비어있지 않다면, 큐 q의 맨 뒤에 있는 요소를 불러와 출력함
            else cout << q.back() << "\n";
        } else if (a == "size") cout << q.size() << "\n";   // 큐 q의 크기를 출력함
        else if (a == "empty") {
            if (q.empty()) cout << 1 << "\n";
            else cout << 0 << "\n";
        }
    }
    return 0;
}

10866. 덱

덱이란 double-ended queue의 줄임말로, 양방향에서 요소를 삽입하고 삭제할 수 있는 자료구조이다.
덱 라이브러리 <deque>에 들어있는 기본 함수들의 사용법은 다음과 같다.

• deque<자료형> dq → ‘dq’라는 이름의 해당 자료형의 덱을 선언함
• dq.push_front(a) → 덱 dq의 맨 앞에에 a를 밀어넣음 (단, a는 덱 dq와 같은 자료형이어야 함)
• dq.push_back(a) → 덱 dq의 맨 뒤에 a를 밀어넣음 (단, a는 덱 dq와 같은 자료형이어야 함)
• dq.pop_front() → 덱 dq의 맨 앞에 있는 요소를 꺼냄
• dq.pop_back() → 덱 dq의 맨 뒤에 있는 요소를 꺼냄
• dq.front() → 덱 dq의 맨 앞에 있는(가장 먼저 들어간) 요소를 불러옴
• dq.back() → 덱 dq의 맨 뒤에 있는(가장 나중에 들어간) 요소를 불러옴
• dq.size() → 덱 dq의 크기를 불러옴 (비어있을 경우 0)
• dq.empty() → 덱 dq가 비어있는지 여부를 확인함 (비어있을 경우 true, 즉 1)

그런데, BOJ 10866번 문제에서는 size() 함수를 사용하면 시간 초과가 뜬다. 이는 size() 연산의 처리 방식과 관련이 있는데, size() 연산은 실행할 때마다 해당 자료구조의 처음부터 끝까지 전부 훑고 지나가기 때문이다. 따라서 다음과 같은 형태의 풀이가 요구된다.

boj_10866 (2022. 11. 10. 풀이)

#include <iostream>
#include <string>
#include <deque>
using namespace std;

string a;
deque<int> dq;

int main() {
    int n, k;
    int size = 0;
    cin >> n;

    for(int i=0; i<n; i++) {
        cin >> a;
        if (a == "push_front") {
            cin >> k;
            dq.push_front(k);
            size++;
        } else if (a == "push_back") {
            cin >> k;
            dq.push_back(k);
            size++;
        }
        else if (a == "pop_front") {
            if (dq.empty()) cout << -1 << "\n";
            else {
                cout << dq.front() << "\n";
                dq.pop_front();
                size--;
            }
        } else if (a == "pop_back") {
            if (dq.empty()) cout << -1 << "\n";
            else {
                cout << dq.back() << "\n";
                dq.pop_back();
                size--;
            }
        } else if (a == "front") {
            if (dq.empty()) cout << -1 << "\n";
            else cout << dq.front() << "\n";
        } else if (a == "back") {
            if (dq.empty()) cout << -1 << "\n";
            else cout << dq.back() << "\n";
        } else if (a == "size") cout << size << "\n";
        else if (a == "empty") {
            if (dq.empty()) cout << 1 << "\n";
            else cout << 0 << "\n";
        }
    }
    return 0;
}