a stack using a linked list like structure from future import annotations from collections abc import iterator from typing import generic typevar t typevart class nodegenerict def initself data t self data data self next nodet none none def strself str return fself data class linkedstackgenerict def initself none self top nodet none none def iterself iteratort node self top while node yield node data node node next def strself str return joinstritem for item in self def lenself int return lentupleiterself def isemptyself bool return self top is none def pushself item t none node nodeitem if not self isempty node next self top self top node def popself t if self isempty raise indexerrorpop from empty stack assert isinstanceself top node popnode self top self top self top next return popnode data def peekself t if self isempty raise indexerrorpeek from empty stack assert self top is not none return self top data def clearself none self top none if name main from doctest import testmod testmod linked list stack implementing push to top pop from top and is_empty stack linkedstack stack is_empty true stack push 5 stack push 9 stack push python stack is_empty false stack pop python stack push algorithms stack pop algorithms stack pop 9 stack pop 5 stack is_empty true stack pop traceback most recent call last indexerror pop from empty stack stack linkedstack stack push c stack push b stack push a str stack a b c stack linkedstack len stack 0 true stack push c stack push b stack push a len stack 3 true stack linkedstack stack is_empty true stack push 1 stack is_empty false stack linkedstack stack push python stack push java stack push c str stack c java python stack linkedstack stack pop traceback most recent call last indexerror pop from empty stack stack push c stack push b stack push a stack pop a true stack pop b true stack pop c true stack linkedstack stack push java stack push c stack push python stack peek python stack linkedstack stack push java stack push c stack push python str stack python c java stack clear len stack 0 true
from __future__ import annotations

from collections.abc import Iterator
from typing import Generic, TypeVar

T = TypeVar("T")


class Node(Generic[T]):
    def __init__(self, data: T):
        self.data = data
        self.next: Node[T] | None = None

    def __str__(self) -> str:
        return f"{self.data}"


class LinkedStack(Generic[T]):
    

    def __init__(self) -> None:
        self.top: Node[T] | None = None

    def __iter__(self) -> Iterator[T]:
        node = self.top
        while node:
            yield node.data
            node = node.next

    def __str__(self) -> str:
        
        return "->".join([str(item) for item in self])

    def __len__(self) -> int:
        
        return len(tuple(iter(self)))

    def is_empty(self) -> bool:
        
        return self.top is None

    def push(self, item: T) -> None:
        
        node = Node(item)
        if not self.is_empty():
            node.next = self.top
        self.top = node

    def pop(self) -> T:
        
        if self.is_empty():
            raise IndexError("pop from empty stack")
        assert isinstance(self.top, Node)
        pop_node = self.top
        self.top = self.top.next
        return pop_node.data

    def peek(self) -> T:
        
        if self.is_empty():
            raise IndexError("peek from empty stack")

        assert self.top is not None
        return self.top.data

    def clear(self) -> None:
        
        self.top = None


if __name__ == "__main__":
    from doctest import testmod

    testmod()