Queue

Queue

Queue란

선입선출(First In First Out) 특성을 지니는 자료구조를 말한다.

예로 들어 1차선 터널의 구조와 유사하다.

추상 자료형

위키피디아의 요구사항에 따라 구현되었다.

필수

• Enqueue: 요소를 큐에 삽입한다.
• Dequeue: 요소를 큐에서 꺼낸다. 꺼낼 요소가 없는 경우 예외가 발생한다.

비필수

• Peek: 요소를 꺼내지 않고 가장 앞 요소를 반환한다. 요소가 하나도 없는 경우 예외가 발생한다.
• Empty: 스택에 아무 요소도 포함되어있지 않으면 True, 아니면 False를 반환한다.
• Size: 스택에 삽입되어 있는 요소의 갯수를 반한한다.

구현

Deque 기반 구현

python에서 제공하는 deque를 활용.
아래 코드처럼, '인터페이스 변환 목적으로 감싸는 형태'를 디자인 패턴에서는 어뎁터 패턴이라고 한다.

from abc import ABCMeta, abstractmethod
from collections import deque
from typing import Generic, Iterable, TypeVar

T = TypeVar("T")


class AbstractQueue(Generic[T], metaclass=ABCMeta):
    @abstractmethod
    def enqueue(self, __object: T) -> None:
        ...

    @abstractmethod
    def dequeue(self) -> T:
        ...


class UnderflowError(RuntimeError):
    ...


class Queue(AbstractQueue[T]):
    def __init__(self, iterable: Iterable[T] | None = None):
        self._queue: deque[T] = deque()
        if iterable:
            for data in iterable:
                self.enqueue(data)

    def enqueue(self, data: T) -> None:
        self._queue.append(data)

    def dequeue(self) -> T:
        try:
            return self._queue.popleft()
        except IndexError:
            raise UnderflowError("dequeue from empty queue")

    def peek(self) -> T:
        try:
            return self._queue[0]
        except IndexError:
            raise UnderflowError("peek from empty queue")

    def __bool__(self) -> bool:  # or "empty"
        return bool(self._queue)

    def __len__(self) -> int:  # or "size"
        return len(self._queue)


queue = Queue([1, 2, 3, 4])

queue.enqueue(5)  # enqueue
assert len(queue) == 5  # size
assert queue.dequeue() == 1  # dequeue
assert queue.peek() == 2  # peek

temp: list[int] = []
while queue:  # empty
    temp.append(queue.dequeue())
assert temp == [2, 3, 4, 5]

Linked list 기반 구현

from abc import ABCMeta, abstractmethod
from dataclasses import dataclass
from typing import Generic, Iterable, TypeVar

from typing_extensions import Self

T = TypeVar("T")


class AbstractQueue(Generic[T], metaclass=ABCMeta):
    @abstractmethod
    def enqueue(self, __object: T) -> None:
        ...

    @abstractmethod
    def dequeue(self) -> T:
        ...


@dataclass(slots=True)
class Node(Generic[T]):
    data: T
    next: Self | None = None


class UnderflowError(RuntimeError):
    ...


class Queue(AbstractQueue[T]):
    def __init__(self, iterable: Iterable[T] | None = None):
        self._head: Node[T] | None = None
        self._tail: Node[T] | None = None
        self._size: int = 0
        if iterable:
            for data in iterable:
                self.enqueue(data)

    def enqueue(self, data: T) -> None:
        new_node = Node(data)
        if not (self._head and self._tail):
            self._head = new_node
            self._tail = new_node
        else:
            self._tail.next = new_node
            self._tail = self._tail.next
        self._size += 1
        return

    def dequeue(self) -> T:
        if not self._head:
            raise UnderflowError("pop from empty queue")
        result = self._head.data
        self._head = self._head.next
        if not self._head:
            self._tail = None
        self._size -= 1
        return result

    def peek(self) -> T:
        if not self._head:
            raise UnderflowError("top from empty queue")
        return self._head.data

    def __bool__(self) -> bool:  # or "empty"
        return self._head is not None

    def __len__(self) -> int:  # or "size"
        return self._size


queue = Queue([1, 2, 3, 4])

queue.enqueue(5)  # enqueue
assert len(queue) == 5  # size
assert queue.dequeue() == 1  # dequeue
assert queue.peek() == 2  # peek

temp: list[int] = []
while queue:  # empty
    temp.append(queue.dequeue())
assert temp == [2, 3, 4, 5]