Stack

• 선입후출 구조(먼저 들어온 것이 나중에 나온다.)

• push->값을 삽입한다.

• pop->가장 마지막에 삽입된 값을 뽑는다.

Stack with type

from typing import Generic, TypeVar, Optional

"""
[Node class]
- item
- pointer:다음 Node를 가르킨다.(마지막은 None)
[LinkedList]
- head:가장 첫번째 node,node가 없으면 None을 가르킨다.
- length:int ,현재 노드의 갯수를 가르킨다.

[Stack] :LinkedList를 상속받는다

- push(item):item을 받아 노드를 만든 후 삽입
- pop():마지막 노드를 제거하고 해당 Item을 반환한다.

"""

T = TypeVar("T", int, str, float)
N = Optional["Node"]


class Node(Generic[T]):
    __slots__ = ["__item", "__next"]

    def __init__(self, item: T, next: N = None):
        self.__item: T = item
        self.__next: N = next

    @property
    def item(self) -> T:
        return self.__item

    @item.setter
    def item(self, new_item: T):
        self.__item = new_item

    @property
    def next(self) -> N:
        return self.__next

    @next.setter
    def next(self, new_next: N):
        self.__next = new_next


class LinkedList:
    __slots__ = ["__head", "test"]

    def __init__(self):
        self.__head: N = None

    @property
    def head(self) -> N:
        return self.__head

    @head.setter
    def head(self, new_head: N):
        self.__head = new_head

    @property
    def length(self) -> int:
        if self.__head is None:
            return 0
        cnt: int = 1
        cur_node: "Node" = self.__head
        while cur_node.next is not None:
            cur_node = cur_node.next
            cnt += 1
        return cnt

    def __str__(self) -> str:
        result: str = ""
        if self.__head is None:
            return result

        cur_node: "Node" = self.__head
        result += f"{cur_node.item}"
        while cur_node.next is not None:
            cur_node = cur_node.next
            result += f", {cur_node.item}"
        return result


class Stack(Generic[T], LinkedList):
    def push(self, item: T):
        new_node: Node[T] = Node[T](item)
        if self.head is None:
            self.head = new_node
            return
        cur_node: "Node" = self.head
        while cur_node.next is not None:
            cur_node = cur_node.next
        cur_node.next = new_node

    def pop(self) -> Optional[T]:
        if self.head is None:
            raise ValueError("stack is empty")
        else:
            cur_node: "Node" = self.head
            if cur_node.next is None:
                self.head = None
                return cur_node.item
            next_node: "Node" = cur_node.next
            while next_node.next is not None:
                cur_node = next_node
                next_node = next_node.next
            cur_node.next = None
            return next_node.item


if __name__ == "__main__":
    stack1 = Stack[int]()
    print(stack1.length)
    stack1.push(10)
    stack1.push(20)
    stack1.push(30)
    stack1.push(40)
    print(stack1.length)
    print(stack1)

    print(stack1.pop())
    print(stack1.pop())
    print(stack1.length)
    print(stack1)

0
4
10, 20, 30, 40
40
30
2
10, 20