Unreal TIL 16일차 - C++ STL Stack/Queue

yys·2026년 3월 18일

내배캠 TIL

TIL

목록 보기

13/76

Stack

후입선출(Last In First Out)의 구조를 지니는 자료구조이다.
마치 상자 안에 있는 물건들을 정리할 때, 맨 위에서부터 먼저 빼서 정리하는 것과 유사하다.

아래는 간단하게 표현한 스택 과정이다.

STL에서 제공하는 stack 라이브러리를 활용하는 예시는 아래와 같다.

#include <stack>
#include <string>

using namespace std;

int main() {
    // 스택 컨테이너 생성
    stack<int> s1;
    stack<int> s2;

    // 1. empty(): 스택이 비어있는지 확인 (비어있으면 true 반환)
    bool is_empty = s1.empty(); // is_empty = true

    // 2. push(): 스택의 맨 위에 원소를 복사하여 추가
    s1.push(10); // s1 상태: [10] (Top)
    s1.push(20); // s1 상태: [20, 10]
    s1.push(30); // s1 상태: [30, 20, 10]

    // 3. emplace(): push와 동일한 역할이나, 스택 내부 메모리에서 직접 객체를 생성하여 추가
    s1.emplace(40); // s1 상태: [40, 30, 20, 10]

    // 4. size(): 스택에 보관된 원소의 총 개수를 반환
    int stack_size = s1.size(); // stack_size = 4

    // 5. top(): 스택의 맨 위 원소에 접근 (제거하지 않음)
    int top_element = s1.top(); // top_element = 40
    
    // top()은 참조(Reference)를 반환하기 때문에 값 수정 가능
    s1.top() = 45; // s1 상태: [45, 30, 20, 10]

    // 6. pop(): 스택의 맨 위 원소를 제거
    s1.pop(); // s1 상태: [30, 20, 10]
    s1.pop(); // s1 상태: [20, 10]

    // 7. swap(): 두 스택의 내용물을 통째로 교환
    s2.push(999); // s2 상태: [999]
    
    s1.swap(s2); 
    // swap 실행 후 상태:
    // s1: [999]
    // s2: [20, 10]

    return 0;
}

여기서 push와 emplace의 차이는 객체를 다루는 데 있어 드러나는데,
객체를 복사한 뒤 스택에 넣냐 vs 인자만 넘기고 스택에서 객체를 생성하냐 의 차이이다.

#include <iostream>
#include <stack>
#include <string>

using namespace std;

class Player {
public:
    string job;
	
    // 생성자
    Player(string n) 
        : job(n)
    {
        cout << "생성자 호출: " << job << endl;
    }

    // 복사 생성자
    Player(const Player& other) : job(other.job) 
    {
        cout << "복사 생성자 호출: " << job << endl;
    }
};

int main() {
    stack<Player> s;

    s.push(Player("Knight"));
    s.emplace("Mage");

    return 0;
}

// 결과
생성자 호출: Knight
복사 생성자 호출: Knight
생성자 호출: Mage

위 코드의 결과처럼, emplace의 경우 stack 내부에서 객체를 생성하기 때문에 복사 생성자가 호출되지 않는다.
그렇기 때문에 객체의 복사 비용이 크다면, emplace를 쓰는 것도 고려해봐야 한다.
(이는 아래에서 설명할 Queue에도 동일하게 적용된다.)

stack의 모든 연산들은 O(1)에서 처리된다.

Queue

선입선출(First In First Out)을 쓰는 자료구조이다.
좁은 에스컬레이터를 먼저 타면 먼저 다음 층에 도달하는 것과 유사하다.

아래는 간단하게 표현한 큐 과정이다.

STL에서 제공하는 queue 라이브러리를 활용하는 예시는 아래와 같다.

#include <queue>
#include <string>

using namespace std;

int main() {
    // 큐 컨테이너 생성
    queue<int> q1;
    queue<int> q2;

    // 1. empty(): 큐가 비어있는지 확인 (비어있으면 true 반환)
    bool is_empty = q1.empty(); // is_empty = true

    // 2. push(): 큐의 맨 뒤에 원소를 복사하여 추가
    q1.push(10); // q1 상태: [10]
    q1.push(20); // q1 상태: [10, 20] 
    q1.push(30); // q1 상태: [10, 20, 30] 

    // 3. emplace(): push와 동일하나, 큐 내부 메모리에서 직접 객체를 생성하여 맨 뒤에 추가
    q1.emplace(40); // q1 상태: [10, 20, 30, 40] 

    // 4. size(): 큐에 보관된 원소의 총 개수를 반환
    size_t queue_size = q1.size(); // queue_size = 4

    // 5. front(): 큐의 맨 앞 원소에 접근 (제거하지 않음)
    int front_element = q1.front(); // front_element = 10
    
    // 6. back(): 큐의 맨 뒤 원소에 접근 (제거하지 않음)
    int back_element = q1.back(); // back_element = 40
    
    // front()와 back()은 참조를 반환하기 때문에 값을 직접 수정할 수 있음
    q1.front() = 15; // q1 상태: [15, 20, 30, 40]
    q1.back() = 45;  // q1 상태: [15, 20, 30, 45]

    // 7. pop(): 큐의 맨 앞 원소를 제거
    q1.pop(); // q1 상태: [20, 30, 45]
    q1.pop(); // q1 상태: [30, 45]

    // 8. swap(): 두 큐의 내용물을 통째로 교환
    q2.push(999); // q2 상태: [999] 
    
    q1.swap(q2); 
    // swap 실행 후 상태:
    // q1: [999] 
    // q2: [30, 45] 

    return 0;
}