queue.asc

Queue

A queue is a linear data structure where the data flows in a First-In-First-Out (FIFO) manner.

Figure 1. Queue data structure is like a line of people: the First-in, is the First-out

A queue is like a line of people at the bank; the person who arrived first is the first to go out.

Similar to the stack, we only have two operations (insert and remove). In a Queue, we add elements to the back of the list and remove it from the front.

We could use an array or a linked list to implement a Queue. However, it is recommended only to use a linked list. Why? An array has a linear runtime O(n) to remove an element from the start, while a linked list has constant time O(1).

Queue’s constructor

link:../../../src/data-structures/queues/queue.js[role=include]
  // ... methods go here ...
}

We initialize the Queue creating a linked list. Now, let’s add the enqueue and dequeue methods.

Insertion

For inserting elements into a queue, also know as enqueue, we add items to the back of the list using addLast:

Queue’s enqueue

link:../../../src/data-structures/queues/queue.js[role=include]

As discussed, this operation has a constant runtime.

Deletion

For removing elements from a queue, also known as dequeue, we remove elements from the front of the list using removeFirst:

Queue’s dequeue

link:../../../src/data-structures/queues/queue.js[role=include]

As discussed, this operation has a constant runtime.

Implementation usage

We can use our Queue class as follows:

Queue usage example

link:../../../src/data-structures/queues/queue.js[role=include]

You can see that the items are dequeued in the same order they were added, FIFO (first-in, first-out).

Queue Complexity

As an experiment, we can see in the following table that if we had implemented the Queue using an array, its enqueue time would be O(n) instead of O(1). Check it out:

Table 1. Time/Space complexity for queue operations

Data Structure	Searching By		Inserting at the			Deleting from			Space
	Index/Key	Value	beginning	middle	end	beginning	middle	end
Queue (w/array)	-	-	-	-	O(1)	O(n)	-	-	O(n)
Queue (w/list)	-	-	-	-	O(1)	O(1)	-	-	O(n)

Practice Questions

Recent Counter

QU-1) Design a class that counts the most recent requests within a time window.

Example:

const counter = new RecentCounter(10); // The time window is 10 ms.
counter.request(1000); // 1 (first request, it always counts)
counter.request(3000); // 1 (last requests was 2000 ms ago, > 10ms, so doesn't count)
counter.request(3100); // 1 (last requests was 100 ms ago, > 10ms, so doesn't count)
counter.request(3105); // 2 (last requests was 5 ms ago, <= 10ms, so it counts)

Common in interviews at: FAANG, Bloomberg, Yandex

link:../../interview-questions/recent-counter.js[role=include]
  // write you code here
}

Solution: [queue-q-recent-counter]

Design Snake Game

QU-2) Design the move function for the snake game. The move function returns an integer representing the current score. If the snake goes out of the given height and width or hit itself, the game is over and return -1.

Example:

const snakeGame = new SnakeGame(4, 2, [[1, 2], [0, 1]]);
expect(snakeGame.move('R')).toEqual(0); //  0
expect(snakeGame.move('D')).toEqual(0); //  0
expect(snakeGame.move('R')).toEqual(1); //  1 (ate food1)
expect(snakeGame.move('U')).toEqual(1); //  1
expect(snakeGame.move('L')).toEqual(2); //  2 (ate food2)
expect(snakeGame.move('U')).toEqual(-1); // -1 (hit wall)

Common in interviews at: Amazon, Bloomberg, Apple

link:../../interview-questions/design-snake-game.js[role=include]

Solution: [queue-q-design-snake-game]