Lecture_Notes/imperfect_notes/pragy/Queues.md

Queues

• preserves order - FIFO
• queue of people in front of a ticker place

Operations:

stack: push and pop, peek

queue:

• enqueue / pushfront
• dequeue / popfront / removefront
• front
  • can't be done efficiently with just enqueue and dequeue
• note: dequeue != deque. DEQue stands for Double Ended Queue

---

Binary Numbers

Generate all binary numbers upto d digits.

• Keep 2 queues
• print 0
• Start with [1]
• pop and print
• append both 0 and 1 to it, and append to queue
• how to append to number? \displaystyle x = 10x + 0, 10x + 1

0
1
10 11
11 100 101
100 101 110 111
...

K-ary numbers

Given N Print first N positive numbers, whose digits are either 1, 2, 3

output: 1 2 3 11 12 13 21 22 23 31 ...

---

Some Tree:

1          2           3
11 12 13  21 22 23   31 32 33

• BFS: level order traversal: Queue
• DFS: stack

---

Implementations

Queue using Array

• front pointer
• read pointer
• enqueue: insert after rear. increment rear
• dequeue: return front. increment front
• issue: wasted space
  • empty space, but overflow
  • can be fixed by using a circular queue

Queue using Stacks

• enqueue: push O(1)
• dequeue: pop all into auxillary. pop and return top of auxillary. push all back again O(n)

What is we want dequeue to be fast, but enqueue can be slow?

• enqueue: pop all into auxillary stack. Push x. Pop and push all into original
• dequeue: pop

Stack using Queue

• push: enqueue O(1)
• pop: dequeue all into auxillary queue. Make sure you don't dequeue last element. Copy back values O(n)

Similarly, complexities can be reversed here too

---

Circular Queue using Array:

1 2 3 4 _ _
dequeue 3 times
enqueue 5, 6, 7

Failure, even though empty place is available

• Draw it circularly
• use mod with size to keep track of front and rear

def __init__(N):
    N
    front = rear = -1

def enqueue(x): 
    if (rear + 1) % N == front:
        raise Overflow
    elif front == -1:
        front, rear = 0, 0
        queue[rear] = x 
    else:
        rear = (rear + 1) % N
        queue[rear] = x

def dequeue(self):
    if front == -1:
        raise Underflow
    elif front == rear:  
        x = queue[front] 
        front, rear = -1, -1
        return x
    else:
        x = queue[front] 
        front = (front + 1) % N
        return x

---

Doubly Ended Queue

• insert_front
• insert_last
• delete_front
• delete_last

Standard implementations in all languages (usually circular and array) Just google and use.

• use array implementation vs linked list implementation
• array
  • space efficient
  • cache - locality of reference
  • can't increase size easily
  • vector
    • amortized O(1) if double
• linked list
  • can increase size easily
  • space inefficient
  • easier to distribute over multiple machines

---

Window Max

Given A[n] Given k Find max element for every k size window

Naive

Keep window of size k. Calculate max every time.
O(nk)

Optimized

Given

9 1 3 2 8 6 3 ...

window of size 6

• The 8 doesn't allow windows after 9 to have other maxes. So max can't be 1, 3, 2

• So we need to maintain the useful (decreasing) elements

• Read array from left to write and maintain the decreasing elements. So we need push_front

• But when some element in the window becomes useless, pop it from the left. So we need remove_last

• So we can use deque

N = 9, k = 3
10   1   2   9   7   6   5   11   3
\------------/

• first element of the useful elements is the max.
• pop from last if the element cant be part of next window. So, store indexes

O(n)

Variation

output max + min for every window of size k