4. 스택, 큐 (Stack/Queue)

위의 STL 자료는 유명한 자료구조이므로 잘 학습해 두어야 한다.

1.Stack

이 알고리즘을 활용하기 위해서는 상단에 반드시 #include <stack>을 선언해야 한다.
이 자료구조의 특징은 LIFO(Last In First Out)이다. 즉, 나중에 들어온 것이 먼저 나가는 자료구조이다.

Stack을 사용하는 경우는 일반적으로 LIFO상황에 맞는 유형일 때 많이 사용된다. 물론 vector나 array를 활용해서 사용할 수도 있으나 컴파일 에러 등의 문제를 걱정하지 않아도 된다는 점에서 Stack STL을 사용하는 것이 유리하다.
선언 방법은 "stack<자료형> 변수이름"이다.

사용방법은 다음과 같다.
s.push(value) : 스택에 원소를 추가
s.pop() : 스택의 마지막 원소를 제거 (LIFO이므로 나가는 것은 나중에 온 원소가 지워지게 된다.)
s.top() : 스택의 마지막 원소를 return한다.
s.empty() : 스택이 비어있으면 true, 아니면 false를 반환한다.
s.size() : 스택안에 있는 원소의 개수를 반환

2.Queue

이 알고리즘을 활용하기 위해서는 상단에 반드시 #include <queue>를 선언해야 한다.
이 자료구조의 특징은 FIFO(First In First Out)이다. 즉 먼저 들어온 것이 먼저 나가는 자료구조이다. 줄 서는 것과 유사한 느낌이라고 이해햐면 된다. 단, Stack과 다르게 이 자료구조는 처음과 끝이 열려있는 형태이므로 첫번째와 마지막 원소를 확인하는 것이 가능하다. 물론 내보내는 순서는 FIFO를 반드시 따라야 한다.

Queue를 이용하는 경우는 일반적으로 FIFO상황에 맞는 유형일 때 많이 사용된다. Stack과 마찬가지로 vector나 array를 활용해어 사용할 수도 있으나 컴파일 에러 등의 문제를 걱정하지 않아도 된다는 점에서 Queue STL를 사용하는 것이 유리하다.
선언 방법은 "queue<자료형> 변수이름"이다.


사용방법은 다음과 같다.
q.push(value) :큐에 원소를 추가
q.pop() : 큐의 첫번째 원소를 제거 (FIFO이므로 나가는 것은 먼저 온 원소가 지워지게 된다.)
q.front() : 큐의 첫번째 원소를 return한다.
q.end() : 큐의 마지막 원소를 return한다.
q.empty() : 큐가 비어있으면 true, 아니면 false를 반환한다.
q.size() : 큐 안에 있는 원소의 개수를 반환

스택에 해당하는 쉬운 문제를 간단하게 살펴보면 다음과 같다.

 

이 문제의 경우는 왼쪽부터 차례로 번호를 붙이고 보는 방향은 오른쪽이라는 점에 집중해보자. 즉, 나중에 번호를 붙인 순서와 보는방향이 제일 가깝다. 즉 이 지점에서 스택 유형임을 알아내야 한다. 문제 자체는, 현재 본인의 숫자보다 더 큰 숫자가 나올때까지 pop시키는 과정을 반복하면 된다.

 

위의 알고리즘을 활용하여 코드를 구현한 결과는 다음과 같다.

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>

using namespace std;

int main(void){
    int n;
    cin >> n;
    stack<int> stack_store;

    for(int i = 0; i < n; i++){
        int temp;
        cin >> temp;
        stack_store.push(temp);
    } // data_store

    int max = -1;
    int count = 0;

    for(int i = 0 ; i < n; i++){
        int compare = stack_store.top();
        if (compare > max){
            count += 1;
            max = compare;
        }
        stack_store.pop();
    }

    cout << count << "\n";
    return 0;
}

 

큐에 해당하는 쉬운 문제를 간단하게 살펴보면 다음과 같다.

 

이 문제의 경우는 위의 문제와 다르게 가장 앞에 있는 원소를 먼저 체크하는 자료구조이므로 큐를 활용하는 것이다. 또한, 나중에 들어온 원소들은 뒤로 배치함으로써 이 부분도 FIFO구조를 만족한다. 이러한 부분에서 큐를 활용한다는 느낌을 잡으면 된다.

문제 자체는 그리 어렵지 않다.

 

위의 알고리즘을 활용하여 코드를 구현한 결과는 다음과 같다.

#include <iostream>
#include <string>
#include <algorithm>
#include <stack>
#include <vector>
#include <cstdlib>
#include <queue>

using namespace std;

int main(void){
    int num;
    cin >> num;
    
    for(int i = 0; i < num; i++){
        int n, m;
        cin >> n >> m;
        int count = 1;
        queue<pair<int,int> > data_store;
        for (int j = 0; j < n; j++){
            int temp;
            cin >> temp;
            pair<int, int> temp_store;
            temp_store.first = temp;
            if (j == m){
                temp_store.second = 1; // 문제에서 요구한 m번째를 따로 체크
            }
            else{
                temp_store.second = 0; // Default case setting
            }
            
            data_store.push(temp_store);
        } // store data

        // 문제에서 요구한 케이스가 나올때까지 계속해서 맨 앞을 수정

        while(data_store.size() -1 != 0){
            queue<pair<int,int> > temp = data_store;
            int front = temp.front().first;
            bool check = true;
            
            // Front에 놓인 숫자가 max값인지 확인하는 작업
            for(int j= 0; j < data_store.size() - 1; j++){
                temp.pop();
                if(front < temp.front().first){
                    check = false;
                    break;
                }
            }

            // 맨 앞에 놓인 숫자가 max인 경우

            if (check == true){
                if(data_store.front().second == 1){
                    break; // 맨 앞에 놓인 숫자가 내가 고르고자 하는 수인 경우
                }
                else{
                    data_store.pop();
                    count += 1; // 아닌 경우 >> 나머지 숫자들을 가지고 다시 반복
                }
            }

            // 맨 앞에 놓인 숫자가 max가 아닌 경우

            else{
                pair <int, int> temp_num = data_store.front();
                data_store.pop();
                data_store.push(temp_num); // 맨 앞에 놓인 숫자를 뒤로 배치시킨다.
            }
        }
        cout << count << "\n"; // 문제에서 요구하는 값 출력
    }

    return 0;
}

스택과 큐는 물론 문제풀이 방법 자체로도 의미가 있겠지만, 사고하는 방법 자체를 익힌다는 점에서 훨씬 중요하다.

여러번 복습하도록 하자.