Queue, Deque | Notion

Intro

Queue is an ADT that represents an ordered collection of items where the addition of new items happens at one end and the removal of existing items occurs at the other end

FIFO (first-in first-out)

Screenshot 2026-01-10 at 23.58.45.png

Screenshot 2022-10-23 at 11.20.34.png

Dequeue is a Queue that has two ends, a front, and a rear, and the items remain positioned in the collection

unrestrictive nature of adding and removing items:
- new items can be added at either the front or the rear
- likewise, existing items can be removed from either end
does not require any particular ordering principle, it is up to you to make consistent use of the addition and removal operations
dequeue = stack + queue

Circular Queue is a Queue in which the last position is connected back to the first position to make a circle

Screenshot 2022-10-23 at 11.21.42.png

Screenshot 2022-07-21 at 13.44.31.png

Screenshot 2026-01-10 at 20.35.21.png

Usage

scheduling systems, networking and handling congestion, multiplayer gaming
request queuing is the procedure of handling requests before they even enter an application to be processed

Screenshot 2022-10-23 at 11.23.04.png

Screenshot 2022-10-23 at 11.22.52.png

Comparison

Advantages

Disadvantages

Problems

[ ] Implement Stack using Queues
[ ] Implement Queue using Stacks
[ ] Design Circular Queue
[ ] Design Hit Counter (LeetCode Premium)
[ ] Sliding Window Maximum [hard]

Corner Cases

empty queue
only 1/2 elements

Implementation

Queue can be implemented using a concrete data structure like a Linked List or a Dynamic Array, or using Python’s queue

Screenshot 2022-07-21 at 13.27.57.png

Time Complexity
Operations	Worst case
	Stack as Dynamic Array	Stack as Linked List
	Front is index 0	Front is head
push()/enqueue()	`O(1)`	`O(1)`
pop()/dequeue()	`O(n)`	`O(1)`
front()	`O(1)`	`O(1)`
back()	`O(1)`	`O(n)`
isEmpty()	`O(1)`	`O(1)`
	Front is index n-1	Front is tail
push()/enqueue()	`O(n)`	`O(1)`
pop()/dequeue()	`O(1)`	`O(n)`
front()	`O(1)`	`O(1)`
back()	`O(1)`	`O(n)`
isEmpty()	`O(1)`	`O(1)`

Space Complexity
Implementation	Worst case
Stack as Dynamic Array	`O(n)`
Stack as Linked List	`O(n)`

n is the number of elements in the queue

Algorithms

Patterns

Code

class DynamicArrayQueue(object):
    def __init__(self):
        self.items = []

    def isEmpty(self):
        return self.items == []

    def push(self, item):
        self.items.append(item)

    def pop(self):
        return self.items.pop()

    def top(self):
        if self.isEmpty():
            return None
        return self.items[len(self.items) - 1]

    def size(self):
        return len(self.items)

class Node:   
    def __init__(self,data):
        self.data = data
        self.next = None

class LinkedQueue:
    def __init__(self):
        self.head = None
      
    def isEmpty(self):
        if self.head == None:
            return True
        return False
	
	def push(self, data):
        if self.head == None:
            self.head = Node(data)
       
        newnode = Node(data)
        newnode.next = self.head
        self.head = newnode

	def pop(self): 
        if self.isEmpty():
            return None
              
        poppednode = self.head
        self.head = self.head.next
        poppednode.next = None
        return poppednode.data

	def peek(self):
        if self.isEmpty():
            return None

				return self.head.data

Resources

To Queue Or Not To Queue