[C++/STL] Stack 정리

C++ 표준 템플릿 라이브러리(STL)에서 제공하는 std::stack은 LIFO(Last In, First Out - 후입선출) 구조를 구현한 컨테이너 어댑터(Container Adapter)이다.

 

Stack의 핵심 개념

• LIFO (Last In, First Out): 가장 마지막에 들어간 데이터가 가장 먼저 나오게 됨
• 제한된 접근: 중간에 있는 원소에 직접 접근할 수 없으며, 오직 가장 위에 있는 원소(Top)만 읽거나 제거할 수 있음. 임의 접근(인덱스 조회) 및 반복자(Iterator)를 통한 순회가 불가능함

 

주요 멤버 함수 및 시간 복잡도

std::stack의 모든 주요 연산은 $O(1)$의 시간 복잡도를 가진다.

 

push(val)	스택의 맨 위에 원소 val을 추가함.	$O(1)$
emplace(args...)	스택의 맨 위에 원소를 직접 생성하여 추가함. (이동/복사 생성자 생략 가능)	$O(1)$
pop()	스택의 맨 위(Top) 원소를 제거함. (값을 반환하지 않음)	$O(1)$
top()	스택의 맨 위(Top) 원소에 대한 참조를 반환함.	$O(1)$
empty()	스택이 비어있는지 여부를 반환함. (true/false)	$O(1)$
size()	스택에 저장된 원소의 개수를 반환함.	$O(1)$
swap(other_stack)	두 스택의 내용을 서로 바꿈.	$O(1)$

 

주의사항: 스택이 비어있는 상태(empty() == true)에서 top()이나 pop()을 호출하면 정의되지 않은 동작(Undefined Behavior) 또는 런타임 에러가 발생하므로, 연산 전에 항상 비어있는지 확인하는게 중요하다.

 

컨테이너 어댑터(Container Adapter)의 비밀

std::stack은 스스로 메모리를 관리하는 독립적인 컨테이너가 아니라, 기존의 컨테이너(vector, deque, list 등)를 래핑하여 스택의 동작 방식(LIFO)만 제공하는 어댑터이다.

• 기본 내부 컨테이너: 아무것도 지정하지 않으면 기본적으로 std::deque를 사용함.
• 내부 컨테이너 변경 방법: 필요에 따라 std::vector나 std::list로 변경하여 선언할 수 있음.

#include <stack>
#include <vector>
#include <list>

std::stack<int> s1;                           // 기본 deque 기반 스택
std::stack<int, std::vector<int>> s2;         // vector 기반 스택
std::stack<int, std::list<int>> s3;           // list 기반 스택

 

왜 기본값이 std::vector가 아닌 std::deque일까?

• std::vector는 동적 배열 크기 재할당 시 전체 원소를 다른 힙 영역으로 복사해야 하는 비용($O(N)$)이 간혹 발생할 수 있다.
• 반면 std::deque는 여러 개의 메모리 블록을 사용하여 재할당 비용이 없고, 양방향 끝에서 빠르게 삽입/삭제가 가능하기 때문에 스택의 연속적인 추가/삭제 성능에 더 유리하다.

 

실전 예제 코드

가장 기본적인 스택의 선언, 삽입, 출력 및 삭제 과정을 보여주는 코드 예제이다.

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

int main() {
    // 스택 선언
    std::stack<std::string> taskStack;

    // 데이터 추가 (push / emplace)
    taskStack.push("작업 1");
    taskStack.push("작업 2");
    taskStack.emplace("작업 3"); // 객체를 내부에서 직접 생성

    std::cout << "현재 스택 크기: " << taskStack.size() << std::endl;

    // 스택 원소 순회하며 출력 및 삭제
    // 스택은 반복자가 없으므로 top()을 확인하고 pop()하는 방식으로 순회해야함.
    while (!taskStack.empty()) {
        std::cout << "현재 Top: " << taskStack.top() << std::endl;
        taskStack.pop(); // 맨 위 원소 제거
    }

    std::cout << "비어있는가? " << (taskStack.empty() ? "예" : "아니오") << std::endl;

    return 0;
}

 

 

push vs emplace 차이점

• push: 이미 생성된 객체의 복사본 또는 이동본을 스택에 추가함.
• emplace: 생성자에 필요한 인자들만 전달하여 스택의 메모리 내부에서 객체를 직접 생성한다. 복사/이동 생성자의 오버헤드가 없어 성능상 이점이 있음.

struct Point {
    int x, y;
    Point(int x, int y) : x(x), y(y) {}
};

std::stack<Point> s;
s.push(Point(1, 2)); // 임시 객체 생성 후 복사/이동 발생
s.emplace(1, 2);     // 내부에서 직접 Point(1, 2) 생성 (더 효율적)

 

 

push의 동작 방식

1. 임시 객체 생성: Point(1, 2) 코드가 실행되면서, 호출한 곳(스택 영역 등)에 임시로 존재하는 Point 객체가 만들어진다.
2. 메모리 할당 및 복사/이동: s.push 함수 내부에서 스택의 새로운 원소를 위한 컨테이너 메모리를 할당한 후, 앞서 만든 임시 객체를 복사(Copy)하거나 이동(Move)하여 컨테이너 내부에 집어넣는다.
3. 임시 객체 소멸: 역할을 다한 임시 객체 Point(1, 2)가 소멸된다.

 

emplace의 동작 방식

 

• 인자 전달: emplace 함수는 객체를 받지 않고, 생성자에 들어갈 재료인 1과 2라는 인자(Argument) 자체를 그대로 전달받는다.
• 내부에서 직접 생성: 스택 내부의 저장 공간(메모리)을 먼저 확보한 뒤, 그 자리에 전달받은 인자 1, 2를 곧바로 집어넣어 Point 객체를 생성한다.
• 의미가 없어지는 동작: s.emplace(Point(1, 2)); $\rightarrow$ (X) emplace의 의미가 없음: push와 동일하게 동작한다.