1- """ A Stack using a Linked List like structure """
2- from typing import Any , Optional
1+ """ A Stack using a linked list like structure """
2+ from typing import Any
33
44
55class Node :
6- def __init__ (self , data : Any , next : Optional ["Node" ] = None ):
7- self .data : Any = data
8- self .next : Optional ["Node" ] = next
6+ def __init__ (self , data ):
7+ self .data = data
8+ self .next = None
9+
10+ def __str__ (self ):
11+ return f"{ self .data }
912
1013
1114class LinkedStack :
@@ -19,7 +22,7 @@ class LinkedStack:
1922 >>> stack.push(5)
2023 >>> stack.push(9)
2124 >>> stack.push('python')
22- >>> stack.is_empty();
25+ >>> stack.is_empty()
2326 False
2427 >>> stack.pop()
2528 'python'
@@ -39,29 +42,116 @@ class LinkedStack:
3942 """
4043
4144 def __init__ (self ) -> None :
42- self .top : Optional [Node ] = None
45+ self .top = None
46+
47+ def __iter__ (self ):
48+ node = self .top
49+ while node :
50+ yield node .data
51+ node = node .next
52+
53+ def __str__ (self ):
54+ """
55+ >>> stack = LinkedStack()
56+ >>> stack.push("c")
57+ >>> stack.push("b")
58+ >>> stack.push("a")
59+ >>> str(stack)
60+ 'a->b->c'
61+ """
62+ return "->" .join ([str (item ) for item in self ])
63+
64+ def __len__ (self ):
65+ """
66+ >>> stack = LinkedStack()
67+ >>> len(stack) == 0
68+ True
69+ >>> stack.push("c")
70+ >>> stack.push("b")
71+ >>> stack.push("a")
72+ >>> len(stack) == 3
73+ True
74+ """
75+ return len (tuple (iter (self )))
4376
4477 def is_empty (self ) -> bool :
45- """ returns boolean describing if stack is empty """
78+ """
79+ >>> stack = LinkedStack()
80+ >>> stack.is_empty()
81+ True
82+ >>> stack.push(1)
83+ >>> stack.is_empty()
84+ False
85+ """
4686 return self .top is None
4787
4888 def push (self , item : Any ) -> None :
49- """ append item to top of stack """
50- node : Node = Node (item )
51- if self .is_empty ():
52- self .top = node
53- else :
54- # each node points to the item "lower" in the stack
89+ """
90+ >>> stack = LinkedStack()
91+ >>> stack.push("Python")
92+ >>> stack.push("Java")
93+ >>> stack.push("C")
94+ >>> str(stack)
95+ 'C->Java->Python'
96+ """
97+ node = Node (item )
98+ if not self .is_empty ():
5599 node .next = self .top
56- self .top = node
100+ self .top = node
57101
58102 def pop (self ) -> Any :
59- """ returns and removes item at top of stack """
103+ """
104+ >>> stack = LinkedStack()
105+ >>> stack.pop()
106+ Traceback (most recent call last):
107+ ...
108+ IndexError: pop from empty stack
109+ >>> stack.push("c")
110+ >>> stack.push("b")
111+ >>> stack.push("a")
112+ >>> stack.pop() == 'a'
113+ True
114+ >>> stack.pop() == 'b'
115+ True
116+ >>> stack.pop() == 'c'
117+ True
118+ """
60119 if self .is_empty ():
61120 raise IndexError ("pop from empty stack" )
62- else :
63- # "remove" element by having top point to the next one
64- assert isinstance (self .top , Node )
65- node : Node = self .top
66- self .top = node .next
67- return node .data
121+ assert isinstance (self .top , Node )
122+ pop_node = self .top
123+ self .top = self .top .next
124+ return pop_node .data
125+
126+ def peek (self ) -> Any :
127+ """
128+ >>> stack = LinkedStack()
129+ >>> stack.push("Java")
130+ >>> stack.push("C")
131+ >>> stack.push("Python")
132+ >>> stack.peek()
133+ 'Python'
134+ """
135+ if self .is_empty ():
136+ raise IndexError ("peek from empty stack" )
137+ return self .top .data
138+
139+ def clear (self ) -> None :
140+ """
141+ >>> stack = LinkedStack()
142+ >>> stack.push("Java")
143+ >>> stack.push("C")
144+ >>> stack.push("Python")
145+ >>> str(stack)
146+ 'Python->C->Java'
147+ >>> stack.clear()
148+ >>> len(stack) == 0
149+ True
150+ """
151+ self .top = None
152+
153+
154+ if __name__ == "__main__" :
155+ from doctest import testmod
156+
157+ testmod ()
0 commit comments