10월 자료구조 - 스택(Stack)

 

1. 오늘 소개할 자료구조

스택 (Stack)

 

2. 고른 자료구조의 정의

스택(Stack)은 후입선출(LIFO, Last In First Out) 방식으로 작동하는 자료구조입니다. 즉, 마지막에 삽입된 데이터가 가장 먼저 삭제됩니다. 스택은 일반적으로 '푸시(push)'와 '팝(pop)'이라는 두 가지 주요 연산을 지원합니다:

• 푸시(Push): 데이터를 스택에 추가하는 연산
• 팝(Pop): 데이터를 스택에서 제거하는 연산 스택은 우리가 일상에서 사용하는 물건을 쌓아놓은 상태와 비슷합니다. 가장 위에 쌓인 물건부터 먼저 꺼내는 원리입니다.

스택은 다양한 알고리즘에서 사용됩니다. 예를 들어, 괄호 검증 문제나 깊이 우선 탐색(DFS) 알고리즘에서 중요한 역할을 합니다.

 

3. 고른 자료구조를 구현한 파이썬 코드 전문

파이썬에서는 리스트를 활용해 스택을 쉽게 구현할 수 있습니다. 아래는 스택을 구현한 파이썬 코드입니다.

class Stack:
    def __init__(self):
        self.stack = []  # 스택을 저장할 리스트

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

    def push(self, item):
        # 스택에 아이템을 추가
        self.stack.append(item)

    def pop(self):
        # 스택에서 아이템을 제거하고 반환
        if not self.is_empty():
            return self.stack.pop()
        else:
            return "스택이 비어 있습니다."

    def peek(self):
        # 스택의 가장 상단에 있는 아이템을 반환
        if not self.is_empty():
            return self.stack[-1]
        else:
            return "스택이 비어 있습니다."

    def size(self):
        # 스택에 현재 저장된 아이템 수 반환
        return len(self.stack)

# 예시 사용
my_stack = Stack()
my_stack.push(1)
my_stack.push(2)
my_stack.push(3)

print("Top item:", my_stack.peek())  # 가장 위의 아이템 출력
print("Popped item:", my_stack.pop())  # 아이템 제거 및 출력
print("Stack size:", my_stack.size())  # 스택의 크기 출력

 

4. 고른 자료구조의 원리를 어떻게 파이썬으로 구현했는지

위 코드는 스택 자료구조를 파이썬의 클래스로 구현한 예시입니다. 코드 해설을 해보겠습니다.

• 클래스 정의: Stack 클래스를 정의하여 스택을 객체지향적으로 구현합니다. 이 클래스는 스택을 나타내는 리스트 self.stack을 가지고 있습니다.
• __init__ 메서드: 생성자 메서드로, 객체가 생성될 때 빈 리스트 self.stack을 초기화합니다. 이 리스트가 스택을 구성하는 데이터 구조입니다.
• is_empty 메서드: 스택이 비어 있는지 확인하는 메서드입니다. 리스트의 길이가 0이면 스택이 비어 있다는 것을 의미합니다.
• push 메서드: 스택에 아이템을 추가하는 연산입니다. 리스트의 append() 메서드를 사용하여 새로운 아이템을 스택의 가장 위에 추가합니다.
• pop 메서드: 스택에서 아이템을 제거하고 반환하는 연산입니다. 리스트의 pop() 메서드를 사용하여 가장 상단에 있는 아이템을 제거하고 반환합니다. 만약 스택이 비어 있으면 "스택이 비어 있습니다."라는 메시지를 반환하도록 예외 처리를 했습니다.
• peek 메서드: 스택의 가장 상단에 있는 아이템을 반환합니다. pop()과 달리 데이터를 제거하지 않습니다. 리스트의 마지막 아이템([-1])을 반환하며, 스택이 비어 있을 경우 메시지를 반환합니다.
• size 메서드: 현재 스택에 저장된 아이템의 개수를 반환하는 메서드입니다. 이는 리스트의 길이인 len(self.stack)으로 구할 수 있습니다.

 

5. 느낀점

스택은 구현이 간단하면서도 매우 강력한 자료구조입니다. 실제로 많은 알고리즘에서 중요한 역할을 하며, 특히 후입선출(LIFO) 방식이 필요한 경우에 유용합니다. 파이썬에서 리스트를 활용하면 스택을 구현하는 데 매우 직관적이고 쉬운 방법을 제공합니다. 이번 구현을 통해 스택의 원리와 이를 파이썬으로 어떻게 쉽게 구현할 수 있는지에 대해 깊이 이해하게 되었습니다. 또한, 스택을 활용한 다양한 알고리즘 문제들을 풀어보며 더욱 많은 실용적인 사례를 접할 수 있을 것 같다는 생각이 들었습니다.