Problem Solving/자료구조 (1) 썸네일형 리스트형 [자료구조] 스택 개인적으로 스택이란 자료구조를 굉장히 좋아하는 편이다. 사실 우리가 일상 생활에서 스택과 유사한 것을 보기는 쉽지 않긴 하지만 정보과학 문제를 풀 때는 스택을 사용하면 정말 예쁘게 풀리는 경우가 꽤 있기 때문이다. 그리고 웬만해서 그런 문제들은 좀 재미있기도 하고.. 스택(Stack)은 기본적으로 후입선출(LIFO, Last In First Out) 구조이다. 다른 말로 자료구조에 제일 먼저 넣은 값이 나올 때는 가장 마지막에 나오는 것이다. 정확히 Queue하고는 반대의 개념을 가지고 있다. 원소를 넣거나 뺄 때는 $O(1)$ 만큼의 시간복잡도를 가져야 하기 때문에 원래는 연결리스트를 사용하는 것이 정석이라고 알고 있기는 한데, 보통은 배열이나 vector로 구현하거나 아니면 그냥 맘편히 STL을 쓴다.. 이전 1 다음