[Rank 5] ft_containers - std::stack

stack

는 무엇인가

#include <vector>

int main(void) {
    std::stack<int> stack1; // 정수형 컨테이너, 용량 0으로 초기화
    std::stack<std::string> stack2(5); // 문자열 컨테이너, 용량 5로 초기화
}

보통 자료구조를 배우다 보면 배열과 연결 리스트를 배운 뒤 스택, 큐를 필수적으로 다루게 된다

그 때 배운 그 스택이 맞다! 입출구가 단 하나인, LIFO (Last in First Out) 속성의 그 스택이다

LIFO 에서 알 수 있듯이, 스택은 요소를 넣을 수 있는 입구가 제한적이고, 그 말인 즉슨 스택을 구현할 때는 원소를 중간에 끼워넣거나 중간의 원소를 삭제하는 등의 연산을 고려할 필요가 없다는 뜻이다

벡터의 구현에 비하면 굉장히 짧은 구현량을 가지고 있다 (아싸)

눈여겨볼 만한 점

• underlying container 라는 것을 가진다
  • 쉽게 말해 원본이 되는 컨테이너를 골라, 해당 컨테이너를 이용해서 스택을 구현하게 된다
  • push_back, pop_back, empty, size, back 메서드는 내부적으로 underlying container의 메서드를 이용해서 동작하므로, underlying container는 해당 연산들을 지원해 주어야 한다
  • 또한 스택의 특성상, underlying container는 순차 컨테이너여야 한다
  • 위의 모든 조건을 만족하는 (underlying container가 될 수 있는) 컨테이너로는 deque, vector, list가 있으며, <stack> 헤더 (gcc 시스템 헤더) 내부에는 덱이 default underlying container로 지정되어 있다
  • 사실상 스택은 underlying container 에 껍데기를 씌운 것임을 알 수 있다
• C++98 기준, 생성자가 두 종류밖에 없다
  • 기본 생성자, 복사 생성자의 두 종류만이 존재한다
  • 데이터를 뒤에서부터 push 하는 스택의 특성상, 생성자 단계에서 크기를 지정하지 않기 때문에 그런 듯
  • C++11부터는 반복자를 받아서 데이터를 복사하는 생성자 등이 추가되긴 한다
• 맨 위 (top) 요소만 다룰 수 있다
  • [] 연산자 오버로드나 at 등의 메서드가 일절 존재하지 않는다
• 스택은 벡터와 달리 underlying container 에서 대부분의 연산을 지원해 주므로, 멤버 자료형이나 멤버 변수, 메서드가 전반적으로 적다
  • 직접 구현하는 사람 입장에선 완전 이득이라는뜻. 아싸

템플릿 인자

template <class T, class Container = deque<T> > class stack;

T

스택 내부에 저장될 요소의 자료형이다 (벡터와 마찬가지로 int, char 등이 올 수 있다)

Container

벡터와 다르게 Allocator 를 받지 않고 Container 를 받는다

이 Container가 앞서 살펴보았던 underlying container 가 들어가는 부분이다

Allocator는 underlying container 의 템플릿 인자로 들어가므로 스택에서는 생략된다

Container 에서는 underlying container 의 템플릿 인자 또한 함께 정의한다

멤버 자료형 정의

value_type

템플릿 인자로 들어오는 T 의 alias 이다

container_type

템플릿 인자로 들어오는 Container 의 alias 이다

size_type

할당자 객체의 내부에서 사용되는 size_type 의 alias 이다

부호 없는 정수형으로, 할당자가 할당하는 메모리 포인터의 단위를 나타낸다

멤버 변수

내부 구현을 어떻게 하는지에 따라 달라질… 수 있지만 대부분은 underlying container 에서 지원해주므로 스택이 갖고 있어야 할 값이 많지 않다

_container

스택의 베이스가 되는 underlying container 의 인스턴스다

사실 실제로 값이 저장되는 곳은 스택 본체가 아닌 _container 에서 관리하며, 스택은 내부적으로 _container 의 멤버 함수 등을 이용하여 연산을 수행한다

벡터에서는 멤버 변수를 잔뜩 정의해야 했지만, 스택에서는 _container 가 이미 멤버 변수를 들고 있기 때문에 추가적으로 선언할 필요가 없다

멤버 함수 - 생성자와 소멸자

기본 생성자 (default constructor)

explicit stack (const container_type& container = container_type());

• 기본 생성자는 underlying container 인스턴스를 인자로 받는다
  • 다른 컨테이너에서 Allocator 타입의 할당자를 인자로 받았던 것과 비슷하다
• 만약 인자가 들어오지 않았을 경우, container_type 의 생성자를 호출하여 underlying container 를 바로 지정하므로, 실질적으로 인자를 받을 필요가 없다
  • container_type 가 아닌 다른 컨테이너를 underlying container 로 지정하고 싶을 때만 넣어주면 될 듯

복사 생성자 (copy constructor)

stack (const stack& instance);

• 기존 스택 인스턴스를 인자로 받고, 내용물을 그대로 복사해서 새로운 스택을 생성한다
• 벡터의 복사 생성자와 마찬가지로 두 스택의 내용물의 순서는 같다
• 내부적으로는 underlying container 를 복사한다
  • 사실상 스택을 복사한다기보단 underlying container 를 복사하는 것이 정확할듯

멤버 함수 - 대입 연산자 오버로드

operator=

stack& operator= (const stack& instance);

• = 연산자 기준, 우측에 있는 스택을 좌측의 스택에 그대로 복사한다
• 위의 복사 생성자와 마찬가지로 사실상 underlying container 를 복사하는 것과 마찬가지
  • 따라서 underlying container 의 복사 대입 연산자나 복사 생성자가 호출된다
  • (물론 다르게 구현해도 상관 없음)

멤버 함수 - 요소 접근자 관련

top

value_type& top ();
const value_type& top () const;

• 스택의 맨 위 (top) 요소를 반환한다
  • LIFO 특성에 의거하여 맨 마지막에 push된 요소가 top이 된다
• 벡터와 다르게, 특정 위치에 있는 요소를 가져오는 접근자는 없고, top 에만 접근할 수 있다
• 내부적으로 underlying container의 back을 호출한다
  • 위에서 언급했듯 underlying container 는 back 메서드를 지원해야 하고, 그 이유가 여기서 나온다

멤버 함수 - 용량 관련

empty

bool empty () const;

• 스택이 비었는지 아닌지를 bool으로 (true / false) 반환한다
• 내부적으로 underlying container의 empty를 호출한다
  • 마찬가지로 underlying container가 empty를 지원해야 하는 이유이기도 하다
  • 사실 size만 지원해도 size == 0 쓰면 되지 않나? 싶기도 하다

size

size_type size () const;

• 스택의 크기 (원소의 개수) 를 반환한다
• 내부적으로 underlying container의 size를 호출한다
  • 스택의 모든 요소는 사실상 underlying container에 들어가 있기 때문에 해당 컨테이너의 size를 호출한다
  • 마찬가지로 underlying container가 size를 지원해야 하는 이유이기도 하다

멤버 함수 - 수정 관련

push

void push (const value_type& val);

• 스택의 맨 뒤 (top) 에 요소 val을 추가하고, size를 1 늘린다
• 내부적으로 underlying container의 push_back을 호출한다
  • 늘어나는 size는 사실상 underlying container의 사이즈
• 새로운 요소는 val을 복사한 값이 들어간다고 한다

pop

void pop ();

• 스택의 맨 뒤 (top) 요소를 삭제하고, size를 1 줄인다
  • top 요소라 함은 top() 메서드를 호출했을 때 반환받는 값을 가리킨다
• 내부적으로 underlying container의 pop_back을 호출한다
  • 줄어드는 size는 사실상 underlying container의 사이즈

비멤버 함수 - 오버로드

• 연산자 오버로드는 사실상 각 스택이 아닌 스택 내부의 underlying container 끼리 비교를 수행한다
  • 내부적으로 underlying container의 연산자 오버로드를 호출하여 비교한다

operator==

bool operator== (const stack& lhs, const stack& rhs);

• lhs (왼쪽 스택) 와 rhs (오른쪽 스택) 가 같은지 비교한다
  • 두 스택이 같을 경우 true, 다를 경우 false

operator!=

bool operator!= (const stack& lhs, const stack& rhs);

• lhs (왼쪽 스택) 와 rhs (오른쪽 스택) 가 다른지 비교한다
  • 두 스택이 다를 경우 true, 같을 경우 false
  • 사실상 == 연산자 오버로드를 거꾸로 뒤집은 것과 같다

operator<

bool operator< (const stack& lhs, const stack& rhs);

• lhs (왼쪽 스택) 와 rhs (오른쪽 스택) 중 오른쪽 스택이 더 큰지 판정한다
  • 오른쪽 스택이 더 클 경우 true, 그 외에 false

operator<=

bool operator<= (const stack& lhs, const stack& rhs);

• lhs (왼쪽 스택) 와 rhs (오른쪽 스택) 중 오른쪽 스택이 더 크거나 같은지 판정한다
  • 오른쪽 스택이 더 크거나 같을 경우 true, 그 외에 false

operator>

bool operator> (const stack& lhs, const stack& rhs);

• lhs (왼쪽 스택) 와 rhs (오른쪽 스택) 중 왼쪽 스택이 더 큰지 판정한다
  • 왼쪽 스택이 더 클 경우 true, 그 외에 false

operator>=

bool operator>= (const stack& lhs, const stack& rhs);

• lhs (왼쪽 스택) 와 rhs (오른쪽 스택) 중 왼쪽 스택이 더 크거나 같은지 판정한다
  • 왼쪽 스택이 더 크거나 같을 경우 true, 그 외에 false

---

참고 자료

https://legacy.cplusplus.com/reference/stack/stack/

https://en.cppreference.com/w/cpp/container/stack