Stack이 무엇이고 어떤 경우에 사용될까?

Stack이란

Stack

- Stack은 LIFO(Last In First Out) 원칙에 기반한 선형 자료구조이다.

 

LIFO란?
가장 최근에 추가된 항목이 가장 먼저 제거되는 순서를 따른다는 것을 의미한다.

 

Stack의 주요 연산

- push(e): 특정 요소를 스택에 추가

- pop(): 스택의 맨 위에 있는 항목(top)을 제거하고, 해당 원소를 반환

- peek(): 스택의 맨 위에 있는 항목(top)을 반환 (제거X)

- isEmpty(): 스택이 비어있는지 확인

 

Stack의 사용 사례

- Undo(실행 취소) / Redo(다시 실행)

Undo와 Redo 기능 구현하기 위해서 주로 두 개의 스택(Stack)을 사용한다.

사용자가 A, B, C, D 순으로 작업을 수행했다면,
Undo Stack = [A, B, C, D], Redo Stack = []

이 상태에서 사용자가 Undo를 클릭하면, D 작업이 수행된다. (Redo Stack에 추가)
Undo Stack = [A, B, C], Redo Stack = [D]

한번 더 Undo를 클릭하면, C 작업이 수행된다. (Redo Stack에 추가)
Undo Stack = [A, B], Redo Stack = [D, C]

이 상태에서 Redo를 클릭하면, C 작업이 수행된다. (Undo Stack에 추가)
Undo Stack = [A, B, C], Redo Stack = [D]

 

- 프로그램의 함수 호출 관리

OS는 함수(메서드)를 호출하기 위해 스택을 사용한다.

이를 호출 스택(Call Stack)이라고 하며, 함수 호출과 반환을 효과적으로 관리할 수 있게 한다.

 

- 그 외

문자열 역순으로 바꾸기, 괄호의 짝 확인하기, 후위 표기법 변환하기 등에 활용된다.

 

Stack의 장점

1. 상수 시간의 기본 연산

스택의 기본 연산(push, pop, peek 등)은 O(1), 즉 상수 시간의 복잡도를 갖는다.

이는 Stack의 사용하여 데이터를 삽입/삭제/접근하는데 걸리는 시간이 일정하다는 것을 의미한다.

 

2. 메모리 효율성

스택은 동적으로 크기가 조정될 수 있어 필요한 만큼의 메모리만 사용하기 때문에 메모리를 효율적으로 사용한다.

 

3. LIFO 특성

스택의 LIFO 특성은 DFS, 백트래킹 알고리즘 등에서 유용하게 사용된다.

 

참고 자료

https://gist.github.com/mlynch/ab554d84dc3b7b8be3d6