Stack

Stack이란

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

예로 들어 프링글스 통의 형태와도 유사하며, 다른 예로는 책을 읽다가 모르는 단어가 나와 다른 책을 기존 책 위에 펼치고, 또 모르는 단어가 나와 위에 펼치는 형태로 중첩되어 쌓이는 형태를 들 수 있다.

힙 영역에서 일반적인 데이터를 저장할 때 사용되는 스택과 스택 영역 메모리에서 함수 콜 중첩 상태에서 사용되는 스택을 혼동할 수 있다.

추상 자료형

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

필수

• Push: 요소를 스택에 삽입한다.
• Pop: 요소를 스택에서 꺼낸다. 꺼낼 요소가 없는 경우 예외가 발생한다.

비필수

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

구현

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 AbstractStack(Generic[T], metaclass=ABCMeta):
    @abstractmethod
    def push(self, __element: T) -> None:
        ...

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


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


class UnderflowError(RuntimeError):
    ...


class Stack(AbstractStack[T]):
    def __init__(self, iterable: Iterable[T] | None = None):
        self._head: Frame[T] | None = None
        self._size: int = 0
        if iterable:
            for data in iterable:
                self.push(data)

    def push(self, data: T) -> None:
        new_head = Frame(data)
        new_head.next = self._head
        self._head = new_head
        self._size += 1

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

    def top(self) -> T:  # or "peek"
        if not self._head:
            raise UnderflowError("top from empty stack")
        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


stack = Stack((i for i in range(9)))

stack.push(9)  # push
assert len(stack) == 10  # size
assert stack.pop() == 9  # pop
assert stack.top() == 8  # top (or peek)

temp: list[int] = []
while stack:  # not empty
    temp.append(stack.pop())
assert temp == [i for i in range(8, 0 - 1, -1)]

List 활용

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

T = TypeVar("T")


class AbstractStack(Generic[T], metaclass=ABCMeta):
    @abstractmethod
    def push(self, __element: T) -> None:
        ...

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


class UnderflowError(RuntimeError):
    ...


class Stack(AbstractStack[T]):
    def __init__(self, iterable: Iterable[T] | None = None):
        self._list: list[T] = []
        if iterable:
            self._list.extend(iterable)

    def push(self, element: T) -> None:
        self._list.append(element)

    def pop(self) -> T:
        try:
            return self._list.pop()
        except IndexError:
            raise UnderflowError("pop from empty stack")

    def top(self) -> T:  # or "peek"
        try:
            return self._list[-1]
        except IndexError:
            raise UnderflowError("top from empty stack")

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

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


stack = Stack((i for i in range(9)))

stack.push(9)  # push
assert len(stack) == 10  # size
assert stack.pop() == 9  # pop
assert stack.top() == 8  # top (or peek)

temp: list[int] = []
while stack:  # not empty
    temp.append(stack.pop())
assert temp == [i for i in range(8, 0 - 1, -1)]