스택(Stack)이란?

📘 스택이란 무엇인가요?

LIFO(Last In, First Out)

마지막에 들어간 데이터가 가장 먼저 나오는 구조

 

간단한 예로 책을 쌓는 것을 생각해 볼 수 있습니다.

책더미에서 책을 꺼낼 때 가장 위에 있는 책부터 꺼내게 됩니다.

이게 바로 스택의 기본 원리입니다!

 

🌟 스택의 장단점

👍 장점

 - 단순하고 빠르다

: 스택은 구조가 단순하며, 데이터 접근/저장이 빠릅니다.

 

- 명확한 규칙으로 인한 오류 감소

: LIFO 규칙이 명확하므로 예상치 못한 오류가 줄어듭니다.

 

👎 단점

 - 데이터의 접근 제한

: 중간에 있는 데이터를 접근하기 위해서는 위에 있는 데이터들을 모두 꺼내야 합니다.

- 메모리 할당

: 스택의 크기가 변동되지 않도록 고정된 메모리를 할당해야 할 수 있습니다.

 

🕒 스택의 시간 복잡도

데이터 접근 시간: O(n) - 중간 데이터에 접근하기 위해서는 순차 접근이 필요

데이터 삽입/삭제 시간: O(1) - 스택의 꼭대기(top)에서 이루어지므로 상수 시간이 소요

 

🤔 스택은 언제 사용하면 좋을까요?

- 최근의 항목을 먼저 처리해야 할 때

ex) Undo 기능 구현 시 가장 마지막에 실행된 명령을 먼저 취소해야 합니다.

 

- 역순으로 데이터를 사용해야 하는 경우

: 스택으로 데이터를 쌓고, 나중에 꺼내면 역순으로 사용할 수 있습니다.

 

- 재귀 호출

: 함수의 호출이 이루어질 때 시스템 스택이 사용되며, 호출이 끝나면 자동으로 복귀 주소가 스택에서 pop 됩니다.