Data Structures - Queues (Part 3/3)

In this last part of the series, we going to talk about Queues

  1. Linked Lists
  2. Stacks
  3. Queues

In a Queue, it is First in - First out, i.e the oldest element comes out first. And the last element is the newest element.

Adding element to the Tail is called Enqueue, and removing element from the [Head] is called Dequeue.

The term peek means look at the head element.

Deques

A Deque is a Queue that goes both ways: i.e it is a double ended Queue. You can Enqueue or Dequeue from both ends.

Priority Queue

In Priority Queue, a numerical priority is assigned to each element that are inserted into the Queues.

When an element is removed (dequeue), it will be the element with the highest priority. If the elements have same priority, then the oldest element is dequeued.

Quizz

Make a Queue class using a list! Hint: You can use any Python list method you’d like! Try to write each one in as few lines as possible. Make sure you pass the test cases too!

class Queue:
    def __init__(self, head=None):
        self.storage = [head]

    def enqueue(self, new_element):
        self.storage.append(new_element)

    def peek(self):
        if len(self.storage) == 0:
            return None
        else:
            return self.storage[0]

    def dequeue(self):
        if len(self.storage) != 0:
            self.storage.pop(0)
            return self.storage[0]
            
    
# Setup
q = Queue(1)
q.enqueue(2)
q.enqueue(3)

# Test peek
# Should be 1
print q.peek()

# Test dequeue
# Should be 1
print q.dequeue()

# Test enqueue
q.enqueue(4)
# Should be 2
print q.dequeue()
# Should be 3
print q.dequeue()
# Should be 4
print q.dequeue()
q.enqueue(5)
# Should be 5
print q.peek()