Python 리스트로 스택(Stack)과 큐(Queue) 쉽게 구현하기

개요

이 글에서는 Python 3.x(그 이하 버전 포함)에서 스택(Stack)과 큐(Queue) 자료구조를 리스트(List)를 활용해 구현하는 방법을 알아봅니다. 두 자료구조의 동작 원리와 함께 아래와 같은 핵심 연산을 다룹니다.

• 삽입 연산 – Push(스택), Enqueue(큐)
• 삭제 연산 – Pop(스택), Dequeue(큐)
• 출력 / 순회 연산 – 전체 요소 확인

사전 지식: 리스트와 리스트 연산에 대한 기본 이해
관련 주제: 리스트 조작(List Manipulation)

스택(Stack)이란?

스택은 물건을 하나씩 위로 쌓아 올린 형태의 자료구조입니다. 요소는 들어온 순서의 역순으로 제거되며, 이러한 방식을 LIFO(Last In First Out, 후입선출)라고 합니다. 즉, 가장 마지막에 추가된 요소가 가장 먼저 삭제됩니다.

스택의 주요 연산

• 요소 추가(Push) – 스택의 맨 위(top)에서 요소가 추가되며, 추가된 항목 수만큼 스택의 크기가 증가합니다.
• 요소 삭제(Pop) – 두 가지 경우로 나뉩니다. 스택이 비어 있으면 삭제할 요소가 없어 언더플로(Underflow)가 발생하고, 요소가 존재한다면 맨 위의 요소가 제거되어 스택의 크기가 줄어듭니다.
• 순회 / 출력(Display) – 스택의 모든 요소를 하나씩 방문하여 화면에 표시합니다.

여기에 Peek 기능을 추가하면 요소를 삭제하지 않고도 스택 최상단의 값을 조회할 수 있습니다.

스택의 특징

• 삽입 순서가 그대로 유지됩니다.
• 중복 요소를 허용합니다.
• 동일한 데이터 타입을 저장하는 것이 일반적입니다.
• 수식 파싱(Parsing) 작업 등에서 매우 유용하게 활용됩니다.

스택 구현 예제 코드

def isEmpty(stk): # 스택이 비어 있는지 확인
    if stk == []:
        return True
    else:
        return False

def Push(stk, item): # 스택에 요소 추가
    stk.append(item)
    top = len(stk) - 1

def Pop(stk):
    if isEmpty(stk): # 스택이 비어 있는지 검사
        print("Underflow")
    else: # 스택에서 요소 삭제
        item = stk.pop()
        if len(stk) == 0:
            top = None
        else:
            top = len(stk)
            print("Popped item is " + str(item))

def Display(stk):
    if isEmpty(stk):
        print("Stack is empty")
    else:
        top = len(stk) - 1
        print("Elements in the stack are: ")
        for i in range(top, -1, -1):
            print(str(stk[i]))

# 실행 코드
if __name__ == "__main__":
    stk = []
    top = None
    Push(stk, 1)
    Push(stk, 2)
    Push(stk, 3)
    Push(stk, 4)
    Pop(stk)
    Display(stk)

위 코드는 Python 3.x에서 스택의 기본 기능을 구현한 것입니다. 여러 개의 if-else 문으로 선택지를 제공하면 메뉴 방식(menu-driven) 프로그램으로 확장할 수 있으며, 이 경우에도 스택을 구성하는 핵심 개념은 동일합니다.

아래는 위 프로그램의 실행 결과입니다. input() 함수를 활용하면 사용자 입력 기반으로 동작하도록 만들 수도 있습니다(여기서는 정적 입력을 사용했습니다).

실행 결과

Popped item is 4
Elements in the stack are:
3
2
1

큐(Queue)란?

큐는 요소가 한 줄로 줄 서 있는 형태의 자료구조로, 도착한 순서대로 제거됩니다. 이러한 방식을 FIFO(First In First Out, 선입선출)라고 하며, 먼저 들어온 요소가 먼저 나가게 됩니다.

큐의 주요 연산

• 요소 추가(Enqueue) – 큐의 뒤쪽(rear) 끝에서 요소가 추가되며, 추가된 항목 수만큼 큐의 크기가 증가합니다.
• 요소 삭제(Dequeue) – 큐가 비어 있으면 삭제할 요소가 없어 언더플로가 발생하고, 요소가 존재한다면 앞쪽(front)의 요소가 제거되어 큐의 크기가 줄어듭니다.
• 순회 / 출력(Display) – 큐의 모든 요소를 방문하여 화면에 표시합니다.

마찬가지로 Peek 기능을 추가하면 큐의 앞쪽 또는 뒤쪽 값을 조회할 수 있습니다.

큐의 특징

• 삽입 순서가 그대로 유지됩니다.
• 중복 요소를 허용합니다.
• 동일한 데이터 타입을 저장하는 것이 일반적입니다.
• CPU 작업 스케줄링 등 프로세스 관리에 매우 유용합니다.

큐 구현 예제 코드

# 큐의 뒤쪽(rear)에 요소 추가
def enqueue(data):
    queue.insert(0, data)

# 큐의 앞쪽(front) 요소 제거
def dequeue():
    if len(queue) > 0:
        return queue.pop()
    return ("Queue Empty!")

# 큐의 요소들을 화면에 출력
def display():
    print("Elements on queue are:")
    for i in range(len(queue)):
        print(queue[i])

# 실행 코드
if __name__ == "__main__":
    queue = []
    enqueue(5)
    enqueue(6)
    enqueue(9)
    enqueue(5)
    enqueue(3)
    print("Popped Element is: " + str(dequeue()))
    display()

위 코드는 Python 3.x에서 큐의 기본 기능을 구현한 것입니다. 스택과 마찬가지로 if-else 문을 활용해 메뉴 방식 프로그램으로 확장할 수 있으며, 큐를 구성하는 개념 역시 동일하게 유지됩니다.

실행 결과

Popped Element is: 5
Elements on queue are:
3
5
9
6

마무리

이 글에서는 Python 3.x에서 리스트를 활용해 스택과 큐 자료구조를 구현하는 방법을 배웠습니다. 동일한 알고리즘은 다른 프로그래밍 언어에서도 그대로 응용할 수 있습니다.

참고로 실무 환경에서는 성능을 위해 collections.deque를 사용하는 것이 좋습니다. deque는 양쪽 끝에서 O(1) 시간 복잡도로 삽입과 삭제가 가능해 리스트 기반 구현보다 훨씬 효율적입니다.