백준의 알고리즘 오프라인 강의를 들으면서 지금까지 배웠던 내용들을 간단하게 정리하려고 한다.
스택
-한쪽 끝에서만 자료를 넣고 뺄 수 있는 자료구조이다. 마지막으로 넣은 것이 가장 먼저나오기 때문에
LIFO(Last In First Out)이라고 한다. 스택은 두가지 연산으로 이루어져있는데
-push함수 : 스택에 자료를 넣는 연산
-pop 함수 : 스택에서 자료를 빼는 연산
-top 함수 : 스택의 가장 위에 있는 자료를 보는 연산 (가끔 인덱스와 혼동할 수 있다.)
-size 함수 : 스택에 저장되어있는 자료의 개수 이다. (size이므로 스택의 크기를 생각 할 수 있으나 개수임을 명심하자)
사실 스택 같은경우 자료구조에서 배열이나 연결리스트로 많이들 구현하고는 하는데 문제를 풀거나, 따로 구현해야할땐
해당 언어의 라이브러리를 이용하는것이 낫다고 한다.
스택을 사용하는 이유
스택을 이용하면 결론적으로 연산속도가 월등히 빨라진다. 그 이유론 스택을 배열으로 구현했다고 했을 때,
데이터를 추출하기 위해선 따로 search할 필요 없이 바로 pop이나 top을 이용해 구할 수 있다.
시간복잡도 : O(1)
반면 일반 배열이나 연결리스트같은경우엔 시간복잡도가 O(N)이기 때문에 스택을 이용할 수 있는 문제에서는
절대적으로 스택이 유리하다는 것을 알 수있다.
스택이 사용되는 경우
Last In First Out : 마지막에 들어간 데이터가 기존에 들어간 데이터와 상호작용을 일으키거나 검사에 사용될 때 많이 사용된다.
다음은 스택을 이용하는 문제들이다.
<괄호 문제>
https://www.acmicpc.net/problem/9012
Stack을 이용하는 경우, 가장 오른쪽에 있는 괄호를(마지막에 들어간 데이터를) 짝이 맞는 괄호를 찾기떄문에(무언가와 매치되는 지 검사)stack을 이용할 수 있다.
<쇠막대기 문제>
https://www.acmicpc.net/problem/10799
괄호문제의 변형
스택예제
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 | +#include <iostream> +#include <stack> +#include <string> +using namespace std; +int main() { + int n; + cin >> n; + stack<int> s; + while (n--) { + + string cmd; + cin >> cmd; + + if (cmd == "push") { + int num; + cin >> num; + s.push(num); + } + + //top은 스택에 있는 데이터를 반환한다. + else if (cmd == "top") { + cout << (s.empty() ? -1 : s.top()) << '\n'; + } + + //size는 스택에 있는 데이터의 개수를 반환한다. + else if (cmd == "size") { + cout << s.size() << '\n'; + } + + //empty는 비어있으면 1(true) 비어있지 않으면 0(false)를 반환. + else if (cmd == "empty") { + cout << s.empty() << '\n'; + } + + //pop은 스택위에 있는 데이터를 반환한다.없으면 에러가 발생. + else if (cmd == "pop") { + cout << (s.empty() ? -1 : s.top()) << '\n'; + if (!s.empty()) { + s.pop(); + } + } + } + return 0; +} | cs |
주의해야할점으로는 pop은 stack이 비어있지 않은 경우에만 사용할 수 있다. 비어있는데 pop을 할 경우엔 에러가 발생하므로 주의할 것!
덧글