[자료구조] 스택, 큐, 데크란 무엇이고 어떨때 사용하는가?(+코드 예시 포함) What are stacks, queues, and decks and when do you use them? (+codes example included)

스택(Stack), 큐(Queue), 데크(Deque)는 데이터를 저장하고 관리하는 자료구조로, 컴퓨터 프로그래밍에서 매우 중요한 개념입니다. 각각의 특징과 용도를 살펴보겠습니다.

1. 스택(Stack):
 - 후입선출(LIFO: Last-In-First-Out) 방식을 따르는 자료구조입니다.
 - 데이터를 삽입(push)하거나 삭제(pop)할 때 항상 최상단(top)에서 수행됩니다.
 - 가장 최근에 삽입된 데이터가 가장 먼저 삭제됩니다.
 - 함수 호출과 복귀 주소 저장, 임시 데이터 저장 등에 사용됩니다.
 - 주요 연산: push(삽입), pop(삭제), top(최상단 데이터 확인), isEmpty(비어있는지 확인)

1-1. 스택(Stack) 예시 - 마트 카트 쌓기와 물건 빼기:
마트에서 물건을 살 때, 마트 카트에 물건을 쌓아올리는 것을 스택의 동작과 비교할 수 있습니다. 카트의 맨 위에 새로운 물건을 추가할 때는 항상 카트의 가장 위에 놓게 됩니다. 이후에 물건을 꺼낼 때도 항상 가장 위에 있는 물건부터 꺼냅니다. 가장 최근에 삽입된 물건이 가장 먼저 꺼내지는 후입선출(LIFO) 방식이 스택과 유사합니다.

1-2. 예시 코드

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

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

    def pop(self):
        if not self.is_empty():
            return self.items.pop()

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

# 마트 카트에 물건 쌓기
mart_cart = Stack()
mart_cart.push("사과")
mart_cart.push("바나나")
mart_cart.push("딸기")

# 물건 빼기 (가장 최근에 쌓은 물건부터 빼냄)
while not mart_cart.is_empty():
    print(mart_cart.pop())

딸기
바나나
사과

 

2. 큐(Queue):
 - 선입선출(FIFO: First-In-First-Out) 방식을 따르는 자료구조입니다.
 - 데이터를 삽입(enqueue)하거나 삭제(dequeue)할 때 가장 앞(front)에서 수행됩니다.
 - 가장 먼저 삽입된 데이터가 가장 먼저 삭제됩니다.
 - 태스크 처리, 작업 대기열, 네트워크 패킷 처리 등에 사용됩니다.
 - 주요 연산: enqueue(삽입), dequeue(삭제), front(가장 앞 데이터 확인), isEmpty(비어있는지 확인)

2-1. 큐(Queue) 예시 - 마트 카트 앞에서 물건 추가와 뒤에서 물건 빼기:
마트에서 계산 대기열에 들어간 물건을 큐의 동작과 비교할 수 있습니다. 마트 카트 앞에서 새로운 물건을 추가하면 기존에 있는 물건들보다 먼저 계산 대기열에 들어가게 됩니다. 이후에 물건을 계산할 때는 가장 먼저 카트 앞에 있던 물건부터 계산을 진행합니다. 먼저 들어온 물건이 먼저 빠져나가는 선입선출(FIFO) 방식이 큐와 유사합니다.

2-2. 예시코드

from collections import deque

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

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

    def dequeue(self):
        if not self.is_empty():
            return self.items.popleft()

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

# 마트 카트에 물건 추가하기
mart_cart = Queue()
mart_cart.enqueue("사과")
mart_cart.enqueue("바나나")
mart_cart.enqueue("딸기")

# 물건 빼기 (가장 먼저 들어온 물건부터 빼냄)
while not mart_cart.is_empty():
    print(mart_cart.dequeue())

사과
바나나
딸기

3.데크(Deque, Double-Ended Queue):
 - 양쪽 끝에서 삽입과 삭제가 모두 가능한 자료구조입니다.
 - 스택과 큐를 합친 형태로, 양방향으로 데이터를 처리할 수 있습니다.
 - 스크롤, 윈도우 화면 관리, 웹 브라우저의 방문 기록 등에 사용됩니다.
 - 주요 연산: pushFront(앞에 삽입), pushBack(뒤에 삽입), popFront(앞에서 삭제),
 - popBack(뒤에서 삭제), front(앞 데이터 확인), back(뒤 데이터 확인), isEmpty(비어있는지 확인)

반응형

3-1. 데크(Deque) 예시 - 마트 카트 양쪽에서 물건 추가와 빼기:
데크는 양쪽에서 삽입과 삭제가 모두 가능한 자료구조입니다. 마트 카트의 앞과 뒤에서 물건을 추가하고 빼는 것을 데크와 비교할 수 있습니다. 데크는 양방향으로 데이터를 처리할 수 있으므로, 마트 카트의 앞과 뒤에 모두 물건을 쌓을 수 있고, 양쪽 끝에서 물건을 꺼낼 수 있습니다.

 

3-.2 예시코드 

from collections import deque

# 마트 카트에 물건 추가하기
mart_cart = deque()
mart_cart.appendleft("사과")  # 앞에 삽입
mart_cart.append("바나나")     # 뒤에 삽입
mart_cart.appendleft("딸기")  # 앞에 삽입

# 물건 빼기 (양쪽 끝에서 물건 꺼냄)
print(mart_cart.pop())      # 뒤에서 꺼냄
print(mart_cart.popleft())  # 앞에서 꺼냄
print(mart_cart.pop())      # 뒤에서 꺼냄

딸기
사과
바나나

스택과 큐, 데크는 각각의 특성에 따라 다양한 상황에서 유용하게 활용됩니다. 프로그래밍에서 적절하게 선택하여 사용하면 효율적인 알고리즘과 자료 구조를 구현하는 데 도움이 됩니다. 이러한 자료구조들은 컴퓨터 과학과 소프트웨어 공학에서 핵심적인 개념이므로, 꼭 익숙해지는 것이 좋습니다.