스택(Stack)
스택(Stack)
Stack의 사전적 정의는 ‘쌓다’, ‘더미’이다. 상자에 물건을 쌓아 올리듯이 데이터를 쌓는 자료구조라고 할수 있다. Stack은 나중에 들어간것이 먼저 나오게 되는 (Last In First Out)의 형태를 띠는 자료구조이다. 예를들어 프링글스 과자를 생각해보자. 과자를 만들때 과자를 위에서 집어넣었다면 우리가 젤 처음 먹는 과자는 제일 나중에 들어갔던 과자 일것이다.
- LIFO(Last In First Out) 구조
- push(원소삽입), pop(원소삭제), Top(꼭대기 원소확인) 시간복잡도 O(1)
- 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
Comments