Queue
Created : January 30, 2021
Written in Python.
- Linear data structure
- FIFO (First-In First-Out)
- Insertion: rear
- Deletion: front
-
Example
- waiting in the queue to enter a restaurant
- Useful in streaming, BFS
Basic Operations
-
enqueue or put: Add an item at the rear.
- If the queue is full → Overflow condition
append(item)
-
dequeue or get: Remove an item from the front.
- If the queue is empty → Underflow condition
pop(0)
- front: Get the front item from queue.
- rear: Get the last item from queue.
Big-O Complexity for Queue
-
Time complexity
- Insertion/Deletion: O(1)
- Access/Search: O(n)
- Space complexity: O(n)
Implementation
# Create queue class
class Queue:
# Initialize
def __init__(self):
self.items = []
# Add an item to the end
def enqueue(self, item):
self.items.append(item)
# Remove an item from the front
def dequeue(self):
# Check if stack is not empty
if not self.isEmpty():
return self.items.pop(0)
else:
print('Stack underflow')
exit()
# Check if stack is empty
def isEmpty(self):
return len(self.items) == 0
# Return size of stack
def size(self):
return len(self.items)