Queues - DSA Notes 📝

🎯 Learning Goals

• What are Queues and how to implement them?
• What are their time complexities?

---

🧠 Key Concepts (aka My Notes)

• FIFO - First In, First Out
  • Enqueue = Pushing at the end
  • Dequeue = Removing from the beginning
• Achieve it using LinkedList

Think of this as a line (left and right) whereas a stack is vertical (top and bottom).

Enqueue

• We are using singly linked list here.
• Need to check for cases where queue is empty and where it is not

def enqueue(self, val):
    newNode = ListNode(val)
    if self.tail:
        self.tail.next = newNode
        self.tail = self.tail.next
    else:
        self.head = self.tail = newNode

⌚ Time complexity is O(1)

Dequeue

• Let’s check if the queue is empty too and then return the value

def dequeue(self):
    # if the queue is empty
    if not self.head:
        return None

    val = self.head.val
    self.head = self.head.next
    if not self.head:
        self.tail = None
    return val

⌚ Time complexity is O(1)

There is also a ‘Deque’ data structure which allows you to enqueue and dequeue from both head and tail.

⌚ Time Complexities

Operation	Big-0
Enqueue	O(1)
Dequeue	O(1)

💪 LeetCode Problems

• 1700. Number of Students Unable to Eat Lunch (Link)
• 225. Implement Stack using Queues (Link)

Comments

[Michael Liang]

Helpful post!

[Juro Zaw]

Thanks for reading!