1.9.1 std::stack

앞에서 설명한 것처럼 어댑터는 std::deque, std::vector 같은 다른 컨테이너를 사용하여 구성합니다. std::stack은 보통 std::deque을 기본 컨테이너로 사용합니다. std::stack은 스택이 기본적으로 제공해야 할 기능을 empty(), size(), top(), push(), pop(), emplace() 등의 함수로 제공합니다. push() 함수는 기본 컨테이너의 push_back() 함수를 사용하여 구현되고, pop() 함수는 pop_back() 함수를 사용하여 구현합니다. top() 함수는 기본 컨테이너의 back() 함수를 사용하는데, 이는 스택에서 맨 위에 있는 데이터가 덱 구조에서는 맨 끝에 있는 원소이기 때문입니다. 이처럼 기본 컨테이너의 한쪽 끝에서만 원소의 추가 및 삭제를 수행함으로써 LIFO 특징을 제공합니다.

스택의 구현을 위해 벡터가 아니라 덱을 기본 컨테이너로 사용한다는 점을 기억하십시오. 이는 덱을 사용하면 원소 저장 공간을 재할당할 때 벡터처럼 전체 원소를 이동할 필요가 없기 때문입니다. 그러므로 벡터보다 덱을 사용하는 것이 더 효율적입니다. 그러나 몇몇 경우에는 특정 컨테이너가 더 좋은 효율을 보여줄 수 있으며, 이러한 경우에는 std::stack 객체 생성 시 템플릿 매개변수로 사용할 컨테이너를 지정할 수 있습니다. 예를 들어 std::vector 또는 std::list를 기본 컨테이너로 사용하는 스택을 만들고 싶다면 다음과 같이 코드를 작성합니다.

std::stack<int, std::vector<int>> stk;
std::stack<int, std::list<int>> stk;

스택의 모든 연산은 시간 복잡도가 O(1)입니다. 스택에서 기본 컨테이너로 함수 호출을 전달하는 과정은 컴파일러의 최적화에 의해 모두 인라인(inline) 형식으로 호출될 수 있어서 여기서 발생하는 오버헤드는 없습니다.