[Algorithm] 스택(Stack) & 큐(Queue)

스택이란?

넣은 순서가 1, 2, 3, 4, 5 라고 한다면, 꺼낼 때 5, 4, 3, 2, 1 순으로 꺼내는 방법인 자료구조(짐 정리 처럼, 가장 나중에 넣은 짐을 가장 먼저 꺼낼 수 있다고 생각하면 편하다)

즉, 입구와 출구가 하나인 경우이다. 일반적으로 알고리즘 문제를 풀 때는 스택을 직접 구현하기 보다는, #include <stack>을 하여 c++ stl 라이브러리를 사용한다.

#include <iostream>
#include <stack>

using namespace std;

int main(void) {
    stack<int> s; // int형 스택 생성

    s.push(7); // 스택에 7 을 넣음
    s.push(10);
    s.push(3);
    s.pop(); // 스택에 가장 마지막에 넣은 요소 꺼내기 
    s.push(8);

    // 스택 내부 데이터들 출력
    while(!s.empty()){ // 스택이 빌 때 까지
        cout << s.top() << ' '; // 스택 가장 위의 요소 출력 
        s.pop(); // 출력 후, 해당 데이터 삭제 
    }
    return 0;
}

7, 10, 3 을 넣고, 3을 뺀다음 8을 다시 넣었기 때문에 결과는 8 10 7이 나온다.

큐란?

넣은 순서가 1, 2, 3, 4, 5 라고 한다면, 꺼낼 때도 넣은 순서대로, 1, 2, 3, 4, 5 순으로 꺼내는 방법인 자료구조(은행 창구 등 선착순을 생각하면 편하다)(First In First Out(FIFO)구조)

즉. 입구와 출구가 각각 있는 것이다. 일반적으로 알고리즘 문제를 풀 때는 스택을 직접 구현하기 보다는, #include <queue>을 하여 c++ stl라이브러리를 사용한다.

#include <iostream>
#include <queue>

using namespace std;

int main(void) {
    queue<int> q; // int형 큐 생성

    q.push(7); // 큐에 7 넣음
    q.push(10);
    q.push(5);
    q.pop(); // 가장 먼저 넣은 요소 삭제
    q.push(3);

    // 큐 출력해보기
    while(!q.empty()){ // 큐가 빌 때 까지
        cout << q.front() << ' '; // 큐의 가장 앞에 있는 값 출력
        q.pop(); // 출력 후 데이터 빼내기
    }

    return 0;
}

7, 10, 5 를 넣고, 7를 빼낸 후, 3을 넣었기 때문에, 10, 5, 3 이 출력된다.