I’m trying to implement the Stack Data Structure in Python from scratch. Unfortunately, I have a problem with the pop functionality.
The pop function should delete the top element of the stack. Unfortunately, in my implementation, running pop and then printing the array returns the same array as before the pop function.
How to better implement the pop function? I could do self.top = self.top.prev, but I am not sure if in the Stack Data Structure we have access to previous elements.
# FOLLOWS LIFO
class StackElement:
def __init__(self, value, prev=None, next=None):
self.value = value
self.prev = prev # Not sure if this is available in the Stack DS...
self.next = next
class Stack:
def __init__(self, values):
self.bottom = None
self.top = None
for v in values:
self.push(v)
def __str__(self):
res = [str(x.value) for x in self]
return " -> ".join(res)
def __iter__(self):
current = self.bottom
while current:
yield current
current = current.next
def __len__(self):
res = 0
current = self.bottom
while current:
res += 1
current = current.next
return res
def push(self, value):
if self.bottom is None:
self.bottom = self.top = StackElement(value)
else:
self.top.next = StackElement(value)
self.top = self.top.next
return self.top
def pop(self):
if not self.is_empty():
self.top = None
return self.top
def peek(self):
if not self.is_empty():
return self.top
def is_empty(self):
if len(self) != 0:
return False
return True
if __name__ == "__main__":
s = Stack(["2", "3", "4"])
print(s)
s.push("5")
print(s, s.top.value, s.bottom.value)
s.pop()
print(s, s.top, s.bottom.value)
res = [str(x.value) for x in s]
print(res)
print(s)
Console Output:
2 -> 3 -> 4
2 -> 3 -> 4 -> 5 5 2
2 -> 3 -> 4 -> 5 None 2
['2', '3', '4', '5']
2 -> 3 -> 4 -> 5
New contributor
S.A.D. is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
2
I tried to simplify logic for you. Read added comments to understand. In my opinion, using .next or .previous suits to linked lists.
Code:
# FOLLOWS LIFO
class StackElement:
def __init__(self, value):
self.value = value
class Stack:
def __init__(self, values):
self.values = [] #all values in stack
self.top = -1 #current element index
for v in values:
self.push(v)
def __str__(self):
res = [str(x) for x in self.values]
return " -> ".join(res)
def __iter__(self):
end = 0
while end:
yield self.values[end]
end += 1
def __len__(self):
return len(self.values) #return list size simply
def push(self, value):
self.values.append(value) #assuming if there is no max size of stack, then push at the end of list
self.top += 1 #current index + 1 as one element is added
def pop(self):
if not self.is_empty(): #atleast one element in stack
self.values = self.values[:self.top] #overwrite list without the last element to follow lifo
self.top -= 1 #current index - 1 as one element is removed
def peek(self):
if not self.is_empty():
return self.values[self.top] #return last element in list
def is_empty(self):
if len(self.values) != 0:
return False
return True
if __name__ == "__main__":
s = Stack(["2", "3", "4"])
print(s)
s.push("5")
print(s, s.top)
s.pop()
print(s, s.top)
res = [str(x) for x in s.values]
print(res)
print(s)
Output:
2 -> 3 -> 4
2 -> 3 -> 4 -> 5 3
2 -> 3 -> 4 2
['2', '3', '4']
2 -> 3 -> 4
As programmers, it is better not to overcomplicate code as it saves time and memory. Have a great day!
New contributor
Muzammil Bin Sohail is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.