3.8 KiB
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 everyk
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