Last Updated on December 14, 2022 by Prepbytes
In data structures, stack and queue are part of linear data structure.
Stack
Stack follows the principle of LIFO (Last in First out) i.e. element which is inserted at last will be removed first. The operation for insertion of elements in stack is known as Push operation and the operation for deletion of element in stack is known as Pop operation.
Queue
Queue follows the principle of FIFO (First in First out) i.e. element which is inserted first will be removed first. The operation for insertion of elements is known as enqueue operation and the operation for deletion of elements is known as dequeue operation.
There are specified classes of stack and queue in python. Given below are the different ways to implement stack and queue in python:
1. Using list
Stack works on the principle of LIFO (Last in First out). In Python, there are some built-in functions that make the implementation of a stack using a list quite short and simple. For performing the push operation i.e. for inserting the element in the stack there is an append() function in the list that works the same according to the push function and for performing the pop operation i.e. for removing the element from the stack there is a pop() function that works the same according to the pop function in the queue. These functions work efficiently for performing operations in the end position.
Code Implementation:
stack = [2, 4, 6] stack.append(5) stack.append(3) print(*stack) print(stack.pop()) print(*stack) print(stack.pop()) print(*stack)
Queue works on the principle of FIFO (First in First out). In Python, there are some built-in functions that make the implementation of a queue using a list simple and easy. For inserting the element in the queue, the append() function will be used that will insert a new element at the last position in the queue. And for removing the element from the queue, the pop(0) function will be used that will remove the element from the first position in the queue.
Code Implementation:
stack = [2, 4, 6] stack.append(5) stack.append(3) print(*stack) print(stack.pop(0)) print(*stack) print(stack.pop(0)) print(*stack)
2. Using Deque
Using deque for implementing the stack will give the same time complexity as using a list will give. There are append() and pop() functions that will insert or remove the element from the stack. The time complexity for these functions will be O(1).
Code Implementation:
from collections import deque queue = deque([2, 4, 6]) queue.append(5) queue.append(3) print(*queue) print(queue.pop()) print(*queue) print(queue.pop()) print(*queue)
But for implementing the queue, the above using list implementing queue is not the efficient method. In the queue, the pop function removes the first element from the queue that takes O(N) time complexity which is quite slow for queue implementation. This happened due to the list working fast for the operations on the rear or end side but slow for the front end because for the front end, all the elements have to be shifted by one position.
It is preferred to use deque instead of list for the implementation of the queue in python as deque is specially designed to have the fast append and pop operations from the both front and back end.
Code Implementation:
from collections import deque queue = deque([2, 4, 6]) queue.append(5) queue.append(3) print(*queue) print(queue.popleft()) print(*queue) print(queue.popleft()) print(*queue)
This article tried to discuss the Implementation of Stack and Queues in python. Hope this blog helps you understand the concept. To practice more problems feel free to check MYCODE | Competitive Programming at Prepbytes.