Stacks and Queues
Implementation
Stack and Recursion
- There aree several situvations when recursive methods are quite handy
- For example: DFS, traversing a binary search tree, looking foir an item in a linkedlist
- All the recursive algorithms can be transformed into a simple methhod with stacks
Important: If we use recursion, the OS will use stacks anyways.
what does it all have to do with stacks? The recursive functions calls are pushed onto the stack until we bump into the base case
- We keep backtrcking: we know the base case so we know the subsolutions.
- If there are too many function calls to be pushed onto the stack: The stack may get full, no more space left.
- Called
Stack Overflow
#collapse-hide
class Stack:
def __init__(self):
self.stack = []
def isEmpty(self):
return self.stack == []
def push(self, element):
self.stack.append(element)
def pop(self):
if not self.isEmpty():
return self.stack.pop()
else:
return -1
def peek(self):
if not self.isEmpty():
return self.stack[-1]
else:
return -1
def display(self):
for i in range(len(self.stack)):
print(self.stack[i])
stack = Stack()
stack.push(1)
stack.pop()
stack.push(10)
stack.push(20)
stack.peek()
stack.display()
#collapse-hide
import sys
class Stack:
def __init__(self):
self.stack=[None] * 100
self.top=-1
def isFull(self):
if self.top==100:
return True
return False
def isEmpty(self):
if self.top==-1:
return True
return False
def push(self,data):
if self.isFull():
print("stack overflow")
return
self.top+=1
self.stack[self.top]=data
def pop(self):
if self.isEmpty():
print("Stack Underflow")
sys.exit(0)
d=self.stack[self.top]
self.top-=1
return d
def peek(self):
if self.isEmpty():
print("Stack Underflow")
sys.exit(0)
d=self.stack[self.top]
return d
def display(self):
if self.isEmpty():
print("Stack Underflow")
sys.exit(0)
self.temp=self.top
while self.temp>=0:
print(self.stack[self.temp])
self.temp-=1
if __name__=='__main__':
s=Stack()
while(1):
print("1.Push\n");
print("2.Pop\n");
print("3.Display the top element\n");
print("4.Display all stack elements\n");
print("5.Quit\n");
print("Enter your choice : ");
choice=int(input())
if choice==1:
value=int(input())
s.push(value)
elif choice==2:
d=s.pop()
print("poped value",d)
elif choice==3:
print("top of the element",s.peek())
elif choice==4:
s.display()
else:
sys.exit(0)