Stack :

Stack is a Linear Data structure that store and removes it's element in Last-In-First-Out(LIFO) or First-In-Last-Out(FILO).

Insertation and Deletion of elements can be perform from One end only.

Insertation and Deletion of elements in stack often called as push and pop.

Functions :

• empty() : Returns whether the stack is empty.
• push(element): Inserts the element ‘element’ at the top of the stack.
• pop(): Deletes the topmost element of the stack.
• size(): Returns the size of the stack.
• top(): Returns a reference to the topmost element of the stack.

Implementation of Stack : Stack can be implemented in python using the following ways :

• list
• collections.deque
• queue.LifoQueue

Implementation of Stack using list :
• list[] can be used as a stack in python.
• We can use append() method for push operation. append() is used to add elements to the top of the list and pop() removes the element from the top of the list.
• len() can be use to get the size of the Stack and stack[len(stack)-1] can gives the topmost element of the Stack.
• The biggest issue of implementation of Stack using list is that it can run into speed issues as it grows. The items in the list are stored next to each other in memory, if the stack grows bigger than the block of memory that currently holds it, then Python needs to do some memory allocations. This can lead to some append() calls taking much longer than other ones.

	
#  Stack using list :
	
	stack=[]
	
	stack.append('a')
	stack.append('b')
	stack.append('c')
	
	print("Origional stack : {}".format(stack))
	
	popedItem = stack.pop()
	
	print("pop({})".format(popedItem))
	print("After pop() stack changed to : {}".format(stack))
	
	# Output : 
	Origional stack : ['a', 'b', 'c']
	pop(c)
	After pop() stack changed to : ['a', 'b'])
	


Implementation of Stack using deque :
• Stack can also be implemented using collections.deque module.
• We can use append() method for push operation. append() is used to add elements to the top of the list and pop() removes the element from the top of the list.
• len() can be use to get the size of the Stack and stack[len(stack)-1] can gives the topmost element of the Stack.
• Deque is preferred over the list in the cases where we need quicker push and pop operations.

	
# Stack using collections.deque() :
	
	from collections import deque
	
	stack = deque()
	
	stack.append('a')
	stack.append('b')
	stack.append('c')

	print("Origional stack : {}".format(stack))

	popedItem = stack.pop()

	print("pop({})".format(popedItem))
	print("After pop() stack changed to : {}".format(stack))
	
	# Output : 
	Origional stack : deque(['a', 'b', 'c'])
	pop(c)
	After pop() stack changed to : deque(['a', 'b'])

	

We can also create our own Stack Class using list or deque(). Below code block shows the Implementation of Stack using collections.deque().

	
#  Implementation of Stack using collections.deque() :

	from collections import deque

	class Stack:
		def __init__(self):
			self.stack = deque()
		
		def __repr__(self):
			cur = deque()
			for ele in self.stack:
				cur.append(ele)
			return str(cur)
			
		def size(self) -> int:
			return len(self.stack)

		def push(self, val):
			self.stack.append(val)
			
		def pop(self):
			return self.stack.pop()
			
		def top(self):
			return self.stack[len(self.stack)-1]
			
		def isempty(self) -> bool:
			if self.stack == None:
				return True
			else:
				return False

	

	
#  Creating Instance of Stack  :
	
	my_stack1 = Stack()
	print(type(my_stack1))		# Output : < class '__main__.Stack' >
	
	# Perform different Operations on Stack : 
	my_stack1.push('a')
	my_stack1.push('b')
	my_stack1.push('c')

	print("Origional stack : {}".format(my_stack1))		

	popedItem = my_stack1.pop()

	print("pop({})".format(popedItem))		
	print("After pop() stack changed to : {}".format(my_stack1))		
	print(my_stack1.size())		
	print(my_stack1.top())
	print(my_stack1.isempty())
	
	# Output : 
	< class '__main__.Stack' >
	Origional stack : deque(['a', 'b', 'c'])
	pop(c)
	After pop() stack changed to : deque(['a', 'b'])
	2
	b
	False