Stack in Python
A stack is a linear data structure that stores items in a Last-In/First-Out (LIFO) or
First-In/Last-Out (FILO) manner. In stack, a new element is added at one end and an
element is removed from that end only. The insert and delete operations are often
called push and pop.
The functions associated with stack are:
empty() – Returns whether the stack is empty – Time Complexity: O(1)
size() – Returns the size of the stack – Time Complexity: O(1)
top() / peek() – Returns a reference to the topmost element of the stack – Time
Complexity: O(1)
push(a) – Inserts the element ‘a’ at the top of the stack – Time Complexity: O(1)
pop() – Deletes the topmost element of the stack – Time Complexity: O(1)
Implementation:
There are various ways from which a stack can be implemented in Python. This article
covers the implementation of a stack using data structures and modules from the
Python library.
Stack in Python can be implemented using the following ways:
list
[Link]
[Link]
Implementation using list:
Python's built-in data structure list can be used as a stack. Instead of push(), append()
is used to add elements to the top of the stack while pop() removes the element in LIFO
order.
Unfortunately, the list has a few shortcomings. The biggest issue 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.
# Python program to
# demonstrate stack implementation
# using list
stack = []
# append() function to push
# element in the stack
[Link]('a')
[Link]('b')
[Link]('c')
print('Initial stack')
print(stack)
# pop() function to pop
# element from stack in
# LIFO order
print('\nElements popped from stack:')
print([Link]())
print([Link]())
print([Link]())
print('\nStack after elements are popped:')
print(stack)
# uncommenting print([Link]())
# will cause an IndexError
# as the stack is now empty
Output
Initial stack
['a', 'b', 'c']
Elements popped from stack:
c
b
a
Stack after elements are popped:
[]
Implementation using [Link]:
Python stack can be implemented using the deque class from the collections module.
Deque is preferred over the list in the cases where we need quicker append and pop
operations from both the ends of the container, as deque provides an O(1) time
complexity for append and pop operations as compared to list which provides O(n) time
complexity.
The same methods on deque as seen in the list are used, append() and pop().
# Python program to
# demonstrate stack implementation
# using [Link]
from collections import deque
stack = deque()
# append() function to push
# element in the stack
[Link]('a')
[Link]('b')
[Link]('c')
print('Initial stack:')
print(stack)
# pop() function to pop
# element from stack in
# LIFO order
print('\nElements popped from stack:')
print([Link]())
print([Link]())
print([Link]())
print('\nStack after elements are popped:')
print(stack)
# uncommenting print([Link]())
# will cause an IndexError
# as the stack is now empty
Output
Initial stack:
deque(['a', 'b', 'c'])
Elements popped from stack:
c
b
a
Stack after elements are popped:
deque([])
Advantages of Stack:
Stacks are simple data structures with a well-defined set of operations, which makes
them easy to understand and use.
Stacks are efficient for adding and removing elements, as these operations have a
time complexity of O(1).
In order to reverse the order of elements we use the stack data structure.
Stacks can be used to implement undo/redo functions in applications.
Drawbacks of Stack:
Restriction of size in Stack is a drawback and if they are full, you cannot add any
more elements to the stack.
Stacks do not provide fast access to elements other than the top element.
Stacks do not support efficient searching, as you have to pop elements one by one
until you find the element you are looking for.