이번에 알아볼 자료구조는 stack(스택)입니다.
stack 뜻을 알아보겠습니다. 영어 사전을 보면 여러 뜻 중 쌓다라는 뜻이 있는 것을 볼 수 있습니다.
스택은 뜻에 따라 자료를 쌓아 보관한다고 생각하면 됩니다.
실제로 스택을 설명할 때 책을 쌓아 올리는 방식에 빗대어 표현합니다.
stack(스택)
스택이란 자료의 추가와 제거가 한 끝에서만 이루어지는 선형 자료구조입니다.
그렇다보니 먼저 들어간 자료가 가장 아래 쪽에 저장되어 하나씩 삭제를 할 때 가장 마지막에 삭제됩니다.
이 특성 때문에 스택을 '후입선출의 자료구조' 또는 'LIFO(Last in, First out)의 자료구조'라고 합니다.
예를 들어 1~5까지 순서대로 저장을 한다고 합시다.
스택은 자료의 처리가 한 쪽 끝에서만 이루어진다 했습니다. 그 끝을 top이라고 부릅니다.
| 5 |
| 4 |
| 3 |
| 2 |
| 1 |
위와 같은 경우는 top이 위 쪽에서 하나씩 자료를 추가한 것입니다.
그러면 하나씩 삭제를 해보겠습니다. top은 5를 가리키고 있겠죠
가장 먼저 삭제되는 데이터는 5입니다. 가장 마지막에 들어간 데이터이죠.
가장 마지막에 삭제되는 데이터는 1로 가장 처음에 들어간 데이터가 됩니다.
스택을 예로 들 때 책을 쌓는 방식이라든지 쟁반 위 쌓인 접시, 상자를 쌓는 상황들을 듭니다.
저는 처음 스택을 공부할 때 발포 비타민이 떠올랐습니다. 하나하나 쌓여 있으면서 넣고 빼내는게 한 쪽에서만 이루어져처음 들어간게 가장 아래쪽에 있어 마지막에 나오고 안에서 순서도 바뀌지 않기 때문이죠.
스택은 이와 같은 성질(특징)들을 가지고 있습니다.
스택의 연산
스택은 다른 자료구조보다 연산이 간단한 편입니다. 한 쪽에서만 추가, 삭제가 이루어지기 때문에 딱히 할 게 없죠.
크게 5가지 정도 살펴보겠습니다.
- 생성
- 스택의 내부 상태(비어있는지 가득 차있는지 확인)
- push
- pop
- peek
스택에서는 추가를 push, 삭제를 pop이라고 합니다.
이제 이전과는 다른 연산이 peek인데 이는 top이 가리키고 있는 자료를 반환하는 연산입니다.
스택에서는 검색 연산이 없습니다. 뭐 억지로 구현하려면 할 수 있지만 사용해도 쓸모가 없습니다.
어째서 일까요?
스택은 자료의 접근이 한 끝, 즉 top에서만 이루어지고 있습니다.
자료를 탐색해서 찾았다고 해도 그 데이터를 반환할 수도, 그 데이터 다음에 다른 데이터를 추가할 수도 없습니다.
그게 스택의 정의이기 때문이죠.
그래서 스택에서는 탐색 연산을 허용하지 않는다라고 말합니다.
스택의 사용
그러면 이제 스택이 어떤 것인지는 알겠는데 어디에 사용되는지 알아야 쓸모가 있어지겠죠?
우선 system stack 또는 call stack이라고 부르는데 함수를 호출할 때 사용됩니다.
특히 재귀 함수를 호출할 때 분명하게 볼 수 있습니다. 재귀 함수는 아실거라고 생각합니다.
https://readytoearndon.tistory.com/6?category=835376
백준 10872 팩토리얼 solution[python] - 풀이, 설명::FBTT
https://www.acmicpc.net/problem/10872 10872번: 팩토리얼 0보다 크거나 같은 정수 N이 주어진다. 이때, N!을 출력하는 프로그램을 작성하시오. www.acmicpc.net 1. 팩토리얼의 정의 생각해보기 n!은 n부터 1까..
readytoearndon.tistory.com
python으로 짜여있지만 대표적인 재귀 예제이죠, 팩토리얼의 재귀 함수를 안다고 생각하고 설명하겠습니다.
예를 들어 factorial(3)을 호출할 때 우선 처음 stack에 main이 들어가고 factorial(3)이 다음에 들어가고 factorial(2)가 호출되면서 들어가고 factorial(1)이 1을 반환하면서 stack에 저장되어 있는 factorial(2)가 실행되고 pop, 다음에 factorial(3)이 실행되고 pop, 마지막으로 main함수의 실행이 끝나면서 stack은 비어있게 됩니다.
| factorial(2) |
| factorial(3) |
| main() |
그리고 visual studio같은 곳에서 코딩을 하다보면 괄호를 검사해주게 됩니다. 빠진 괄호가 없는지 괄호가 잘못 매칭되지는 않았는지를 말이죠.
이 괄호를 검사할 때도 스택이 사용됩니다.
( { })이러한 형태의 괄호를 검색한다고 해봅시다. 그러면 열린 괄호는 스택에 저장합니다.
| { |
| ( |
그래서 위와 같은 스택이 생깁니다. 그리고 닫힌 괄호를 만나게 되면 스택의 top과 비교를 합니다.
여기서는 top인 '{'와 '}'를 비교하게 됩니다. 모두 중괄호이므로 스택에서 pop합니다.
| ( |
그리고 ')'와 비교하여 모두 소괄호이기 때문에 다시 스택에서 pop합니다. 그래서 마지막에 모든 괄호를 검사해서 스택이 비어있을 때 모든 괄호가 잘 연결되어 있다고 판단합니다.
이 외에도 후위 표기 계산이나 미로 문제에도 스택이 사용됩니다.
다음 글에서는 스택을 배열로 구현해보도록 하겠습니다. 이번 글에서 다뤘던 연산들을 말이죠
