스택 (Stack)

개념

스택은 데이터를 한쪽 끝(Top)에서만 삽입/삭제 가능한 후입선출(LIFO) 자료구조이다.

특징

• 후입선출(LIFO) 방식 나중에 들어간 데이터가 먼저 나오는 후입선출 구조이며, 이를 위해 한쪽 끝(Top)에서만 데이터의 삽입/삭제가 이루어진다.
• 구현 방식 배열이나 연결 리스트로 구현되며, C++ STL에서는 덱을 사용하여 구현되어있다.
• 다양한 활용법 재귀 호출, 함수 호출 관리, 실행 취소 등 후입선출 구조가 필요한 다양한 분야에서 활용할 수 있다.

장점

• 단순한 구조 구조가 단순해 구현이 쉽고, 데이터의 추가 및 제거가 빠르다.

단점

• 임의 접근 불가 Top 이외의 데이터에는 직접 접근할 수 없으며, 이로 인해 중간 데이터에 접근하는 것이 비효율적이다.
• 고정된 크기 (배열 기반 한정) 배열 기반 스택은 크기를 미리 정해야하며, 스택 오버플로우/언더플로우의 위험이 있다.

std::stack

stack은 deque을 기반으로 구성한 후입선출 구조의 컨테이너 어댑터이다.

• empty, size, top, push, pop, emplace 등의 함수를 기본적으로 제공한다.
• push는 push_back, pop은 pop_back, top은 back 함수를 사용하여 구현된다.
• 모든 연산은 O(1)의 시간 복잡도를 가지며, 스택이 기본 컨테이너로 함수 호출을 전달하는 과정은 인라인 형식으로 호출되어 오버헤드가 발생하지 않는다.