Al-Mustaqbal University
College of Healthcare and Medical Techniques
Intelligent Medical System Department
ك ـ ـ ـ ـل ـيــة ال ـ ـتـقـنـيـ ـ ـ ــات الـص ـحـيـة وال ـط ـبـي ــة
ق ـس ـ ـ ـ ـ ـم االنـ ـظ ـ ـم ـ ـة ال ـ ـطـبـيـة الـ ـذك ـ ـ ـيـ ـة
Intelligent Medical Systems Department
Lecture: (2)
Stack in Python
Subject: Data Structure Lab.
Class: Second
Lecturer: Asst. Prof. Mehdi Ebady Manaa
Asst. Lec. Sajjad Ibrahim Ismael
Data Structure Lab – Second Stage 2022-2023 |Page1
Al-Mustaqbal University
College of Healthcare and Medical Techniques
Intelligent Medical System Department
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.
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,
Data Structure Lab – Second Stage 2022-2023 |Page2
Al-Mustaqbal University
College of Healthcare and Medical Techniques
Intelligent Medical System Department
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:
[]
Data Structure Lab – Second Stage 2022-2023 |Page3
Al-Mustaqbal University
College of Healthcare and Medical Techniques
Intelligent Medical System Department
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
Data Structure Lab – Second Stage 2022-2023 |Page4
Al-Mustaqbal University
College of Healthcare and Medical Techniques
Intelligent Medical System Department
b
a
Stack after elements are popped:
deque([])
Implementation using queue module
Queue module also has a LIFO Queue, which is basically a Stack. Data is inserted into
Queue using the put() function and get() takes data out from the Queue.
There are various functions available in this module:
• maxsize – Number of items allowed in the queue.
• empty() – Return True if the queue is empty, False otherwise.
• full() – Return True if there are maxsize items in the queue. If the queue was
initialized with maxsize=0 (the default), then full() never returns True.
• get() – Remove and return an item from the queue. If the queue is empty,
wait until an item is available.
• get_nowait() – Return an item if one is immediately available, else raise
QueueEmpty.
• put(item) – Put an item into the queue. If the queue is full, wait until a free
slot is available before adding the item.
• put_nowait(item) – Put an item into the queue without blocking. If no free
slot is immediately available, raise QueueFull.
• qsize() – Return the number of items in the queue.
# Python program to demonstrate stack implementation using queue module
from queue import LifoQueue
# Initializing a stack
stack = LifoQueue(maxsize=3)
# qsize() show the number of elements in the stack
print([Link]())
# put() function to push element in the stack
[Link]('a')
[Link]('b')
[Link]('c')
Data Structure Lab – Second Stage 2022-2023 |Page5
Al-Mustaqbal University
College of Healthcare and Medical Techniques
Intelligent Medical System Department
print("Full: ", [Link]())
print("Size: ", [Link]())
# get() function to pop element from stack in LIFO order
print('\nElements popped from the stack')
print([Link]())
print([Link]())
print([Link]())
print("\nEmpty: ", [Link]())
Output
0
Full: True
Size: 3
Elements popped from the stack
c
b
a
Empty: True
Data Structure Lab – Second Stage 2022-2023 |Page6