-
Notifications
You must be signed in to change notification settings - Fork 0
/
Stack Array ADT Class
138 lines (111 loc) · 4.6 KB
/
Stack Array ADT Class
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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
"""
-------------------------------------------------------
Array version of the Stack ADT.
-------------------------------------------------------
Author: Ryan Chisholm
__updated__ = "2023-01-23"
-------------------------------------------------------
"""
from copy import deepcopy
class Stack:
def __init__(self):
"""
-------------------------------------------------------
Initializes an is_empty stack. Data is stored in a Python list.
Use: s = Stack()
-------------------------------------------------------
Returns:
a new Stack object (Stack)
-------------------------------------------------------
"""
self._values = [] #stack object
def is_empty(self):
"""
-------------------------------------------------------
Determines if the stack is empty.
Use: b = s.is_empty()
-------------------------------------------------------
Returns:
True if the stack is empty, False otherwise
-------------------------------------------------------
"""
return len(self._values) == 0
def push(self, value):
"""
-------------------------------------------------------
Pushes a copy of value onto the top of the stack.
Use: s.push(value)
-------------------------------------------------------
Parameters:
value - a data element (?)
Returns:
None
-------------------------------------------------------
"""
self._values.append(deepcopy(value))
def pop(self):
"""
-------------------------------------------------------
Pops and returns the top of stack. The value is removed
from the stack. Attempting to pop from an empty stack
throws an exception.
Use: value = s.pop()
-------------------------------------------------------
Returns:
value - the value at the top of the stack (?)
-------------------------------------------------------
"""
assert len(self._values) > 0, "Cannot pop from an empty stack"
value = deepcopy(self._values.pop()) #value popped from top of stack
return value
def peek(self):
"""
-------------------------------------------------------
Returns a copy of the value at the top of the stack.
Attempting to peek at an empty stack throws an exception.
Use: value = s.peek()
-------------------------------------------------------
Returns:
value - a copy of the value at the top of the stack (?)
-------------------------------------------------------
"""
assert len(self._values) > 0, "Cannot peek at an empty stack"
value = deepcopy(self._values[-1]) #value at top of stack
return value
def split_alt(self):
"""
-------------------------------------------------------
Splits the source stack into separate target stacks with values
alternating into the targets. At finish source stack is empty.
Use: target1, target2 = source.split_alt()
-------------------------------------------------------
Returns:
target1 - contains alternating values from source (Stack)
target2 - contains other alternating values from source (Stack)
-------------------------------------------------------
"""
_values = self._values
target1 = Stack()
target2 = Stack()
target = True
while len(_values) != 0:
if target == True:
target1._values.append(_values.pop()) #working directly with _values variable
else:
target2._values.append(_values.pop())
target = not target #switch value each iteration, for alternating lists
return target1, target2
def __iter__(self):
"""
FOR TESTING ONLY
-------------------------------------------------------
Generates a Python iterator. Iterates through the stack
from top to bottom.
Use: for v in s:
-------------------------------------------------------
Returns:
value - the next value in the stack (?)
-------------------------------------------------------
"""
for value in self._values[::-1]:
yield value