-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathstack_queue_samples.py
More file actions
143 lines (104 loc) · 3.4 KB
/
Copy pathstack_queue_samples.py
File metadata and controls
143 lines (104 loc) · 3.4 KB
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
138
139
140
141
142
143
""" This class implements a basic stack.
The module consists of two classes, the StackNode and the stack
itself.
IMPORTANT NOTE: The need to actually a stack of this nature is
almost non-existant in the real world, due to the facilities of Python
lists.
"""
class StackNode():
def __init__(self,data):
""" Initialize a node. The node knows who is points to, which
is the nextNode.
"""
self.data = data
self.prev = None
def __repr__(self):
""" Create representation of this object.
"""
str="Data: " + self.data
if self.prev is None:
str = str + "." + " Pointer node is None"
else:
str=str + "." + " Pointer node data is: " + self.prev.data
return str
class Stack():
def __init__(self,node=None):
""" Create the stack with an initial node, if it is given.
If not given, then the stack is empty. If a node is given,
the size is one.
"""
if node is not None:
self.size = 1
self.top = node
self.bottom = node
node.prev = None
else:
self.size = 0
self.top = None
self.bottom = None
def pretty_print(self):
""" Pretty print the stack. Used for testing purposes. This
will print with the top of the stack fierst.
"""
#start with the first node, and go done the list until you reach
# the last node
if self.size == 0:
print("The stack is empty")
return
elif self.size == 1:
print "The data is: ", self.top.data
return
node = self.top
while node is not None:
print "The data is: ",node.data
node = node.prev
def push(self,node):
""" Push a node to the top of the stack
"""
if self.top is None: # was empty
self.top = node
self.bottom = node
node.prev = None
else:
node.prev = self.top
self.top = node
self.size+=1
def pop(self):
""" Pop the top node off the stack, adjusting accordingly
"""
if self.size == 0:
return None
elif self.size == 1:
node = self.top
self.top = None
self.bottom = None
else:
node = self.top
self.top = node.prev
node.prev = None
self.size = self.size -1
return node
def contains_node(self,test_node):
""" Determine if there is at least one instance of a
a node with the given data. The next pointer in the node
is irrelevant. Note that we could have designed the interface
to accept data and not a node... but it is nice to have
consistency, one way or the other...
Returns the first position where the node was found; else,
returns -1. Positions start at 0
"""
print
if self.size == 0:
return -1
node = self.top
pos = 0
found = False
while node is not None:
if node.data == test_node.data:
found = True
break
node = node.prev
pos += 1
if not found:
pos = -1
return pos