Stack and Queues in Python
Last Updated :
09 May, 2022
Prerequisites : list and Deque in Python.
Unlike C++ STL and Java Collections, Python does have specific classes/interfaces for Stack and Queue. Following are different ways to implement in Python
1) Using list
Stack works on the principle of “Last-in, first-out”. Also, the inbuilt functions in Python make the code short and simple. To add an item to the top of the list, i.e., to push an item, we use append() function and to pop out an element we use pop() function. These functions work quiet efficiently and fast in end operations.
Let’s look at an example and try to understand the working of push() and pop() function:
Example:
stack = ["Amar", "Akbar", "Anthony"]
stack.append("Ram")
stack.append("Iqbal")
print(stack)
print(stack.pop())
print(stack)
print(stack.pop())
print(stack)
|
Output:
['Amar', 'Akbar', 'Anthony', 'Ram', 'Iqbal']
Iqbal
['Amar', 'Akbar', 'Anthony', 'Ram']
Ram
['Amar', 'Akbar', 'Anthony']
Queue works on the principle of “First-in, first-out”. Below is list implementation of queue. We use pop(0) to remove the first item from a list.
queue = ["Amar", "Akbar", "Anthony"]
queue.append("Ram")
queue.append("Iqbal")
print(queue)
print(queue.pop(0))
print(queue)
print(queue.pop(0))
print(queue)
|
Output:
['Amar', 'Akbar', 'Anthony', 'Ram', 'Iqbal']
Amar
['Akbar', 'Anthony', 'Ram', 'Iqbal']
Akbar
['Anthony', 'Ram', 'Iqbal']
2) Using Deque
In case of stack, list implementation works fine and provides both append() and pop() in O(1) time. When we use deque implementation, we get same time complexity.
from collections import deque
queue = deque(["Ram", "Tarun", "Asif", "John"])
print(queue)
queue.append("Akbar")
print(queue)
queue.append("Birbal")
print(queue)
print(queue.pop())
print(queue.pop())
print(queue)
|
Output:
deque(['Ram', 'Tarun', 'Asif', 'John'])
deque(['Ram', 'Tarun', 'Asif', 'John', 'Akbar'])
deque(['Ram', 'Tarun', 'Asif', 'John', 'Akbar', 'Birbal'])
Birbal
Akbar
deque(['Ram', 'Tarun', 'Asif', 'John'])
But when it comes to queue, the above list implementation is not efficient. In queue when pop() is made from the beginning of the list which is slow. This occurs due to the properties of list, which is fast at the end operations but slow at the beginning operations, as all other elements have to be shifted one by one.
So, we prefer the use of dequeue over list, which was specially designed to have fast appends and pops from both the front and back end.
Let’s look at an example and try to understand queue using collections.deque:
from collections import deque
queue = deque(["Ram", "Tarun", "Asif", "John"])
print(queue)
queue.append("Akbar")
print(queue)
queue.append("Birbal")
print(queue)
print(queue.popleft())
print(queue.popleft())
print(queue)
|
Output:
deque(['Ram', 'Tarun', 'Asif', 'John'])
deque(['Ram', 'Tarun', 'Asif', 'John', 'Akbar'])
deque(['Ram', 'Tarun', 'Asif', 'John', 'Akbar', 'Birbal'])
Ram
Tarun
deque(['Asif', 'John', 'Akbar', 'Birbal'])
Similar Reads
Queue in Python
Like a stack, the queue is a linear data structure that stores items in a First In First Out (FIFO) manner. With a queue, the least recently added item is removed first. A good example of a queue is any queue of consumers for a resource where the consumer that came first is served first. Operations
6 min read
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 wi
8 min read
Stack and Queue in Python using queue Module
A simple python List can act as queue and stack as well. Queue mechanism is used widely and for many purposes in daily life. A queue follows FIFO rule(First In First Out) and is used in programming for sorting and for many more things. Python provides Class queue as a module which has to be generall
3 min read
Circular Queue in Python
A Circular Queue is a kind of queue that can insert elements inside it dynamically. Suppose, in a given array there is not any space left at the rear but we have space at the front in the normal queue it is not possible to insert elements at the front but in the case of a circular queue we can do th
3 min read
numpy.stack() in Python
NumPy is a famous Python library used for working with arrays. One of the important functions of this library is stack(). Important points:stack() is used for joining multiple NumPy arrays. Unlike, concatenate(), it joins arrays along a new axis. It returns a NumPy array.to join 2 arrays, they must
5 min read
Queue Implementation in Python
Queue is a linear data structure that stores items in a First In First Out (FIFO) manner. With a queue, the least recently added item is removed first. One can imagine a queue as a line of people waiting to receive something in sequential order which starts from the beginning of the line. It is an o
4 min read
Priority Queue in Python
A priority queue is like a regular queue, but each item has a priority. Instead of being served in the order they arrive, items with higher priority are served first. For example, In airlines, baggage labeled “Business†or “First Class†usually arrives before the rest. Key properties of priority que
3 min read
Python program to reverse a stack
The stack is a linear data structure which works on the LIFO concept. LIFO stands for last in first out. In the stack, the insertion and deletion are possible at one end the end is called the top of the stack. In this article, we will see how to reverse a stack using Python. Algorithm: Define some b
3 min read
Start and stop a thread in Python
The threading library can be used to execute any Python callable in its own thread. To do this, create a Thread instance and supply the callable that you wish to execute as a target as shown in the code given below - Code #1 : # Code to execute in an independent thread import time def countdown(n):
4 min read
Monotonic Stack in Python
A Monotonic Stack is a data structure used to maintain elements in a monotonically increasing or decreasing order. It's particularly useful in problems like finding the next or previous greater or smaller elements. In this article, we'll learn how to implement and use a monotonic stack in Python wit
3 min read