Kodeclik Blog
How to implement a Stack in Python
A stack is a last-in-first-out (LIFO) data structure. For instance, if you stack up disks on a peg they will come out in the reverse order in which you put them in. The peg that entered the stack first will be the last one to come out. Likewise the peg that entered the stack last will be the first one to come out. A stack is thus a LIFO data structure unlike a queue which is a FIFO data structure.
Another example of a stack is a stack of plates. Once you stack them you do not try to take the first plate you pushed into the stack. Instead you take the plate from the top (i.e., the last one to be placed onto the stack).
Stacks can be implemented in Python in many ways. Below we highlight each of these methods.
Method 1: Use a list data structure
The easiest way to implement a stack is to use a list data structure. You can use the append method to add elements (“push”) to the stack. You can use the pop method to remove elements from the stack.
Here is some code to create a stack and push three elements (fruits of various types) onto it:
mystack = []
mystack.append('Apples')
mystack.append('Bananas')
mystack.append('Grapes')We can print our stack using:
print(mystack)And we will get:
['Apples', 'Bananas', 'Grapes']We can then pop elements from the stack using the following series of commands:
print(mystack.pop())
print(mystack.pop())
print(mystack.pop())This will output:
Grapes
Bananas
ApplesNote that the elements are coming in the reverse order in which you inserted them because a stack is a LIFO data structure.
If we attempt to pop again:
print(mystack.pop())we will get the error:
File "main.py", line 10, in <module>
print(mystack.pop())
IndexError: pop from empty listhighlighting that the stack is now empty.
Method 2: Use a collections.deque data structure
The second approach to initialize and implement a stack in Python is to use the collections module and specifically the data structure called “deque” (double ended queue). A deque has more capabilities than what we need in a stack but it is optimized for fast insertions and removals. Here is the code to initialize a stack using the collections.deque data structure and pushing elements one by one.
The advantage of the collections.deque data structure is that adding elements and removing elements uses the same methods as before, i.e., append() and pop() respectively. Here is some code:
from collections import deque
mystack = deque([])
mystack.append('Apples')
mystack.append('Bananas')
mystack.append('Grapes')
print(mystack)The mystack data structure is initially set to be an empty deque. Then three elements are added one by one so that when we print it we get the output:
deque(['Apples', 'Bananas', 'Grapes'])Let us try popping one element:
print("Popping one element")
print(mystack.pop())This prints:
Popping one element
GrapesIf we pop two more elements:
print(mystack.pop())
print(mystack.pop())we will get:
Bananas
ApplesAnd finally, if we try to pop and print again:
Traceback (most recent call last):
File "main.py", line 14, in <module>
print(mystack.pop())
IndexError: pop from an empty dequewe will get the same error as before.
Method 3: Use a queue.LIFOQueue data structure
The third approach to initialize a queue is to use the queue module and the LIFOQueue data structure within it (the name is a misnomer because it is not a queue but the LIFO should remind you that this is a stack). Here is the corresponding code and methods to accomplish the same example as above:
from queue import LifoQueue
mystack = LifoQueue(maxsize=5)
mystack.put('Apples')
mystack.put('Bananas')
mystack.put('Grapes')
print(mystack)In the above program, the parameter 5 refers to the maximum size of the stack. Each put() command adds an element. The output is (your specific output might vary):
<queue.LifoQueue object at 0x7f9be0142580>This output is not very informative. To confirm the contents of the stack (i.e., LIFOQueue) have been added as intended, we can use the get() method which pops the element from the stack and also returns it so you can print it:
from queue import LifoQueue
mystack = LifoQueue(maxsize=5)
mystack.put('Apples')
mystack.put('Bananas')
mystack.put('Grapes')
print(mystack)
print(mystack.get())
print(mystack.get())
print(mystack.get())The output of the above program will be:
<queue.LifoQueue object at 0x7f753af04580>
Grapes
Bananas
ApplesNote that the elements are being popped (and printed) in the reverse order in which they were pushed (put) into the stack.
Following these three get() method operations, the stack will now be empty.
There you have it - three different methods to setup a stack in Python. Which method is your favorite?
Interested in more things Python? Checkout our post on Python queues. Also see our blogpost on Python's enumerate() capability. Also if you like Python+math content, see our blogpost on Magic Squares. Finally, master the Python print function!
Want to learn Python with us? Sign up for 1:1 or small group classes.
