36
stack in python using LinkedList or List
Stack is a type of data structure. They are preferred over arrays or lists due to their fast insert and delete operations.
Stack works on the last in first out (LIFO)
principle i.e insertion and deletion happens at only one end.
3.stack has an O(1) time complexity for pop or push operation.
look at the code below to understand how to implement stack on our own and how to use it.
Note: We can implement a stack using LinkedList or lists in python. Both implementations work fine and have the same time complexities for all the operations but I prefer implementing them using a list because it's much easier.
class stack:
def __init__(self):
self.data = []
def push(self,elem):
self.data.append(elem)
def pop(self):
try:
popped_item = self.data.pop()
return popped_item
except IndexError:
print('Stack Underflow')
def peek(self):
try:
print(self.data[len(self.data)-1])
except IndexError:
print('No elements in stack')
def size(self):
return len(self.data)
my_stack = stack()
my_stack.push('1')
my_stack.push('2')
my_stack.push('3')
print("data:", my_stack.data, "size:", my_stack.size())data: ['1','2','3'] size: 3class node:
def __init__(self,val):
self.val = val
self.next = None
class linkedListStack:
def __init__(self):
self.head = None
def push(self,val):
if (self.head == None):
self.head = node(val)
else:
new_node = node(val)
new_node.next = self.head
self.head = new_node
def pop(self):
if (self.head == None):
print('Stack underflow')
else:
popped_val = self.head.val
self.head = self.head.next
return popped_val
def peek(self):
if (self.head==None):
print(None)
else:
print(self.head.val)
def display_stack(self):
dummy = self.head
while(dummy):
print(dummy.val,end=" <- ")
dummy = dummy.next
lls = linkedListStack()
lls.push(1)
lls.push(2)
lls.push(3)
lls.push(4)
lls.pop()
lls.peek()
lls.display_stack()3
3 <- 2 <- 1 <-36