-
Notifications
You must be signed in to change notification settings - Fork 0
/
linkedstack.py
68 lines (56 loc) · 1.92 KB
/
linkedstack.py
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
68
"""
File: linkedstack.py
Author: Ken Lambert
Editor: Leigh Stauffer
Project 12
"""
from node import Node
from abstractstack import AbstractStack
class LinkedStack(AbstractStack):
"""A link-based stack implementation."""
# Constructor
def __init__(self, sourceCollection = None):
"""Sets the initial state of self, which includes the
contents of sourceCollection, if it's present."""
self._items = None
AbstractStack.__init__(self, sourceCollection)
# Accessor methods
def __iter__(self):
"""Supports iteration over a view of self."""
def visitNodes(node):
"""Adds items to tempList from tail to head."""
if not node is None:
visitNodes(node.next)
tempList.append(node.data)
tempList = list()
visitNodes(self._items)
return iter(tempList)
def peek(self):
"""
Returns the item at the top of the stack.
Precondition: the stack is not empty.
Raises: KeyError if the stack is empty."""
if self.isEmpty():
raise KeyError("The stack is empty.")
return self._items.data
# Mutator methods
def clear(self):
"""Makes self become empty."""
self._size = 0
self._items = None
def push(self, item):
"""Adds item to the top of the stack."""
self._items = Node(item, self._items)
self._size += 1
def pop(self):
"""
Removes and returns the item at the top of the stack.
Precondition: the stack is not empty.
Raises: KeyError if the stack is empty.
Postcondition: the top item is removed from the stack."""
if self.isEmpty():
raise KeyError("The stack is empty.")
data = self._items.data
self._items = self._items.next
self._size -= 1
return data