스택(Stack)

Stack의 사전적 정의는 '쌓다', '더미'이다. 상자에 물건을 쌓아 올리듯이 데이터를 쌓는 자료구조라고 할 수 있다. Stack은 나중에 들어간 것이 먼저 나오게 되는 (Last In First Out)의 형태를 띠는 자료구조이다. 예를 들어 프링글스 과자를 생각해보자. 과자를 만들 때 과자를 위에서 집어넣었다면 우리가 젤 처음 먹는 과자는 제일 나중에 들어갔던 과자 일 것이다.

 

1. LIFO(Last In First Out) 구조
2. push(원소 삽입), pop(원소 삭제), Top(꼭대기 원소 확인) 시간 복잡도 O(1)
3. Stack은 C++ 표준 라이브러리(Standard Template Library)에 있는 정의 되어 있어 필요할 때마다 만들어 사용하지 않고 include 하여 사용하면 된다.

어떻게 사용하는가?

#include <stack> // stack이 포함된 헤더파일

stack<int> s; // int형 스택 선언, 다른 자료형을 넣어도 됨

s.push(x); // 스택에 데이터 x를 입력한다.

s.pop(); //스택의 데이터를 삭제한다.

s.top(); //스택의 꼭대기 데이터를 반환한다.

s.empty(); //스택이 비어 있는지 판단한다.

s.size(); //스택안에 있는 원소의 갯수를 반환

관련 문제

• BOJ 10828 스택 <https://www.acmicpc.net/problem/10828>
• BOJ 9012 괄호 <https://www.acmicpc.net/problem/9012>
• BOJ 1918 후위표기식 <https://www.acmicpc.net/problem/1918>
• BOJ 1935 후위표기식2 <https://www.acmicpc.net/problem/1935>
• BOJ 1725 히스토그램 <https://www.acmicpc.net/problem/1725>
• BOJ 2304 창고다각형 <https://www.acmicpc.net/problem/2304>
• BOJ 2841 외계인의 기타 연주 <https://www.acmicpc.net/problem/2841>
• BOJ 3986 좋은단어 <https://www.acmicpc.net/problem/3986>
• BOJ 5076 Web Pages <https://www.acmicpc.net/problem/5076>