자료구조 - 스택(Stack)

스택이란 무엇일까?

스택(Stack)은 나중에 들어간 데이터가 먼저 나오는 자료구조입니다. 이를 LIFO(Last In, First Out) 구조라고 부릅니다.

가장 최근에 추가된 데이터가 가장 먼저 꺼내지기 때문에, 일상생활에서도 자주 접할 수 있습니다.

예를 들어, 식판을 쌓을 때 가장 마지막에 올려놓은 식판을 가장 먼저 꺼내는 것과 같은 원리입니다.

스택의 구조

스택은 주로 두 가지 기본 연산을 수행합니다:

• push(푸시): 새로운 데이터를 스택의 맨 위에 추가합니다.
• pop(팝): 스택의 맨 위에 있는 데이터를 꺼내고 제거합니다.

추가로 자주 사용하는 연산:

• peek(피크): 맨 위에 있는 데이터를 꺼내지 않고 단순히 확인만 합니다.

스택에서는 오직 맨 위(top)만 다룰 수 있기 때문에, 중간 데이터에 접근하는 것은 허용되지 않습니다.

스택 동작 예시

1. 스택이 비어 있습니다. → []
2. push(10) → [10]
3. push(20) → [10, 20]
4. push(30) → [10, 20, 30]
5. pop() → 30을 꺼냄 → [10, 20]
6. pop() → 20을 꺼냄 → [10]
7. peek() → 10을 확인 (꺼내지는 않음)

스택 예시 (Python)

stack = []  # 리스트를 이용한 스택 생성

# push 연산 (append)
stack.append(10)
stack.append(20)
stack.append(30)

# pop 연산
print(stack.pop())  # 출력: 30
print(stack.pop())  # 출력: 20

# peek 연산 (리스트의 마지막 요소 확인)
print(stack[-1])    # 출력: 10 (삭제되지 않고 확인만)

스택의 시간복잡도

스택은 삽입(push), 삭제(pop), 조회(peek) 모두 빠르게 수행할 수 있습니다.

연산	시간복잡도	설명
push(추가)	O(1)	스택의 맨 위에 바로 추가합니다.
pop(삭제)	O(1)	스택의 맨 위에서 바로 제거합니다.
peek(조회)	O(1)	맨 위 데이터를 빠르게 확인할 수 있습니다.

시간복잡도가 O(1)이라는 것은, 스택의 크기와 관계없이 일정한 시간에 연산이 완료된다는 의미입니다.

스택의 장점과 단점

장점

• 구현이 간단하고 직관적입니다.
• 맨 위 데이터에 빠르게 접근할 수 있습니다.
• 함수 호출 관리, 되돌리기 기능 등 다양한 분야에서 활용됩니다.

단점

• 중간 데이터에 접근하거나 조작할 수 없습니다.
• 데이터 순서에 제한이 있기 때문에 상황에 따라 불편할 수 있습니다.

스택이 활용되는 예시

활용 분야	설명
웹 브라우저 뒤로 가기	방문한 페이지를 스택에 저장하고, 뒤로 갈 때 pop으로 페이지를 꺼냅니다.
함수 호출 관리 (콜 스택)	프로그램이 함수를 호출할 때마다 스택에 쌓고, 함수 실행이 끝나면 pop합니다.
괄호 짝 검사	열고 닫는 괄호의 짝을 검사할 때 스택을 이용합니다.
실행 취소(Undo) 기능	사용자의 작업을 스택에 저장했다가 취소할 때 pop하여 이전 상태로 되돌립니다.

실생활 예시로 이해하기

스택은 책 더미와 비슷합니다. 책을 쌓을 때 가장 나중에 올려놓은 책을 먼저 꺼내야 하며, 중간에 있는 책을 꺼내려면 위의 책들을 먼저 치워야 합니다.

또 다른 예시로는 접시 쌓기, 탑 쌓기, 함수 호출 등이 있습니다.

마무리 정리

항목	스택
데이터 처리 방식	LIFO (Last In, First Out)
주된 연산	push, pop, peek
주요 특징	맨 위 데이터만 접근 가능, 순서 엄격
활용 예시	웹 브라우저 뒤로가기, 함수 호출 관리, 괄호 검사, Undo 기능