[자료구조]파이썬 스택 구조 완벽 가이드: 개념, 구현 및 활용 예제

파이썬에서 스택(Stack) 구조는 데이터 저장 및 접근 방식 중 하나로, 후입선출(LIFO: Last In, First Out) 원칙을 따릅니다. 이는 마지막에 추가된 항목이 가장 먼저 제거되는 구조로, 브라우저의 뒤로 가기 기능이나 호출 스택(Call Stack)에서 흔히 볼 수 있습니다. 이번 포스팅에서는 파이썬에서 스택 구조의 개념, 구현 방법, 그리고 실전 활용 예제를 다룰 것입니다.

≣ 목차

• 스택이란?
• 배열구조로 스택 구현하기
• 스택의 활용 예제
• 파이썬에서 스택 사용하기
• 시스템스택과 순환호출
• 핵심 내용👀

스택은 배열 구조로 구현되는데, 파이썬에서는 배열을 리스트와 튜플을 통해 구현할 수 있습니다. 배열은 자료 구조를 구현하는 데 필요한 원소들을 변경할 수 있어야 하므로, 파이썬에서는 주로 리스트를 사용합니다. 리스트는 원소의 추가, 제거, 변경 등이 가능하며, 이러한 유연성 때문에 자료 구조를 구현할 때 많이 활용됩니다. 튜플은 변경이 불가능한 성질을 가지고 있어, 데이터가 변경되지 않는 상황에서 사용됩니다.

파이썬의 리스트와 튜플에 대한 자세한 내용은 아래 포스팅을 참고해 주세요😁

[Python]파이썬 컬렉션 자료형: 리스트와 튜플의 활용법과 차이점

---

01. 스택이란?🧐

스택(Stack)은 후입선출(LIFO: Last In, First Out) 원칙을 따르는 선형 자료구조입니다. 이는 마지막에 추가된 항목이 가장 먼저 제거되는 구조로, 상단에서만 데이터를 삽입하고 삭제할 수 있습니다. 스택은 컴퓨터 과학에서 매우 중요한 개념으로, 다양한 알고리즘과 데이터 처리 과정에서 활용됩니다.

스택은 데이터의 임시 저장 및 관리, 함수 호출의 순서 관리, 수식의 괄호 검사 등 다양한 곳에서 사용됩니다. 스택을 이해하고 활용하면 알고리즘을 효과적으로 구현하고 데이터 처리 과정을 간단하고 직관적으로 만들 수 있습니다.

1-1. 스택의 연산

스택은 데이터를 순서대로 쌓아 올리는 구조입니다. 일반적인 스택의 연산은 다음과 같습니다.

• push: 스택의 상단에 항목을 추가합니다.
• pop: 스택의 상단에서 항목을 제거하고 반환합니다.

추가적으로, 스택의 현재 상태를 확인하기 위한 연산들도 있습니다:

• peek: 스택의 상단에 있는 항목을 제거하지 않고 반환합니다.
• is_empty: 스택이 비어 있는지 확인합니다.
• size: 스택에 있는 항목의 개수를 반환합니다.
• 오버플로(Overflow): 스택이 꽉 찬 상태에서 추가로 항목을 삽입하려고 할 때 발생합니다.
• 언더플로(Underflow): 스택이 비어 있는 상태에서 항목을 제거하려고 할 때 발생합니다.

1-2. 스택의 활용 예 : 웹 브라우저의 이전페이지로 이동

웹 브라우저의 뒤로 가기 기능은 스택을 이용하여 구현됩니다. 사용자가 방문한 페이지를 스택에 저장하고, '뒤로 가기' 버튼을 클릭할 때마다 스택의 상단에서 페이지를 제거하여 이전 페이지로 이동합니다.

1-3. 추상 자료형

스택은 추상자료형(Abstract Data Type, ADT)으로 정의됩니다. 이는 스택의 동작을 정의하는 명세이며, 이를 구현하는 다양한 방법이 존재합니다. 추상자료형은 구현 세부 사항과 무관하게 스택의 동작을 설명하는 데 중점을 둡니다.

---

02. 배열구조로 스택 구현하기

스택은 배열 구조나 연결 리스트 구조를 통해 구현할 수 있습니다. 여기서는 배열 구조를 사용하여 스택을 구현하는 방법에 대해 설명하겠습니다.

2-1. 자료구조의 구현 방법들 (배열구조, 연결된 구조)

• 배열구조: 고정된 크기의 배열을 사용하여 스택을 구현합니다. 이 방법은 구현이 간단하고, 인덱스를 이용한 빠른 접근이 가능합니다. 그러나 배열의 크기가 고정되어 있어 크기를 초과하면 스택 오버플로가 발생합니다.
• 연결된 구조: 연결 리스트를 사용하여 스택을 구현합니다. 이 방법은 동적으로 크기를 조절할 수 있어 메모리 효율적이지만, 노드의 연결과 해제에 추가적인 시간이 소요됩니다.

2-2. 배열 구조의 스택을 위한 데이터

배열 구조의 스택을 구현할 때, 고정된 크기의 배열을 사용하여 스택의 용량(capacity)을 설정할 수 있습니다. 이때 top 변수는 스택의 현재 상단 위치를 가리킵니다.

2-3. 스택의 연산

스택에서 사용할 주요 연산은 다음과 같습니다.

• push: 리스트의 끝에 항목을 추가합니다.
• pop: 리스트의 끝에서 항목을 제거하고 반환합니다.
• peek: 리스트의 끝에 있는 항목을 제거하지 않고 반환합니다.
• is_empty: 리스트가 비어 있는지 확인합니다.
• size: 리스트에 있는 항목의 개수를 반환합니다.

다음은 고정된 크기의 배열을 사용하여 스택을 구현한 예제와 데이터를 추가하고 제거하는 예제입니다.

class ArrayStack:
    def __init__(self, capacity=10):
        # 스택의 용량을 설정하고 배열을 초기화합니다.
        self.capacity = capacity
        self.array = [None] * capacity
        self.top = -1  # 스택의 상단을 가리키는 포인터를 초기화합니다.

    def is_empty(self):
        # 스택이 비어 있는지 확인합니다.
        return self.top == -1

    def is_full(self):
        # 스택이 가득 찼는지 확인합니다.
        return self.top == self.capacity - 1

    def push(self, item):
        # 스택의 상단에 항목을 추가합니다.
        if self.is_full():
            # 스택이 가득 찼으면 예외를 발생시킵니다.
            raise OverflowError("push to full stack")
        self.top += 1  # 상단 포인터를 증가시킵니다.
        self.array[self.top] = item  # 새로운 항목을 상단에 추가합니다.

    def pop(self):
        # 스택의 상단에서 항목을 제거하고 반환합니다.
        if self.is_empty():
            # 스택이 비어 있으면 예외를 발생시킵니다.
            raise IndexError("pop from empty stack")
        item = self.array[self.top]  # 상단의 항목을 가져옵니다.
        self.array[self.top] = None  # 상단의 항목을 None으로 설정하여 슬롯을 비웁니다.
        self.top -= 1  # 상단 포인터를 감소시킵니다.
        return item  # 상단의 항목을 반환합니다.

    def peek(self):
        # 스택의 상단에 있는 항목을 제거하지 않고 반환합니다.
        if self.is_empty():
            # 스택이 비어 있으면 예외를 발생시킵니다.
            raise IndexError("peek from empty stack")
        return self.array[self.top]  # 상단의 항목을 반환합니다.

    def size(self):
        # 스택에 있는 항목의 개수를 반환합니다.
        return self.top + 1

# 스택 사용 예제
stack = ArrayStack(10)
stack.push(1)  # 스택에 1을 추가합니다.
stack.push(2)  # 스택에 2를 추가합니다.
stack.push(3)  # 스택에 3을 추가합니다.
print(stack.pop())  # 출력: 3 (스택의 상단에서 3을 제거하고 반환합니다.)
print(stack.peek()) # 출력: 2 (스택의 상단에 있는 2를 제거하지 않고 반환합니다.)
print(stack.size()) # 출력: 2 (스택에 있는 항목의 개수를 반환합니다.)

2-4. 스택을 클래스로 구현

자료구조는 함수를 기반으로 하는 절차적 프로그래밍보다 클래스를 기반으로 하는 객체 지향 프로그래밍 기법을 이용해 구현하는 것이 훨씬 좋습니다. 이는 자료구조의 추상자료형이 클래스의 개념과 정확히 일치하기 때문입니다. 다음은 파이썬에서 배열 구조를 사용하여 스택을 구현한 예제입니다.

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

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

    def push(self, item):
        self.items.append(item)

    def pop(self):
        if not self.is_empty():
            return self.items.pop()
        else:
            raise IndexError("pop from empty stack")

    def peek(self):
        if not self.is_empty():
            return self.items[-1]
        else:
            raise IndexError("peek from empty stack")

    def size(self):
        return len(self.items)

구현한 스택 클래스를 이용하여 데이터를 스택에 추가하고 제거하는 예제는 다음과 같습니다.

# 스택 사용 예제
stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)
print(stack.pop())  # 출력: 3
print(stack.peek()) # 출력: 2
print(stack.size()) # 출력: 2

이처럼 배열 구조를 사용한 스택 구현은 간단하고 효율적입니다. 리스트의 끝부분을 스택의 상단으로 간주하여 데이터를 추가하고 제거할 수 있습니다.

---

03. 스택의 활용 예제: 괄호 검사 프로그램

스택은 괄호의 짝이 맞는지 확인하는 문제에 유용하게 활용될 수 있습니다. 이 섹션에서는 스택을 사용하여 괄호의 짝을 검사하는 알고리즘과 이를 구현한 프로그램을 살펴보겠습니다.

3-1. 괄호 검사 알고리즘

괄호 검사 알고리즘은 문자열에 있는 괄호들이 올바르게 짝지어져 있는지 확인합니다. 이 알고리즘은 다음과 같이 동작합니다:

1. 문자열을 처음부터 끝까지 순회합니다.
2. 여는 괄호가 나오면 스택에 push 합니다.
3. 닫는 괄호가 나오면 스택에서 pop 하여 짝이 맞는 여는 괄호인지 확인합니다.
4. 문자열의 끝까지 검사했을 때 스택이 비어 있으면 모든 괄호가 올바르게 짝지어져 있는 것입니다.
5. 스택이 비어 있지 않거나 짝이 맞지 않는 경우, 괄호가 올바르게 짝지어져 있지 않은 것입니다.

3-1. 괄호 검사 프로그램

다음은 파이썬에서 스택을 사용하여 괄호의 짝을 검사하는 프로그램입니다.

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

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

    def push(self, item):
        self.items.append(item)

    def pop(self):
        if not self.is_empty():
            return self.items.pop()
        else:
            raise IndexError("pop from empty stack")

    def peek(self):
        if not self.is_empty():
            return self.items[-1]
        else:
            raise IndexError("peek from empty stack")

    def size(self):
        return len(self.items)

def is_balanced(expression):
    stack = Stack()
    # 괄호의 짝을 맞추기 위한 딕셔너리
    pairs = {')': '(', '}': '{', ']': '['}

    for char in expression:
        if char in pairs.values():
            # 여는 괄호를 스택에 추가
            stack.push(char)
        elif char in pairs.keys():
            # 닫는 괄호가 나오면 스택에서 여는 괄호를 제거하고 짝이 맞는지 확인
            if stack.is_empty() or stack.pop() != pairs[char]:
                return False

    # 모든 괄호가 짝이 맞다면 스택이 비어 있어야 함
    return stack.is_empty()

# 괄호 검사 프로그램 사용 예제
print(is_balanced("(a + b) * (c + d)"))  # 출력: True
print(is_balanced("{[a + b] * (c + d)}"))  # 출력: True
print(is_balanced("{[a + b] * (c + d)"))  # 출력: False

주요 함수 설명

• is_balanced: 주어진 표현식의 괄호가 올바르게 짝지어져 있는지 확인합니다.
  • expression: 괄호의 짝을 검사할 문자열입니다.
  • stack: 스택 인스턴스를 생성하여 괄호를 저장합니다.
  • pairs: 닫는 괄호와 여는 괄호의 짝을 맞추기 위한 딕셔너리입니다.
  • 문자열을 순회하면서 여는 괄호는 스택에 push 하고, 닫는 괄호는 스택에서 pop 하여 짝이 맞는지 확인합니다.
  • 모든 괄호를 검사한 후 스택이 비어 있으면 True를 반환하고, 그렇지 않으면 False를 반환합니다.

이 프로그램을 통해 문자열의 괄호가 올바르게 짝지어져 있는지 쉽게 확인할 수 있습니다. 괄호 검사 알고리즘은 컴파일러에서 코드의 구문 오류를 검사하거나 텍스트 에디터에서 괄호 짝을 맞추는 기능 등에 활용될 수 있습니다.

---

04. 파이썬에서 스택 사용하기

파이썬에서 스택을 사용하는 방법은 여러 가지가 있습니다. 이 섹션에서는 파이썬 리스트를 스택으로 사용하는 방법과 queue 모듈의 LifoQueue를 사용하는 방법을 살펴보겠습니다. 이 두 가지 방법을 통해 파이썬에서 스택을 쉽게 구현하고 사용할 수 있습니다. 리스트를 사용하는 방법은 간단하고 직관적이며, LifoQueue를 사용하는 방법은 스레드 안전성을 제공하므로 멀티스레딩 환경에서 유용합니다.

4-1. 파이썬 리스트를 스택으로 사용하기

파이썬의 리스트 자료형은 스택의 연산을 쉽게 지원합니다. 리스트의 append() 메서드로 push 연산을, pop() 메서드로 pop 연산을 수행할 수 있습니다.

다음은 파이썬 리스트를 사용하여 스택을 구현한 예제입니다.

class ListStack:
    def __init__(self):
        # 스택을 구현하기 위해 빈 리스트를 초기화합니다.
        self.items = []

    def is_empty(self):
        # 스택이 비어 있는지 확인합니다.
        return len(self.items) == 0

    def push(self, item):
        # 스택의 상단에 항목을 추가합니다.
        self.items.append(item)

    def pop(self):
        # 스택의 상단에서 항목을 제거하고 반환합니다.
        if not self.is_empty():
            return self.items.pop()
        else:
            # 스택이 비어 있으면 예외를 발생시킵니다.
            raise IndexError("pop from empty stack")

    def peek(self):
        # 스택의 상단에 있는 항목을 제거하지 않고 반환합니다.
        if not self.is_empty():
            return self.items[-1]
        else:
            # 스택이 비어 있으면 예외를 발생시킵니다.
            raise IndexError("peek from empty stack")

    def size(self):
        # 스택에 있는 항목의 개수를 반환합니다.
        return len(self.items)

# 리스트를 사용한 스택 사용 예제
stack = ListStack()
stack.push(1)  # 스택에 1을 추가합니다.
stack.push(2)  # 스택에 2를 추가합니다.
stack.push(3)  # 스택에 3을 추가합니다.
print(stack.pop())  # 출력: 3 (스택의 상단에서 3을 제거하고 반환합니다.)
print(stack.peek()) # 출력: 2 (스택의 상단에 있는 2를 제거하지 않고 반환합니다.)
print(stack.size()) # 출력: 2 (스택에 있는 항목의 개수를 반환합니다.)

주요 메서드 설명

이 코드에서는 Stack 클래스를 정의하고, 파이썬의 리스트를 내부적으로 사용하여 스택을 구현하였습니다. 각 메서드의 역할은 다음과 같습니다.

• __init__() 메서드: 스택을 초기화합니다. 여기서는 비어 있는 리스트를 self.items에 저장합니다.
• is_empty() 메서드: 스택이 비어 있는지 여부를 반환합니다. 리스트의 길이가 0이면 비어 있는 것으로 판단합니다.
• isFull(): 파이썬 리스트는 용량이 무한대이므로 스택의 포화상태는 의미가 없으며 항상 false입니다.
• push(item) 메서드: 스택의 맨 위에 데이터를 추가합니다. 리스트의 append() 메서드를 사용하여 구현합니다.
• pop() 메서드: 스택의 맨 위에서 데이터를 제거하고 반환합니다. 리스트의 pop() 메서드를 사용하며, 스택이 비어 있는 경우 IndexError를 발생시킵니다.
• peek() 메서드: 스택의 맨 위에 있는 데이터를 반환하지만 제거하지는 않습니다. 리스트의 인덱스 -1(리스트의 마지막 요소를 음수로 표현)을 사용하여 구현하며, 스택이 비어 있는 경우 IndexError를 발생시킵니다.
• size() 메서드: 스택에 저장된 데이터의 개수를 반환합니다. 리스트의 길이를 반환합니다.

---

4-2. queue 모듈의 LifoQueue 사용하기

파이썬의 queue 모듈에서는 LifoQueue 클래스를 제공하여 스택을 간편하게 구현할 수 있습니다. 이를 통해 추가적인 스택 구현 없이도 다양한 문제를 해결할 수 있습니다.

다음은 queue 모듈의 LifoQueue를 사용한 예제입니다.

from queue import LifoQueue

# LifoQueue 객체 생성
stack = LifoQueue()

# 데이터 추가 (push)
stack.put(1)
stack.put(2)
stack.put(3)

# 스택의 크기 확인
print("스택의 크기:", stack.qsize())

# 데이터 제거 및 반환 (pop)
print("pop:", stack.get())

# 스택의 크기 다시 확인
print("스택의 크기:", stack.qsize())

# peek 기능 구현 (맨 위 데이터 확인)
def peek(stack):
    if not stack.empty():
        top_element = stack.get()
        stack.put(top_element)
        return top_element
    else:
        raise IndexError("peek from empty stack")

# peek 함수 사용 예제
print("peek:", peek(stack))

# 스택의 크기 확인 (peek 함수는 데이터를 제거하지 않음)
print("스택의 크기:", stack.qsize())

주요 메서드 설명

위 예제에서는 LifoQueue 객체를 생성하고, put() 메서드를 사용하여 데이터를 스택에 추가하고(push), get() 메서드를 사용하여 데이터를 스택에서 제거하고 반환합니다(pop). 스택의 현재 크기를 확인하기 위해 qsize() 메서드를 사용할 수 있습니다.

또한, peek() 메서드는 LifoQueue 클래스에 직접적으로 포함되어 있지 않기 때문에, 별도로 함수를 정의하여 스택의 맨 위 데이터를 확인하는 기능을 구현했습니다. 이 함수는 스택에서 데이터를 제거하지 않고 조회하는 방식으로 동작합니다.

---

05. 시스템스택과 순환호출

시스템스택(System Stack)과 순환호출(Recursion)은 프로그래밍에서 중요한 개념입니다. 각각의 개념을 간단히 설명하고, 어떻게 상호작용하는지에 대해 알아보겠습니다.

5-1. 시스템스택(System Stack)

시스템스택은 함수 호출을 관리하기 위해 사용되는 메모리 영역입니다. 일반적으로 각 함수 호출은 스택 메모리에 프레임(Frame)이라고 불리는 데이터 구조로 저장됩니다. 각 프레임은 함수의 인수, 로컬 변수 및 함수가 반환될 위치 등의 정보를 포함합니다.

시스템스택의 주요 특성은 다음과 같습니다:

• LIFO (Last In, First Out): 함수 호출이 스택에 쌓이고, 가장 최근에 호출된 함수가 가장 먼저 반환됩니다.
• 재귀 호출 관리: 재귀 함수 호출 시 각 재귀 호출은 새로운 프레임을 시스템스택에 추가합니다. 이를 통해 재귀 호출이 깊어질 때마다 시스템스택도 그에 맞게 증가합니다.

시스템스택의 크기는 제한되어 있기 때문에, 너무 많은 재귀 호출이나 너무 깊은 재귀 호출은 스택 오버플로우(Stack Overflow)를 일으킬 수 있습니다. 이는 스택이 최대 용량을 초과하여 시스템이 더 이상 함수 호출을 처리할 수 없게 되는 상황을 말합니다.

5-2. 순환호출(Recursion)

순환호출은 함수가 자기 자신을 직접 또는 간접적으로 호출하는 것을 말합니다. 이는 다양한 알고리즘과 문제 해결 방법에서 유용하게 사용됩니다. 주요 특성은 다음과 같습니다:

• 기본 사례(Base case): 재귀 함수는 자신을 계속 호출하는데, 이를 멈추기 위한 종료 조건이 필요합니다. 이 종료 조건을 기본 사례라고 합니다.
• 재귀 사례(Recursive case): 기본 사례를 만족하지 않을 때 자신을 호출하여 작은 문제로 분해하고 해결합니다.
• 스택을 사용한 구현: 대부분의 프로그래밍 언어에서 재귀 호출은 내부적으로 시스템스택을 사용하여 구현됩니다. 각 재귀 호출은 새로운 프레임을 시스템스택에 추가하게 됩니다.

5-3. 시스템스택과 순환호출의 상호작용

재귀 호출을 사용하면, 시스템스택에 여러 개의 재귀 호출 프레임이 차례로 쌓이게 됩니다. 각 재귀 호출은 자신의 프레임을 스택에 추가하고, 기본 사례가 나타날 때까지 계속해서 새로운 프레임을 추가하게 됩니다. 재귀 호출이 깊어지면 시스템스택도 그에 맞게 깊어지게 됩니다.

예를 들어, 팩토리얼을 구하는 재귀 함수를 살펴보면

def factorial(n):
    if n == 0:
        return 1
    else:
        return n * factorial(n - 1)

이 함수는 자신을 계속 호출하여 팩토리얼 값을 계산합니다. 호출이 깊어질수록 시스템스택도 그에 맞게 깊어지게 됩니다. 따라서 재귀 호출을 사용할 때는 시스템스택의 크기 제한을 고려하여 스택 오버플로우를 방지할 필요가 있습니다.

결론적으로, 시스템스택과 순환호출은 프로그래밍에서 중요한 개념이며, 재귀 호출을 통해 스택을 활용하는 것은 다양한 알고리즘 및 문제 해결에 유용하게 사용됩니다.

---

06. 핵심 내용👀