FilesExpand file tree

 master

/

linked_stack.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

67 lines (58 loc) · 1.75 KB

 master

/

linked_stack.py

Copy path

Top

File metadata and controls

• Code
• Blame

67 lines (58 loc) · 1.75 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

""" A Stack using a Linked List like structure """

from typing import Any, Optional

class Node:

def __init__(self, data: Any, next: Optional["Node"] = None):

self.data: Any = data

self.next: Optional["Node"] = next

class LinkedStack:

"""

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

"""

def __init__(self) -> None:

self.top: Optional[Node] = None

def is_empty(self) -> bool:

""" returns boolean describing if stack is empty """

return self.top is None

def push(self, item: Any) -> None:

""" append item to top of stack """

node: Node = Node(item)

if self.is_empty():

self.top = node

else:

# each node points to the item "lower" in the stack

node.next = self.top

self.top = node

def pop(self) -> Any:

""" returns and removes item at top of stack """

if self.is_empty():

raise IndexError("pop from empty stack")

else:

# "remove" element by having top point to the next one

assert isinstance(self.top, Node)

node: Node = self.top

self.top = node.next

return node.data