Design Circular Queue

1. Define the problem

Build a queue that lives inside a fixed block of memory of size k and never grows. It supports adding at the back, removing from the front, reading the front value and reading the back value. The idea is to keep a slot number called head for where the queue starts, plus a count of how many values are stored. The back slot is then (head + count) % k . When that sum runs off the end of the block it wraps back around to slot 0 , which is where the word circular comes from. This function takes a list of operation names and a matching list of arguments, and returns the list of results. Adding to a full queue returns false, and reading from an empty queue returns -1.

Constraints

1 ≤ k ≤ 1000
0 ≤ value ≤ 1000
At most 3000 operations in total
Every operation must run in constant time

Example

Input

k = 3, operations = ['enQueue', 'enQueue', 'enQueue', 'enQueue', 'rear', 'deQueue', 'enQueue', 'rear'], values = [[1], [2], [3], [4], [], [], [4], []]

Output[true, true, true, false, 3, true, true, 4]

Explanation The fourth add fails because the queue is full. After one removal there is room again, and the new value 4 wraps around into slot 0.

2. Know the words first

In plain terms

Circular buffer: A fixed run of slots used as if the last slot were joined to the first. Nothing ever moves; only the head slot number changes.
Head: The slot number where the front of the queue currently sits. Removing from the front just moves head one step along, wrapping to 0 after the last slot.
Modulo (%): The remainder after dividing. Using % k turns any slot number into a number between 0 and k - 1, which is what makes the wrap around happen automatically.
Count: How many values are stored right now. It tells you whether the queue is empty (0) or full (k), which head alone cannot.

3. Visualize the solution

One row of cells is the fixed buffer of k = 3 slots; slot numbers never move, the head does

slot 0—

slot 1—

slot 2—

Statusinit

Three empty slots. head is 0 and the count is 0.

What happens in this step

size = 3, head = 0, count = 0
buffer = [empty, empty, empty]

The buffer is allocated once, up front, and is never resized.
An empty queue and a full queue both leave head at some slot, so the count is what tells them apart.

Step 1 of 8

Steps to visualize

The three cells are the whole storage. Nothing is ever shifted along.
Adding writes into slot (head + count) % 3 and then increases the count.
Removing from the front only moves head one step along and lowers the count.
A slot outside the live stretch is shown as a dash, because its old contents no longer belong to the queue.

4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

One row of cells is the fixed buffer of k = 3 slots; slot numbers never move, the head does

slot 0—

slot 1—

slot 2—

Statusinit

Three empty slots. head is 0 and the count is 0.

What happens in this step

size = 3, head = 0, count = 0
buffer = [empty, empty, empty]

The buffer is allocated once, up front, and is never resized.
An empty queue and a full queue both leave head at some slot, so the count is what tells them apart.

Step 1 of 8

5. Solution

Solution

solution.tsTypeScript

function circularQueue(k, operations, values) {
  class CircularQueue {
    constructor(size) {
      this.buffer = new Array(size).fill(null);
      this.size = size;
      this.head = 0;
      this.count = 0;
    }

    enQueue(value) {
      if (this.count === this.size) {
        return false;
      }

      this.buffer[(this.head + this.count) % this.size] = value;
      this.count++;
      return true;
    }

    deQueue() {
      if (this.count === 0) {
        return false;
      }

      this.head = (this.head + 1) % this.size;
      this.count--;
      return true;
    }

    front() {
      return this.count === 0 ? -1 : this.buffer[this.head];
    }

    rear() {
      const last = (this.head + this.count - 1) % this.size;
      return this.count === 0 ? -1 : this.buffer[last];
    }
  }

  const queue = new CircularQueue(k);
  const output = [];

  for (let i = 0; i < operations.length; i++) {
    const name = operations[i];
    const arg = values[i];

    if (name === 'enQueue') {
      output.push(queue.enQueue(arg[0]));
    } else if (name === 'deQueue') {
      output.push(queue.deQueue());
    } else if (name === 'front') {
      output.push(queue.front());
    } else {
      output.push(queue.rear());
    }
  }

  return output;
}

Time: O(1) per operation
Space: O(k)

6. Test cases

Test cases

Input	Expected	Covers
`k = 3, operations = ['enQueue', 'enQueue', 'enQueue', 'enQueue', 'rear', 'deQueue', 'enQueue', 'rear'], values = [[1], [2], [3], [4], [], [], [4], []]`	`[true, true, true, false, 3, true, true, 4]`	example from the docstring, including a full queue and a wrap around
`k = 1, operations = ['enQueue', 'front', 'deQueue', 'front'], values = [[8], [], [], []]`	`[true, 8, true, -1]`	the smallest possible buffer
`k = 2, operations = ['deQueue', 'front', 'rear'], values = [[], [], []]`	`[false, -1, -1]`	reading and removing from an empty queue, the degenerate case
`k = 2, operations = ['enQueue', 'enQueue', 'deQueue', 'enQueue', 'front', 'rear'], values = [[1], [2], [], [3], [], []]`	`[true, true, true, true, 2, 3]`	the back of the queue wraps past the end of the buffer
`k = 3, operations = ['enQueue', 'enQueue', 'front', 'rear'], values = [[5], [6], [], []]`	`[true, true, 5, 6]`	front and back differ while the buffer is only part full
`k = 2, operations = ['enQueue', 'enQueue', 'front', 'deQueue', 'front'], values = [[-1], [-2], [], [], []]`	`[true, true, -1, true, -2]`	negative values are stored and returned unchanged

Design Circular Queue