개인적으로 스택이란 자료구조를 굉장히 좋아하는 편이다. 사실 우리가 일상 생활에서 스택과 유사한 것을 보기는 쉽지 않긴 하지만 정보과학 문제를 풀 때는 스택을 사용하면 정말 예쁘게 풀리는 경우가 꽤 있기 때문이다. 그리고 웬만해서 그런 문제들은 좀 재미있기도 하고..
스택(Stack)은 기본적으로 후입선출(LIFO, Last In First Out) 구조이다. 다른 말로 자료구조에 제일 먼저 넣은 값이 나올 때는 가장 마지막에 나오는 것이다. 정확히 Queue하고는 반대의 개념을 가지고 있다. 원소를 넣거나 뺄 때는 $O(1)$ 만큼의 시간복잡도를 가져야 하기 때문에 원래는 연결리스트를 사용하는 것이 정석이라고 알고 있기는 한데, 보통은 배열이나 vector로 구현하거나 아니면 그냥 맘편히 STL을 쓴다. 다음은 BOJ 10828번 스택 문제의 구현이다.
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 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 | #include <stdio.h> #include <string.h> int st[10005],en=0; void push(int x) { st[en++]=x; } int pop() { if(en==0) return -1; return st[--en]; } int size() { return en; } int empty() { if(en==0) return 1; else return 0; } int top() { if(en==0) return -1; return st[en-1]; } int main() { int n; scanf("%d",&n); for(int i=0;i<n;i++) { char str[30]; int t; scanf("%s",str); if(strcmp(str,"push")==0) { scanf("%d",&t); push(t); } else if(strcmp(str,"pop")==0) printf("%d\n",pop()); else if(strcmp(str,"top")==0) printf("%d\n",top()); else if(strcmp(str,"empty")==0) printf("%d\n",empty()); else if(strcmp(str,"size")==0) printf("%d\n",size()); } return 0; } | cs |
보다시피 굉장히 간단한 코드로 스택이 만들어지는 것을 확인할 수 있다.위 코드에서 보이듯(조금 다른 부분도 있지만) 스택은 다음과 같이 5개의 연산을 기본적으로 지원한다.
이 코드에서는 배열을 사용해서 구현을 했는데, 단순히 스택의 맨 위가 어디 있는지만을 확인해주며 동작하는 모습을 볼 수 있다. pop 연산을 할 때에도 원소를 굳이 따로 지워주지 않는다는 점을 확인하자.
경험상 스택을 사용하는 문제는 거의 다 처음 볼 때도 "아, 이건 스택 쓰는 문제구나" 할 만큼 대놓고 스택 문제라는 것을 알아차릴 수 있었다. 일단 앞으로 포스팅 할 스택 관련 문제들을 몇개 게시하고, 차례로 풀이를 쓰도록 하겠다.