스택(stack)

개요

• 헤더 파일: <stack>
• STL 컨테이너 어댑터(adapter container): 기본적으로 deque의 기능을 제한하여 만들어진 자료구조.
• 탐색 시간: $O(1)$ (TOP 탐색)
• 요소 추가/삭제: $O(1)$

스택(Stack)은 선형 자료구조이면서 후입선출(Last In First Out, LIFO) 특성을 가지는 자료구조입니다.

후입 선출이란, 마지막에 넣은 것이 먼저 제거되는 특성을 말합니다.

이를테면, 아래가 막혀있는 상자에 너비가 똑같은 물건을 쌓아(stack)두고 빼는 것과 유사합니다.

스택은 매우 단순하지만, 특정 알고리즘에서는 매우 효과적으로 동작하는 자료구조입니다.

스택은 TOP이라는 위치의 데이터에만 접근할 수 있기 때문에, 중간 요소의 순서 변경이 없으므로, 순서를 보장합니다. 또한, 후입선출(LIFO)의 특성으로 인해 어떤 순서를 역순서로 바꾸기에도 매우 유용합니다. (역순서 보장)

1. 스택의 TOP은 항상 최근 데이터를 가리키고 있습니다.
2. 때문에, 삽입시 TOP를 먼저 올려보고 컨테이너가 꽉 찼는지 확인 후 데이터를 삽입합니다.
3. 반대로 삭제시 TOP의 위치를 확인 후 데이터를 삭제한 다음 TOP를 내려 다음 데이터의 상단을 가리킵니다.

C++ 에서의 스택

C++의 <stack>은 기본적으로 <deque>의 기능을 제한하여 만들어진 컨테이너입니다. (벡터, 덱, 리스트 등 다양한 컨테이너를 기반으로 만들 수 있습니다.)

스택은 임의 접근을 허용하지 않을 뿐만 아니라, 이터레이터 또한 허용하지 않습니다. 이는 스택의 LIFO 특성을 유지하기 위함입니다.

스택의 활용

스택은 이러한 순서 보장과 역순서 보장의 특징으로 인해 다양한 알고리즘에서 효과적으로 활용됩니다.

예를 들어, 함수 호출과 복귀(함수는 순서대로 실행되고 종료 시 바로 이전 위치로 돌아가야 합니다.), 표현식 평가(연산자 우선순위 보장 및 표현식 변환 등…), 명령 취소(가장 최근에 실행된 명령 순서대로 취소), 등… 많은 알고리즘에서 효과적으로 동작합니다.

(연산자 우선순위에 대한 이해를 하기 위해서 9012번: 괄호 (acmicpc.net)나 4949번: 균형잡힌 세상 (acmicpc.net)와 같은 코딩테스트 문제가 도움이 될 수 있습니다.)

---

특징

1. TOP에서 빠른 삽입/삭제가 가능하며 TOP을 빠르게 탐색할 수 있는 자료구조입니다.
2. 역순서 보장: 스택은 데이터의 순서를 엄격하게 관리하며, 역순서로 데이터를 처리할 수 있습니다.

장단점

장점

• 간단하고 효율적: 스택은 구현이 간단하며, 특정 알고리즘에서 데이터 처리를 효율적으로 수행할 수 있습니다.
• 빠른 연산: TOP에서의 요소 추가 및 삭제가 $O(1)$의 시간 복잡도를 가집니다.

단점

• 유연성 부족: 스택은 중간 요소에 대한 접근이나 수정이 불가능하여, 일부 알고리즘에는 적합하지 않을 수 있습니다.

(이 외에 스택을 구현한 컨테이너나 방식에 따라 세부적인 장단점이 추가될 수 있습니다.)

---

사용법

생성자

std::stack<typename _Ty, typename _Container> s; // 기본 생성자. 컨테이너를 선택할 수 있습니다.
std::stack<typename _Ty, typename _Container> s(std::_Container<_Ty> _Cont); // 기존의 컨테이너 데이터로 스택을 만듭니다.
std::stack<typename _Ty, typename _Container> s(std::stack<_Container> _Right); // 기존의 스택을 복사합니다.

스택은 기존의 시퀀스 컨테이너와는 달리 컨테이너 어댑터(adapter container)로, 스택을 구현 할 컨테이너를 지정할 수 있습니다.

위 생성자 목록 중 두 번째에 해당하는 기존의 컨테이너 데이터로 스택을 만드는 예제를 보겠습니다.

#include <iostream>
#include <stack>
#include <vector>

int main()
{
	std::vector<int> v = { 1, 2, 3, 4, 5, 6, 7 };
	std::stack<int, std::vector<int>> s(v);

	for (int i = 0; i < 7; i++)
	{
		std::cout << s.top() << std::endl;
		s.pop();
	}
}

스택을 std::vector 컨테이너로 만들고, 매개변수로 기존 std::vector 객체를 넘겨주었습니다.

---

멤버 함수

멤버 함수	설명
s.push(x) / s.pop()	스택의 Top에 요소 x를 삽입하거나 Top 요소를 제거합니다.
s.top()	스택의 Top 요소에 대한 참조를 반환합니다.
s.empty()	스택이 비어있으면 true를 반환합니다.
s.size()	스택에 저장된 요소의 수를 반환합니다.