Stack in Python

A stack is a linear data structure that follows the Last-In/First-Out (LIFO) principle, also known as First-In/Last-Out (FILO). This means that the last element added is the first one to be removed. In a stack, both insertion and deletion happen at the same end, which is called the top of the stack.

Python does not have a built-in stack type, but stacks can be implemented in different ways using different data structures, let's look at some of the implementations:

1. Using a List

• Python lists provide built-in methods that make them suitable for stack operations.
• The append () method adds an element to the end of the list.
• The pop () method removes and returns the last element from the list.
• These operations allow a list to directly support stack-like behavior.

stack = [] # append() function to push element in the stack stack.append('a') stack.append('b') stack.append('c') print('Initial stack') print(stack) # pop() function to pop element from stack in LIFO order print('\nElements popped from stack:') print(stack.pop()) print(stack.pop()) print(stack.pop()) print('\nStack after elements are popped:') print(stack) # uncommenting print(stack.pop()) will cause an IndexError as the stack is now empty 

Initial stack ['a', 'b', 'c'] Elements popped from stack: c b a Stack after elements are popped: [] 

Lists may slow down when they grow very large due to memory reallocation.

2. Using collections.deque

• Python’s collections module provides a deque (double-ended queue) for efficient insertions and deletions.
• The append () method adds an element to the right end of the deque.
• The pop () method removes and returns the element from the right end.
• Since deque is optimized for fast appends and pops, it is often preferred over lists for stack implementation.

Example:

from collections import deque stack = deque() # append() function to push element in the stack stack.append('a') stack.append('b') stack.append('c') print('Initial stack:') print(stack) # pop() function to pop element from stack in LIFO order print('\nElements popped from stack:') print(stack.pop()) print(stack.pop()) print(stack.pop()) print('\nStack after elements are popped:') print(stack) # uncommenting print(stack.pop()) will cause an IndexError as the stack is now empty 

Initial stack: deque(['a', 'b', 'c']) Elements popped from stack: c b a Stack after elements are popped: deque([]) 

Stack Implementation using some other Data Structures

• Using queue
• Using Linked-List