004_스택 (std::stack)

스택 (std::stack)

스택(stack)은 컨테이너 어댑터(Container Adapter) 중 하나이다. (deque 기반) stack 은 LIFO(Last-In-First-Out) 구조로 제일 마지막에 넣은 데이터가 처음으로 빠져나온다.

stack 은 제일 상단이 아닌 나머지 원소들의 확인, 변경이 원칙적으로 불가능하다.

stack 에 대한 일반적인 연산의 복잡도는 다음과 같다.

원소의 추가 : O(1)
원소의 제거 : O(1)
제일 상단의 원소 확인 : O(1)

stack 의 사용

stack 헤더파일

#include <stack>

stack의 선언

std::stack<Type> StackName;

stack의 생성자 (편의상 int)

std::stack<int> s;	비어있는 스택 s를 생성
std::stack<int> s2(s1);	스택 s1을 복사하여 스택 s2를 생성

stack의 멤버 함수

std::stack<int> s;

s.push(n)	스택 상단에 원소 n 삽입
s.pop()	스택 상단의 원소를 제거
s.top()	스택 상단 원소의 참조를 반환
s.size()	원소의 개수 반환
s.empty()	스택 s가 비어있으면 `true`를 반환
s2.swap(s1)	s1 스택과 s2 스택을 서로 바꿈

stack의 원소 삽입/삭제

#include <iostream>
#include <stack>

int main() 
{
	std::stack<int> s;
	
	for (int i = 1; i <= 5; ++i)
	{
		s.push(i);
		std::cout << s.top() << std::endl;
	}

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