anonymous.rs

자료구조: 스택 (Stack)

6 min read

스택 (Stack) 자료구조 완벽 가이드

소프트웨어 엔지니어링 인터뷰에서 가장 기본적이면서도 중요한 자료구조 중 하나인 **스택(Stack)**에 대해 알아보겠습니다.

1. 스택(Stack)이란?

스택은 데이터를 차곡차곡 쌓아 올린 형태의 선형 자료구조입니다. 프링글스 통이나 식당의 접시 더미를 상상하면 이해하기 쉽습니다.

가장 중요한 특징은 후입선출 (LIFO: Last-In, First-Out) 원칙을 따른다는 것입니다. 즉, 가장 마지막에 들어간 데이터가 가장 먼저 나옵니다. 한쪽 끝(Top)에서만 데이터의 삽입과 삭제가 이루어집니다.

2. 스택의 주요 연산 및 시간 복잡도

스택은 매우 단순한 구조를 가지며, 주요 연산의 시간 복잡도는 대부분 입니다.

연산설명시간 복잡도
Push스택의 가장 위(Top)에 데이터를 삽입합니다.
Pop스택의 가장 위(Top)에 있는 데이터를 제거하고 반환합니다.
Peek (Top)스택의 가장 위(Top)에 있는 데이터를 제거하지 않고 반환(확인)합니다.
isEmpty스택이 비어있는지 확인합니다.

만약 배열로 구현된 스택의 크기가 꽉 차서 동적으로 배열 크기를 늘려야 하는 경우, Push 연산은 최악의 경우 이 될 수 있지만 상각된 시간 복잡도(Amortized Time Complexity)는 여전히 로 간주합니다.

3. 스택의 구현

스택은 배열(Array/List)이나 연결 리스트(Linked List)를 사용하여 구현할 수 있습니다.

파이썬(Python)에서는 내장 자료형인 **리스트(List)**를 사용하여 아주 쉽게 스택을 사용할 수 있습니다. append() 메서드로 Push를, pop() 메서드로 Pop을 에 수행할 수 있습니다.

stack = []
 
# 데이터 삽입 (Push)
stack.append(1)
stack.append(2)
stack.append(3)
print(f"현재 스택: {stack}") # [1, 2, 3]
 
# 최상단 데이터 확인 (Peek)
top_element = stack[-1]
print(f"Top 데이터: {top_element}") # 3
 
# 데이터 추출 (Pop)
popped_element = stack.pop()
print(f"추출된 데이터: {popped_element}") # 3
print(f"Pop 이후 스택: {stack}") # [1, 2]

4. 스택의 활용 사례

스택은 그 특성상 ‘가장 최근의 상태’를 기억하고 돌아가야 하는 상황에서 필수적으로 사용됩니다.

  1. 함수 호출 스택 (Call Stack): 프로그램에서 함수가 호출될 때마다 해당 함수의 정보(지역 변수, 복귀 주소 등)가 스택에 저장됩니다. 함수가 종료되면 스택에서 pop되어 이전 함수로 돌아갑니다. 재귀 함수가 무한 루프에 빠지면 ‘Stack Overflow’ 오류가 발생하는 이유입니다.
  2. 웹 브라우저의 방문 기록 (뒤로 가기): 사용자가 방문한 페이지가 스택에 쌓이고, ‘뒤로 가기’ 버튼을 누르면 가장 최근(Top)에 방문한 페이지가 pop되어 이전 페이지로 이동합니다.
  3. 실행 취소 (Undo / Ctrl+Z): 문서 편집기나 프로그램에서 사용자의 행동을 스택에 기록해 두고, 취소 시 가장 최근 행동부터 되돌립니다.
  4. 괄호 짝 맞추기 (문법 검사): 수식이나 코드에서 (, {, [ 등의 열린 괄호를 스택에 넣고, 닫힌 괄호가 나올 때마다 스택에서 pop하여 짝이 맞는지 검사하는 알고리즘에 핵심적으로 사용됩니다.
  5. 깊이 우선 탐색 (DFS, Depth-First Search): 그래프 탐색 알고리즘인 DFS를 재귀가 아닌 반복문으로 구현할 때 스택이 사용됩니다.

요약

스택(Stack)은 “나중에 들어온 것이 먼저 나가는(LIFO)” 단순하지만 강력한 자료구조입니다. 삽입과 삭제 연산이 한 곳(Top)에서만 발생하며 연산 속도가 로 매우 빠릅니다. 함수 호출, 뒤로 가기, 괄호 검사 등 이전 상태로 되돌아가거나 최근 데이터를 우선으로 처리해야 하는 문제에서 가장 먼저 떠올려야 하는 자료구조입니다.

Graph View