Kwangmin Kim - Data Structure (5) Stack

1 Stack

정의: 스택 (Stack)

스택은 마지막에 삽입된 데이터가 가장 먼저 제거되는 LIFO(Last-In, First-Out) 자료구조다.

삽입(Push): 항상 맨 위(top)에 추가 — \(O(1)\)
추출(Pop): 항상 맨 위(top)에서 제거 — \(O(1)\)
최상위 조회(Top): 제거 없이 top 원소 확인 — \(O(1)\)

다양한 알고리즘과 프로그램에서 사용됨
스택: 먼저 들어온 데이터가 나중에 나가는 자료구조
흔히 박스가 쌓인 형태를 스택(stack)이라고 한다. 예) ‘Deep Learning 알고리즘의 구조가 stacked 되어 있는 구조다’ 라고 표현
- 우리가 박스를 쌓은 뒤에 꺼낼 때는, 가장 마지막에 올렸던 박스부터 꺼내야 한다.
새로운 원소를 삽입할 때는 마지막 위치에 삽입한다. (가장 최근에 삽입된 원소가 가장 끝에 위치)
새로운 원소를 삭제할 때는 마지막 원소가 삭제된다. (가장 최근에 삽입된 원소가 제거됨)
head = 최상위 원소 = 가장 최근에 삽입이된 원소

직관적 이해: 식당 주방의 접시 더미와 같다. 새 접시는 항상 맨 위에 올리고(Push), 꺼낼 때도 항상 맨 위에서 꺼낸다(Pop). 바닥의 접시를 꺼내려면 위의 접시를 모두 치워야 한다.

동작 원리 (시각화):

초기     push(7)  push(2)  pop()   pop()
         ┌───┐    ┌───┐            
         │ 7 │    │ 2 │    ┌───┐   
         └───┘    │ 7 │    │ 7 │   
                  └───┘    └───┘   
 (빈 스택) top=7   top=2   top=7  (빈 스택)

2 왜 필요한가

함수 호출 스택(call stack): 재귀 함수 호출이 LIFO 방식으로 관리된다.
웹 브라우저 뒤로가기: 방문 기록을 스택으로 관리한다.
괄호 유효성 검사: 열린 괄호를 스택에 push하고 닫힌 괄호를 pop으로 검증한다.
DFS(깊이 우선 탐색): 스택 기반으로 구현된다.

3 스택 자료구조의 중요성

스택은 굉장히 기본적인 자료구조이다.
기계 학습 분야뿐 아니라 다양한 프로그램을 개발할 때 빠지지 않고 사용된다.

4 스택 자료구조의 시간 복잡도

스택은 여러 가지 연산을 제공한다.

표 1: a list of the stack functions in Python

Number	Methods	Time Complexity	Description
1	삽입(Push)	\(O(1)\)	스택에 원소를 삽입하는 연산
2	추출(Pop)	\(O(1)\)	스택에서 원소를 추출하는 연산
3	최상위 원소 (Top)	\(O(1)\)	스택의 최상위 원소(마지막에 들어온 원소) 를 확인(조회)하는 연산
4	Empty	\(O(1)\)	스택이 비어 있는지 확인하는 연산

See 표 1.

5 Python에서 스택을 구현하는 방법 1: 리스트 자료형

파이썬의 기본적인 리스트 자료형은 다음의 두 가지 메서드를 제공한다.
append() 메서드: 마지막 위치에 원소를 삽입하며, 시간 복잡도는 \(O(1)\) 이다.
pop() 메서드: 마지막 위치에서 원소를 추출하며, 시간 복잡도는 \(O(1)\) 이다.
따라서 일반적으로 스택을 구현할 때, 파이썬의 리스트(list) 자료형을 사용한다.

아래 코드는 Python list를 이용해 스택을 구현한다. append()가 push, pop()이 pop 역할을 한다.

class Stack:
    def __init__(self):
        self.stack = []

    def push(self, data):
        # 마지막 위치에 원소 삽입
        self.stack.append(data)

    def pop(self):
        if self.is_empty():
            return None
        # 마지막 원소 추출
        return self.stack.pop()

    def top(self):
        if self.is_empty():
            return None
        # 마지막 원소 반환
        return self.stack[-1]

    def is_empty(self):
        return len(self.stack) == 0


stack = Stack()
arr = [9, 7, 2, 5, 6, 4, 2]
for x in arr:
    stack.push(x)

while not stack.is_empty():
    print(stack.pop())
# 출력:
# 2
# 4
# 6
# 5
# 2
# 7
# 9

핵심 포인트

Python의 list는 스택으로 바로 사용할 수 있다: arr.append(x) / arr.pop()
두 메서드 모두 \(O(1)\) 이므로 별도의 Stack 클래스 구현이 불필요한 경우가 많다.
arr[-1]로 top 원소를 꺼내지 않고 확인할 수 있다.

6 연결 리스트로 스택 구현하기

스택을 연결 리스트로 구현하면, 삽입과 삭제에 있어서 \(O(1)\) 을 보장한다.
연결 리스트로 구현할 때는 머리(head)를 가리키는 하나의 포인터만 가진다.
머리(head): 남아있는 원소 중 가장 마지막에 들어 온 데이터를 가리키는 포인터

연결 리스트로 구현한 스택은 동적 메모리를 사용하여 크기 제한이 없다. head 포인터가 스택의 top을 가리킨다.

6.1 삽입 연산

삽입할 때는 기존의 머리 뒤에 데이터가 들어가고 포인터가 가장 최근에 삽입된 데이터를 가리키도록 머리(head) 위치를 바꿔준다.
삭제할 때는 머리(head) 위치에서 데이터를 꺼낸다.
- 즉, 포인터를 삭제할 데이터에 앞에 있는 데이터로 머리 위치를 바꾸는 것만으로 삭제는 이루어진다.

6.2 삭제 연산

삭제할 때는 머리(head) 위치에서 데이터를 꺼낸다.


class Node:
    def __init__(self, data):
        self.data = data
        self.next = None


class Stack:
    def __init__(self):
        self.head = None

    # 원소 삽입
    def push(self, data):
        node = Node(data)
        node.next = self.head
        self.head = node

    # 원소 추출하기
    def pop(self):
        if self.is_empty():
            return None

        # 머리(head) 위치에서 노드 꺼내기
        data = self.head.data
        self.head = self.head.next

        return data

    # 최상위 원소(top)
    def top(self):
        if self.is_empty():
            return None
        return self.head.data

    # 먼저 추출할 원소부터 출력
    def show(self):
        cur = self.head
        while cur:
            print(cur.data, end=" ")
            cur = cur.next

    # 스택이 비어있는지 확인
    def is_empty(self):
        return self.head is None


stack = Stack()
arr = [9, 7, 2, 5, 6, 4, 2]
for x in arr:
    stack.push(x)
stack.show()
print()

while not stack.is_empty():
    print(stack.pop())
# 출력:
# 2 4 6 5 2 7 9
# 2
# 4
# 6
# 5
# 2
# 7
# 9

7 응용 분야

함수 호출 스택(Call Stack): 함수가 호출될 때마다 스택 프레임이 쌓이고, 반환 시 제거된다. 재귀 함수의 동작 원리이다.
괄호 유효성 검사: (, [, {를 push하고 닫는 괄호가 나오면 pop하여 매칭을 확인한다.
웹 브라우저 뒤로가기: 방문 페이지를 스택에 쌓아 뒤로가기 시 pop한다.
DFS(깊이 우선 탐색): 방문할 노드를 스택에 넣어 깊이 우선으로 탐색한다.
수식 계산기: 후위 표기법(Postfix) 연산에서 피연산자를 스택으로 관리한다.