Queue
As 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 the queue is any queue of consumers for a resource where the consumer that came first is served first.
Operations associated with queue are:
- Enqueue: Adds an item to the queue. If the queue is full, then it is said to be an Overflow condition – Time Complexity: O(1)
- Dequeue: Removes an item from the queue. The items are popped in the same order in which they are pushed. If the queue is empty, then it is said to be an Underflow condition – Time Complexity: O(1)
- Front: Get the front item from queue – Time Complexity: O(1)
- Rear: Get the last item from queue – Time Complexity: O(1)
Python queue Implementation
Queue in Python can be implemented in the following ways:
- list
- collections.deque
- queue.Queue
Implementation using list
Instead of enqueue() and dequeue(), append() and pop() function is used.
Python3
# Initializing a queuequeue = []# Adding elements to the queuequeue.append('g')queue.append('f')queue.append('g')print("Initial queue")print(queue)# Removing elements from the queueprint("\nElements dequeued from queue")print(queue.pop(0))print(queue.pop(0))print(queue.pop(0))print("\nQueue after removing elements")print(queue)# Uncommenting print(queue.pop(0))# will raise and IndexError# as the queue is now empty |
Initial queue ['g', 'f', 'g'] Elements dequeued from queue g f g Queue after removing elements []
Implementation using collections.deque
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.
Python3
from collections import deque# Initializing a queueq = deque()# Adding elements to a queueq.append('g')q.append('f')q.append('g')print("Initial queue")print(q)# Removing elements from a queueprint("\nElements dequeued from the queue")print(q.popleft())print(q.popleft())print(q.popleft())print("\nQueue after removing elements")print(q)# Uncommenting q.popleft()# will raise an IndexError# as queue is now empty |
Initial queue deque(['g', 'f', 'g']) Elements dequeued from the queue g f g Queue after removing elements deque([])
Implementation using the queue.Queue
queue.Queue(maxsize) initializes a variable to a maximum size of maxsize. A maxsize of zero ‘0’ means an infinite queue. This Queue follows the FIFO rule.
Python3
from queue import Queue# Initializing a queueq = Queue(maxsize = 3)# qsize() give the maxsize# of the Queueprint(q.qsize())# Adding of element to queueq.put('g')q.put('f')q.put('g')# Return Boolean for Full# Queueprint("\nFull: ", q.full())# Removing element from queueprint("\nElements dequeued from the queue")print(q.get())print(q.get())print(q.get())# Return Boolean for Empty# Queueprint("\nEmpty: ", q.empty())q.put(1)print("\nEmpty: ", q.empty())print("Full: ", q.full())# This would result into Infinite# Loop as the Queue is empty.# print(q.get()) |
0 Full: True Elements dequeued from the queue g f g Empty: True Empty: False Full: False
Python Data Structures
Data Structures are a way of organizing data so that it can be accessed more efficiently depending upon the situation. Data Structures are fundamentals of any programming language around which a program is built. Python helps to learn the fundamental of these data structures in a simpler way as compared to other programming languages.
In this article, we will discuss the Data Structures in the Python Programming Language and how they are related to some specific Python Data Types. We will discuss all the in-built data structures like list tuples, dictionaries, etc. as well as some advanced data structures like trees, graphs, etc.