[STL] 05. std::stack

std::stack은 C++ 표준 라이브러리(STL)에서 제공하는 스택 자료구조를 구현한 클래스다.

스택은 후입선출 (LIFO, Last-In-First-Out) 방식으로 데이터를 관리하는 자료구조로 std::stack 역시 이러한 동작을 한다.

다음은 std::stack의 주요 특징과 사용법이다.

 

 

특징

 

1. 표준 라이브러리의 일부 : std::stack은 C++ STL의 일부이며 <stack> 헤더에 정의되어 있다.

 

2. 스택의 기능 제공 : std::stack은 스택 자료구조의 기능을 제공한다.

즉 데이터를 스택에 넣는(push) 동작과 스택에서 데이터를 빼내는(pop) 동작을 지원한다.

 

3. 컨테이너 어댑터 : std::stack은 다른 시퀀스 컨테이너를 내부적으로 사용해 스택을 구현한다.

따라서 스택의 특성을 그대로 유지하면서 다양한 컨테이너를 사용할 수 있다.

 

 

사용법

 

#include <iostream>
#include <stack>

int main() {

	std::stack<int> stk;

	stk.push(10);	// 10
	stk.push(20);	// 20 <- 10
	stk.push(30);	// 30 <- 20 <- 10
	stk.push(40);	// 40 <- 30 <- 20 <- 10

	stk.pop();	// 30 <- 20 <- 10

	std::cout << stk.top() << std::endl;	// 30

	if (stk.empty()) { //스택이 비었다면 아래의 메시지를 출력

		std::cout << "isEmpty" << std::endl;
	}
}

 

 

 

스택의 주요 멤버 함수와 기능

 

멤버 함수	설명	시간 복잡도
push()	스택에 요소를 추가	O(1)
pop()	스택 맨 위의 요소를 제거	O(1)
top()	스택 맨 위의 요소를 참조	O(1)
empty()	스택이 비어 있는지 확인	O(1)
size()	스택에 저장된 요소의 수를 반환	O(1)

 

std::stack은 컨테이너 어댑터이므로 실제 데이터 저장에는 다른 시퀀스 컨테이너를 사용하며

시간 복잡도는 주로 내부 컨테이너의 동작에 의해 결정된다.

이는 스택 자체의 동작은 O(1)에 수행되지만, 내부 컨테이너에 따라 추가적인 오버헤드가 발생할 수 있음을 의미하며

보통은 std::deque를 내부 컨테이너로 사용하는 경우가 일반적이기에

위의 표에선 std::deque를 내부 컨테이너로 사용한다는 전제 조건으로 시간 복잡도를 작성했다.