Queues

Implementation:

You can implement a queue using either a linked list or an array.

Circular Array based queue:

Enqueuing:

Initialize two pointers, f (front), b (back), and a variable length (to store the length of array).

front = 0, back = 0, length = 0

         f b
         ↓ ↓
        ┌───┬───┬───┬───┬───┬───┐
Array → │   │   │   │   │   │   │
        └───┴───┴───┴───┴───┴───┘
          ⁰   ¹   ²   ³   ⁴   ⁵

To enqueue, back is incremented (back + 1) % Array.length (we use mod so that it wraps around).
Increment our length by 1,

front = 0, back = 1, length = 1

          f   b
          ↓   ↓
        ┌───┬───┬───┬───┬───┬───┐
Array → │ 3 │   │   │   │   │   │
        └───┴───┴───┴───┴───┴───┘
          ⁰   ¹   ²   ³   ⁴   ⁵

Let's add a second item:

front = 0, back = 2, length = 2

          f       b
          ↓       ↓
        ┌───┬───┬───┬───┬───┬───┐
Array → │ 3 │ 4 │   │   │   │   │
        └───┴───┴───┴───┴───┴───┘
          ⁰   ¹   ²   ³   ⁴   ⁵

Dequeuing:

Define a new result variable.
Store the value at index sub front in the result variable.

front = 0, back = 2, length = 2, result = 3

          f       b
          ↓       ↓
        ┌───┬───┬───┬───┬───┬───┐
Array → │ 3 │ 4 │   │   │   │   │
        └───┴───┴───┴───┴───┴───┘
          ⁰   ¹   ²   ³   ⁴   ⁵

Decrement our length and increment the front variable. When incrementing front, make sure to do (front + 1) % Array.length as this will allow us to wrap around back to 0, 1, ... if needed.

front = 1, back = 2, length = 1, result = 3

              f   b
              ↓   ↓
        ┌───┬───┬───┬───┬───┬───┐
Array → │ 3 │ 4 │   │   │   │   │
        └───┴───┴───┴───┴───┴───┘
          ⁰   ¹   ²   ³   ⁴   ⁵

Return the result. Notice: we don't need to clear out A[front] as we'll just overwrite it if we need the slot.

Q: Find sum of each sliding window of size 3.

Tip: queue's are great for sliding window problems

Enqueue each value until you've reached the sliding window size (3), maintain a sum as you enqueue each value, and store it in an output array.

Array → [1, 4, 3, 5, 3, 1]   Sum = 8 / Output = [8]
         ───────
            ┌───┬───┬───┐
Queue     → │ 3 │ 4 │ 1 │ →
            └───┴───┴───┘

Dequeue from the back (1) and subtract it from the sum 4 + 3 = 7:

Array → [1, 4, 3, 5, 3, 1]   Sum = 7 / Output = [8]
            ───────
            ┌───┬───┐   ┌───┐
Queue     → │ 3 │ 4 │ → │ 1 │ →
            └───┴───┘   └───┘

Enqueue the next value, and update the sum 4 + 3 + 5 = 11

Array → [1, 4, 3, 5, 3, 1]   Sum = 9 / Output = [8, 11]
            ───────
            ┌───┐   ┌───┬───┐   ┌───┐
Queue     → │ 5 │ → │ 3 │ 4 │ → │ 1 │ →
            └───┘   └───┴───┘   └───┘

Q: Implement a Queue with O(1) lookup of the maximum element in the Queue.

Initialize two linked list queues, value_queue and max_queue:

        ┌───┐
Value → │   │
        └───┘
        ┌───┐
  Max → │   │
        └───┘

For the first value, enqueue it on both queues.

        ┌───┐
Value → │ 1 │ →
        └───┘
        ┌───┐
  Max → │ 1 │ →
        └───┘

Let's say we add 4 to this queue, we can get rid of the one (since even if we dequeue, four will still be our max as items can only be removed from the front).

        ┌───┐   ┌───┐
Value → │ 4 │ → │ 1 │ →
        └───┘   └───┘
        ┌───┐
  Max → │ 4 │ →
        └───┘

Let's say we now enqueue 2.

        ┌───┐   ┌───┐   ┌───┐
Value → │ 2 │ → │ 4 │ → │ 1 │ →
        └───┘   └───┘   └───┘
        ┌───┐
  Max → │ 4 │ →
        └───┘

Since 4 is greater than 2, 4 must remain our max. But say we dequeue 1, and 4:

        ┌───┐
Value → │ 2 │ →
        └───┘
        ┌───┐
  Max → │   │ →
        └───┘

The 2 would become the new maximum. So to handle this, we need to enqueue our 2 to the max queue:

        ┌───┐   ┌───┐   ┌───┐
Value → │ 2 │ → │ 4 │ → │ 1 │ →
        └───┘   └───┘   └───┘
        ┌───┐   ┌───┐
  Max → │ 2 │ → │ 4 │ →
        └───┘   └───┘

Now let's say we enqueued 3:

        ┌───┐   ┌───┐   ┌───┐   ┌───┐
Value → │ 3 │ → │ 2 │ → │ 4 │ → │ 1 │ →
        └───┘   └───┘   └───┘   └───┘
        ┌───┐   ┌───┐
  Max → │ 2 │ → │ 4 │ →
        └───┘   └───┘

Our 2 is useless since it can never be our max, so we enqueue our 3.

        ┌───┐   ┌───┐   ┌───┐   ┌───┐
Value → │ 3 │ → │ 2 │ → │ 4 │ → │ 1 │ →
        └───┘   └───┘   └───┘   └───┘
        ┌───┐   ┌───┐
  Max → │ 2 │ → │ 4 │ →
        └───┘   └───┘

from collections import deque

valq = deque()
maxq = deque()
front, back = (0, -1)

def enqueue(n):
    valq.append(n)
    while maxq and maxq[back] < n:
        maxq.pop()
    maxq.append(n)
    
for n in [1, 4, 2, 3]:
    enqueue(n)

print(f'values: {valq}\nmax:\t{maxq}')

values: deque([1, 4, 2, 3])
max:	deque([4, 3])

Conversely, to dequeue:

Let's say we dequeue 1, and then dequeue 4:

        ┌───┐   ┌───┐
Value → │ 3 │ → │ 2 │ →
        └───┘   └───┘
        ┌───┐   ┌───┐
  Max → │ 3 │ → │ 4 │ →
        └───┘   └───┘

Our 4 will also need to be removed from our max_queue:

        ┌───┐   ┌───┐
Value → │ 3 │ → │ 2 │ →
        └───┘   └───┘
        ┌───┐
  Max → │ 3 │ →
        └───┘

So to finish our dequeue alogrithm:

from collections import deque

valq = deque([3, 2, 4, 1])
maxq = deque([3, 4])
front, back = (0, -1)

def dequeue():
    if maxq and maxq[back] == valq[back]:
        maxq.pop()
    valq.pop()

for _ in range(0, 2):
    dequeue()

print(f'values: {valq}\nmax:\t{maxq}')

values: deque([3, 2])
max:	deque([3])

This can be combined with sliding window problems, so if you wanted the top 2 within the window:

Iteration 1:

Array → [3, 1, 2, 4, 1]
         ───────
      ┌───┐ ┌───┐
Max → │ 2 │→│ 3 │
      └───┘ └───┘

Result: [[2, 3]]

iteration 2:

Array → [3, 1, 2, 4, 1]
            ───────
      ┌───┐ ┌───┐
Max → │ 2 │→│ 4 │
      └───┘ └───┘

Result: [[2, 3], [2, 4]]

iteration 3:


Array → [3, 1, 2, 4, 1]
               ───────
      ┌───┐ ┌───┐
Max → │ 2 │→│ 4 │
      └───┘ └───┘

Result: [[3, 2], [4, 2], [4, 2]]

Homework Problem 1 (Level: Hard)

Maximum of Sliding Window: Given an array A and an integer K, find the maximum element in each sliding window of size K.

For example:

A = [4, 6, 5, 2, 4, 7] and K = 3

The windows are as follows:

A = [4, 6, 5, 2, 4, 7] : Max = 6
     ───────
A = [4, 6, 5, 2, 4, 7] : Max = 6
        ───────
A = [4, 6, 5, 2, 4, 7] : Max = 5
           ───────           
A = [4, 6, 5, 2, 4, 7] : Max = 7
             ────────

Output: [6, 6, 5, 7]

Hint: You can do this in O(n) time, by using the Queue with Max we implemented above. Solution:

from collections import deque

front, back = (0, -1)
valq = deque()
maxq = deque()

def enqueue(n):
    valq.append(n)
    while maxq and maxq[back] < n:
        maxq.pop()
    maxq.append(n)
    
def slide_right(i):
    # pop the left value to make room to slide the window.
    n = valq.popleft()
    
    # if the value being removed exists in our max value queue,
    # we need to remove it.
    if maxq[back] == n:
        maxq.pop()
    elif maxq[front] == n:
        maxq.popleft()

    # add the new value with added to our window.
    enqueue(array[i])
    
    # increment i to setup for next iteration.
    i += 1
    return i

def max_sliding_window(array, window_size):
    output = []
    length = len(array)
    i = 0
    
    # populate our initial window.
    while i < window_size:
        enqueue(array[i])
        i += 1

    # add the maximum value to the output array.
    output.append(maxq[front])

    while i < (length):
        # slide our window right.
        i = slide_right(i)
        
        # record the windows max value in our output array.
        output.append(maxq[front])
    return output

array = [4, 6, 5, 2, 4, 7]
window_size = 3

results = max_sliding_window(array, window_size)
print('Maximum sliding window: ', results)

Maximum sliding window:  [6, 6, 5, 7]

nficano/queues.md