스택(Stack)

개요

스택(Stack)은 데이터가 일렬로 쌓이고, 가장 마지막에 삽입된 요소가 가장 먼저 제거되는 후입선출(Last-In, First-Out, LIFO) 원칙을 따르는 선형 자료구조이다. 삽입은 push, 삭제는 pop, 현재 요소 확인은 peek 또는 top 연산으로 수행되며, 재귀, 수식 계산, 괄호 검사, 웹 브라우저의 방문 기록 등 다양한 분야에서 널리 활용된다.

---

1. 개념 및 정의

항목	설명
구조	선형적, 한쪽 끝에서만 삽입 및 삭제 가능
주요 연산	push(삽입), pop(삭제), peek/top(최상단 확인), isEmpty
대표 원리	LIFO (Last-In, First-Out)

---

2. 스택 연산 동작 예시

초기: []
push(10) → [10]
push(20) → [10, 20]
pop() → [10] (20 제거)
push(30) → [10, 30]
peek() → 30

스택은 한쪽 방향으로만 입출력이 이루어지는 단순하면서도 강력한 구조이다.

---

3. 파이썬 구현 예시 (리스트 기반)

stack = []

stack.append(10)  # push
stack.append(20)
print(stack.pop())  # pop → 20
print(stack[-1])  # peek → 10
print(not stack)  # isEmpty → False

리스트의 append, pop을 사용해 스택 구조를 쉽게 구현할 수 있다.

---

4. 시간 및 공간 복잡도

연산	시간 복잡도
push	O(1)
pop	O(1)
peek	O(1)
isEmpty	O(1)

모든 주요 연산이 상수 시간에 동작하여 매우 효율적이다.

---

5. 배열 vs 연결 리스트 기반 스택

구현	설명	특징
배열 기반	리스트/배열에 요소 삽입	구현 쉬움, 메모리 고정 또는 재할당 필요
연결 리스트 기반	노드를 추가하며 동적 생성	유연한 크기, 메모리 관리 필요

---

6. 스택의 활용 사례

분야	예시
컴퓨터 언어	함수 호출, 재귀 처리 (Call Stack)
수식 계산기	중위 → 후위 표현식 변환, 계산
괄호 검사	올바른 괄호 문자열 판단
웹 브라우저	뒤로가기 기능 구현
알고리즘	DFS(깊이 우선 탐색), 백트래킹

---

7. 스택의 장단점

구분	장점	단점
구조	간단하고 구현 쉬움	중간 요소 접근 불가
성능	연산 속도 빠름 (O(1))	유연한 탐색에는 부적합
메모리	배열/연결 리스트 선택 가능	메모리 재할당 또는 노드 관리 필요

---

8. 결론

스택은 후입선출 구조를 갖는 매우 단순하고 강력한 자료구조로, 함수 호출, 수식 계산, 탐색 알고리즘 등 수많은 곳에서 활용된다. 배열 또는 연결 리스트 기반으로 쉽게 구현 가능하며, 알고리즘 문제 해결과 자료구조 학습의 기본 중 하나로 반드시 익혀야 한다.