Bootcamp
Search…
A.5.4: Queues

# Learning Objectives

By the end of this lesson, you should:
• be familiar with queue functionality time and space complexity
• understand the difference between LIFO and FIFO
• understand the python queue class example

# Introduction

Queues are similar to stacks except instead of removing elements from the end of a list, we can only remove elements from the front of a list. Instead of push and pop operations, queues have "enqueue" and "dequeue" operations respectively. Enqueue adds an element to the back of a queue, and dequeue removes an element from the front of a queue. Queues are FIFO- First In First Out.

### Big-O of Queues

If we think of a list or, even worse, a stack, operations that affect the beginning of the data would run in at least O(n). Remember that in an array, removing something from the front is O(n). We can think of a queue as a doubly linked list so that taking things off the front or the back is always O(1).

1. 1.
This video is a concise introduction for the motivation and usage of queues.
2. 2.
This video is a more detailed introduction to queues and how to use them in Python.
3. 3.
Read pages 109-110 in the Cracking the Coding Interview PDF.

# Queue Class

Notice we Python's built-in `deque` data structure because it supports more efficient popping (dequeuing) of the left-most element than Python Lists.
# We use the built-in Python deque data structure for queues.
# Deque is implemented using linked lists and more efficient
# than Python lists for popping the left-most element.
from collections import deque
class Queue:
'''
Define a Queue class that supports the methods
1) .enqueue(element): Add element to back of queue
2) .dequeue(): Return element from front of queue
3) .size(): Return number of elements in queue
'''
# self is a reference to the instance that was just created
def __init__(self):
self.data = deque()
# Return optional representation of class in string format
def __repr__(self):
return str(self.data)
def enqueue(self, element):
print(f"{element} joins the queue")
self.data.append(element)
def dequeue(self):
element = self.data.popleft()
print(f"{element} leaves the queue")
return element
def size(self):
print(f"Queue contains {len(self.data)} elements")
return len(self.data)

From here.
class Node:
def __init__(self, data):
self.data = data
self.next = None
# A class to represent a queue
# The queue, front stores the front node
# of LL and rear stores the last node of LL
class Queue:
def __init__(self):
self.front = self.rear = None
def isEmpty(self):
return self.front == None
# Method to add an item to the queue
def EnQueue(self, item):
temp = Node(item)
if self.rear == None:
self.front = self.rear = temp
return
self.rear.next = temp
self.rear = temp
# Method to remove an item from queue
def DeQueue(self):
if self.isEmpty():
return
temp = self.front
self.front = temp.next
if(self.front == None):
self.rear = None
# Driver Code
if __name__== '__main__':
q = Queue()
q.EnQueue(10)
q.EnQueue(20)
q.DeQueue()
q.DeQueue()
q.EnQueue(30)
q.EnQueue(40)
q.EnQueue(50)
q.DeQueue()
print("Queue Front " + str(q.front.data))
print("Queue Rear " + str(q.rear.data))

# Exercises

Please use Python's `deque` data structure to represent queues.
Please fork starter code Repls and attempt solutions there. Feel free to compare with reference solutions after attempting each problem. Have fun!

## Comfortable

1. 1.
1. 1.
Hint: This may be solved more efficiently without queues, but see how we can implement it with queues first.