스택
시작하기에 앞서
해당 블로그의 모든 문서는 학습한 내용을 제 방식으로 정리하여 작성하고 있습니다.
순수 창작물도 아니고, 틀린 내용이 있을 수 있으므로 참고하고 읽어주시면 감사하겠습니다.
스택이란?
스택은 후입선출 LIFO(Last In First Out)의 자료구조입니다. 말 그대로 가장 마지막에 입력된 데이터가 가장 먼저 출력됩니다. 활용 예시는 후위 표기법 연산, 괄호 유효성 검사, 웹 브라우저 방문 기록, 깊이 우선탐색(DFS)등이 있습니다. 간단하게 데이터를 입력하고 출력하는 예시를 들어보겠습니다.
일단 어떠한 데이터도 저장되어 있지 않은 비어있는 스택을 하나 준비했다고 가정해 보겠습니다. 그리고 연산에 대해서 간단히 용어 설명을 하자면, 스택에 데이터를 입력하는 연산을 push라고 하며, 데이터를 출력하는 연산을 pop이라고 합니다.
스택에 숫자 10을 입력해 보겠습니다.
push(10)
- 10
이어서 숫자 20을 입력해 보겠습니다.
push(20)
- 10, 20
이번엔 스택에서 데이터를 하나 출력해 보겠습니다.
pop()
- 10
데이터를 하나 더 출력해 보겠습니다.
pop()
- Empty
스택의 push 연산과 pop 연산을 살펴보면 알 수 있듯이, 가장 마지막으로 입력된 20이 먼저 입력된 10보다 먼저 출력되는 것을 볼 수 있습니다. 그래서 스택을 가장 마지막으로 입력된 데이터가 가장 먼저 출력된다고 하여 LIFO(Last In First Out) 자료구조라고 부릅니다.
과자 중에 프링글스를 알고 있다면 상상하기가 쉽습니다. 뚜껑을 열고, 밑에 있는 과자를 먹기 위해서는 위에 있는 과자부터 하나씩 꺼내서 먹어야 하는 구조로 되어있는데, 이는 스택 구조와 매우 유사합니다.
