-
Notifications
You must be signed in to change notification settings - Fork 2
/
Copy path3-stack-with-1-array.py
157 lines (113 loc) · 2.63 KB
/
3-stack-with-1-array.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
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
144
145
146
147
148
149
150
151
152
153
154
155
156
157
"""
cracking coding interview page #98
Describe how will implement three stack with 1 array
Approach 1: Divide array by 3 (space might be unused)
Approach 2: saving up space
"""
class Stack():
def __init__(self):
self.data = None
self.top = None
self.next = None
def setData(self,data):
self.data = data
def isstackempty(self):
return self.top == None
def print(self):
print("_____")
p = self
while p.next!=None:
print(p.data)
p = p.next
class Array():
def __init__(self,size):
self.a=[None]*size
self.free =0
self.prev_free = -1
def push(self,data,obj):
if self.free !=None:
#array is not full
obj.setData(data)
self.a[self.free] = obj.data
if obj.top is not None:
# stack has other entries
obj.next = obj.top
#top pointer pointing to current free index
obj.top = self.free
#check if there is any empty slot in array
if self.prev_free == -1:
self.free +=1
elif self.prev_free == None:
self.free = None
else:
self.free =self.prev_free
self.prev_free = -1
if self.free is not None and self.free >= len(self.a):
#array is full
self.free = None
else:
print("array is full can't push any more items")
return
def pop(self,obj):
print("pop")
self.prev_free = self.free
self.free = obj.top
self.a[self.free] = None
obj.top = obj.next
return
def print(self):
print("_________")
c = 0
for i in self.a:
print("index[",c,"]",i)
c +=1
print("_________")
# three stack object
sa = Stack()
sb = Stack()
sc = Stack()
a = Array(4)
# a.push("a",sa)
# a.push("b",sa)
# a.push("c",sa)
# # a.push(4,sa)
# a.print()
# a.pop(sa)
# a.print()
# a.pop(sa)
# a.print()
# a.pop(sa)
# a.print()
# a.pop(sa)
# a.print()
a.push("a",sa)
a.push("b",sb)
a.push("c",sc)
a.push("d",sa)
a.print()
print("pop in sc")
a.pop(sc)
a.print()
a.push("e",sc)
a.print()
# print("push 6 in sb")
a.push("f",sb)
# print("pop in sa")
a.pop(sa)
a.print()
# print("pop in sa")
a.pop(sa)
a.print()
# print("push 7 in sb")
a.push(7,sb)
a.print()
# print("push 8 in sb")
# a.push(8,sb)
# a.print()
# print("push 9 in sc")
# a.push(9,sc)
# a.pop(sc)
# a.print()
# print("pop in sa")
# a.pop(sa)
# a.print()