Python 데이터 구조 - 스택(Stack)과 큐(Queue) 완벽 가이드

Python Logo

 

개발을 오래 하다 보면 특정 데이터 구조가 얼마나 중요한지 알게 됩니다. 특히 스택과 큐는 알고리즘을 구현하거나 시스템 설계를 할 때 필수적인 구조입니다. Java와 같은 언어를 다뤄왔던 입장에서, Python에서 이 구조들을 활용하는 방식이 다소 직관적이어서 초보자들이 배우기 좋다고 생각해요. 스택과 큐의 개념을 잘 이해해 두면 이후의 알고리즘 문제 풀이에서도 큰 도움이 될 것입니다. 기초를 탄탄히 다지기 위해 천천히 따라해 보시기 바랍니다.

---

1. 스택(Stack)과 큐(Queue)란 무엇인가?

스택과 큐는 프로그래밍에서 기본이 되는 데이터 구조입니다. 이 두 구조는 데이터를 순서대로 처리하고 관리하는 방식이 다릅니다. 각 구조의 특성과 사용법을 알아봅시다.

1.1 스택(Stack)의 개념

스택은 LIFO(Last In, First Out) 구조입니다. 즉, 가장 마지막에 추가된 데이터가 가장 먼저 나가는 구조입니다. 흔히 접시를 쌓는 것과 비교할 수 있는데, 가장 위에 있는 접시를 먼저 꺼내는 것처럼 스택도 마지막에 들어간 데이터가 먼저 제거됩니다.

스택의 기본 연산

• push: 데이터를 스택의 맨 위에 추가합니다.
• pop: 스택의 맨 위에 있는 데이터를 제거하고 반환합니다.
• peek: 스택의 맨 위에 있는 데이터를 제거하지 않고 확인합니다.
• is_empty: 스택이 비어있는지 확인합니다.

# 스택 구현 예제 (리스트 사용)
stack = []

# push 연산
stack.append(1)
stack.append(2)
stack.append(3)

# pop 연산
print(stack.pop())  # 출력: 3
print(stack.pop())  # 출력: 2

# 스택 상태
print(stack)  # 출력: [1]

1.2 큐(Queue)의 개념

큐는 FIFO(First In, First Out) 구조입니다. 즉, 가장 먼저 들어온 데이터가 가장 먼저 나가는 구조입니다. 줄을 서서 차례를 기다리는 것과 비슷합니다. 처음에 들어온 데이터가 맨 앞에서 처리되고 제거됩니다.

큐의 기본 연산

• enqueue: 데이터를 큐의 맨 뒤에 추가합니다.
• dequeue: 큐의 맨 앞에 있는 데이터를 제거하고 반환합니다.
• peek: 큐의 맨 앞에 있는 데이터를 제거하지 않고 확인합니다.
• is_empty: 큐가 비어있는지 확인합니다.

# 큐 구현 예제 (리스트 사용)
from collections import deque

queue = deque()

# enqueue 연산
queue.append(1)
queue.append(2)
queue.append(3)

# dequeue 연산
print(queue.popleft())  # 출력: 1
print(queue.popleft())  # 출력: 2

# 큐 상태
print(queue)  # 출력: deque([3])

---

2. Python에서 스택 구현하기

Python에서는 스택을 구현하기 위해 보통 리스트를 사용합니다. 리스트는 데이터를 추가하고 제거하는 연산이 편리하기 때문입니다. Python의 리스트는 동적 배열이기 때문에 크기 제한 없이 데이터를 다룰 수 있습니다.

2.1 스택 기본 연산 구현

리스트를 활용한 스택의 기본 연산을 직접 구현해 보겠습니다.

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

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

    def pop(self):
        if not self.is_empty():
            return self.stack.pop()
        return "스택이 비어 있습니다."

    def peek(self):
        if not self.is_empty():
            return self.stack[-1]
        return "스택이 비어 있습니다."

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

• push: 리스트의 append() 메서드를 사용해 스택의 끝에 데이터를 추가합니다.
• pop: 리스트의 pop() 메서드를 사용해 스택의 끝에서 데이터를 제거하고 반환합니다.
• peek: 스택의 마지막 요소를 반환하지만, 제거하지 않습니다.
• is_empty: 스택이 비어있는지 확인합니다.

2.2 스택 예제

# 스택 인스턴스 생성
my_stack = Stack()

# 스택에 데이터 추가
my_stack.push(10)
my_stack.push(20)
my_stack.push(30)

# 스택의 맨 위 데이터 확인
print(my_stack.peek())  # 출력: 30

# 데이터 제거
print(my_stack.pop())   # 출력: 30
print(my_stack.pop())   # 출력: 20

# 스택 상태 확인
print(my_stack.is_empty())  # 출력: False

---

3. Python에서 큐 구현하기

Python에서 큐는 보통 deque(Double-Ended Queue)를 사용하여 구현합니다. 이는 큐 연산에서 효율성을 높여주며, 데이터 삽입과 제거가 매우 빠르게 이루어집니다.

3.1 큐 기본 연산 구현

from collections import deque

class Queue:
    def __init__(self):
        self.queue = deque()

    def enqueue(self, item):
        self.queue.append(item)

    def dequeue(self):
        if not self.is_empty():
            return self.queue.popleft()
        return "큐가 비어 있습니다."

    def peek(self):
        if not self.is_empty():
            return self.queue[0]
        return "큐가 비어 있습니다."

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

• enqueue: append() 메서드를 사용하여 큐의 끝에 데이터를 추가합니다.
• dequeue: popleft() 메서드를 사용하여 큐의 앞에서 데이터를 제거하고 반환합니다.
• peek: 큐의 맨 앞 데이터를 반환하지만, 제거하지 않습니다.
• is_empty: 큐가 비어있는지 확인합니다.

3.2 큐 예제

# 큐 인스턴스 생성
my_queue = Queue()

# 큐에 데이터 추가
my_queue.enqueue("a")
my_queue.enqueue("b")
my_queue.enqueue("c")

# 큐의 맨 앞 데이터 확인
print(my_queue.peek())  # 출력: "a"

# 데이터 제거
print(my_queue.dequeue())  # 출력: "a"
print(my_queue.dequeue())  # 출력: "b"

# 큐 상태 확인
print(my_queue.is_empty())  # 출력: False

---

4. 스택과 큐의 활용 예제

스택과 큐는 다양한 상황에서 유용하게 사용됩니다. 데이터 구조를 관리하거나 알고리즘 문제를 해결할 때 이들을 이해하고 활용하는 것이 중요합니다.

4.1 스택 활용 - 괄호 검증

주어진 문자열에 괄호가 올바르게 열리고 닫혔는지 확인하는 문제는 스택으로 쉽게 해결할 수 있습니다.

def check_brackets(expression):
    stack = []
    for char in expression:
        if char == "(":
            stack.append(char)
        elif char == ")":
            if not stack:
                return False
            stack.pop()
    return len(stack) == 0

print(check_brackets("(())"))  # 출력: True
print(check_brackets("(()"))   # 출력: False

4.2 큐 활용 - 작업 스케줄링

큐는 작업을 순차적으로 처리하는 스케줄러나 BFS(너비 우선 탐색) 알고리즘에서 자주 사용됩니다.

def process_tasks(tasks):
    queue = Queue()
    for task in tasks:
        queue.enqueue(task)
    while not queue.is_empty():
        current_task = queue.dequeue()
        print(f"Processing {current_task}")

tasks = ["Task1", "Task2", "Task3"]
process_tasks(tasks)
# 출력:
# Processing Task1
# Processing Task2
# Processing Task3

---

요약 디스크립션

Python의 스택과 큐는 데이터를 순차적으로 처리하고 관리하는 데 필수적인 데이터 구조입니다. LIFO와 FIFO 구조를 이해하고, 이를 Python에서 어떻게 구현하고 활용할 수 있는지 배워보세요.