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 that arrived first is the first to go out as well.

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 goes here ...
}

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

Insertion

For inserting elements on 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 know 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 like follows:

Queue usage example

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

You can see that the items are dequeue 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)