스택(Stack)에 대해 알아보겠습니다.
스택은 데이터 구조의 한 종류로, 어디에서나 쓰이고 몰라서는 안될 자료구조입니다.
이번 글에서는 스택의 개념, 메소드, 사용 시 주의점, 그리고 활용 사례까지 자세히 살펴보겠습니다.
1. 스택이란
스택은 데이터를 쌓아 올리는 구조로, 후입선출(LIFO: Last In, First Out) 방식을 따릅니다.
즉, 가장 나중에 추가된 데이터가 가장 먼저 제거되는 구조입니다.
쉽게 말해, 바닥이 막혀 있는 통에 물체를 넣고 빼는 구조를 생각하시면 됩니다.
2. 스택 (배열)의 메소드
자바스크립트로 스택을 구현할 때는 보통 일반 배열을 사용합니다.
배열의 메소드 중 일부는 스택의 동작을 구현하기에 적합합니다.
(1) push(...items: T[]): number;
- 데이터를 스택의 맨 위에 추가합니다.
- 예제:
const stack = []; stack.push(10); // [10] stack.push(20); // [10, 20]
(2) pop(): T | undefined;
- 스택의 맨 위에 있는 데이터를 제거하고 반환합니다.
- 예제:
const top = stack.pop(); // [10], top은 20
(3) .length: number;
- 스택에 있는 데이터의 개수를 반환합니다.
- 예제:
const stack = [1,2,3] console.log(stack.length); // 3
03. 스택 오버플로우
스택을 사용할때는 “스택 오버플로우” 상황이 발생하지 않도록 주의해야 합니다.
특히 재귀 호출을 사용하는 알고리즘에서 스택이 너무 깊어지면 아래 사진과 같이 스택 오버플로우(Stack Overflow) 문제가 발생할 수 있습니다.
4. 스택의 활용 사례
스택은 다양한 문제를 해결하는 데 사용됩니다. 몇 가지 대표적인 예를 들어보겠습니다.
(1) 브라우저의 뒤로가기 기능
브라우저는 방문한 페이지를 스택에 저장합니다.
pop() 메소드를 사용하여 마지막 방문 페이지로 돌아갈 수 있습니다.
(2) 괄호의 유효성 검사
괄호가 올바르게 열리고 닫혔는지 확인할 때 스택을 사용할 수 있습니다.
예제:
function isValidParentheses(s) {
const stack = [];
for (const char of s) {
if (char === '(') {
stack.push(char);
} else if (char === ')') {
if (stack.pop() !== '(') {
return false;
}
}
}
return stack.length === 0;
}
console.log(isValidParentheses("(())")); // true
console.log(isValidParentheses("(()")); // false(3) 재귀 호출
함수가 재귀적으로 호출될 때, 함수 호출 기록은 스택에 저장됩니다.
이를 통해 재귀 호출의 흐름을 관리합니다.
(4) DFS(깊이 우선 탐색)
그래프 탐색 알고리즘 중 깊이 우선 탐색(Depth First Search)은 스택을 이용하여 구현할 수 있습니다.
스택은 간단하지만 매우 강력한 데이터 구조입니다.
프로그램에서 데이터를 관리하거나 알고리즘을 구현할 때 자주 사용되므로 꼭 익혀두시면 좋습니다.
