Objectives

By the end of this chapter you should be able to:

• Compare and contrast stacks and queues
• Describe what a queue is and implement essential queue operations
• Understand common use cases for queues

Queue

An example of a queue data structure is a line in a grocery store. The first person in line is the first person served. Each subsequent person is served in priority order. If you want to be served, you must add yourself to the end of the line.

In general, a queue is considered a First In, First Out data structure, or a FIFO data structure. It maintains an order and the first element added or enqueued to the queue is the first that will be returned or dequeued

Common queue operations:

• enqueue - Add an item to the back of the line. In the image below 2 is enqueue'ed into the queue and added to the back of the queue.

• dequeue - Return the first element in the queue. In the example below, -30 was the first element, so it is the element that is returned when dequeue is invoked.

• length - How many elements are in the queue.

Real World Examples of Queues

Prioritization - One of the most common use cases for a queue is when priority is important. Let's imagine your web site has thousands of requests a second. Since you cannot service all requests at the same time, you might implement a first-come-first serve policy by time of arrival. To manage the priority and ordering of requests, a Queue would be the most ideal data structure to use. Similarly in a multitasking operating system, the CPU cannot run all jobs at once, so jobs must be batched up and then scheduled according to some policy. Again, a queue might be a suitable option in this case. Finally, queues are commonly used with scheduling jobs for printers, where the first job to be enqueued is the first to be print.

Searching Algorithms / Traversal - for certain kinds of algorithms (especially ones we will examine in a later section on Binary Search Trees), remembering information in a certain order can easily be achieved using a queue. Queues can also be used with maze algorithms to keep track of options that have not yet been explored.

Job/Process Scheduling - Very commonly when background jobs are being run, there is a queue that manages the order in which these background jobs are coming in and how they are being processed. Very commonly, in memory databases like Redis are used to manage these processes.

Naive Queue Implementation

function Queue() {
    this.queue = [];
}

Queue.prototype.enqueue = function(val) {
    this.queue.push(val);
}

Stack.prototype.dequeue = function() {
    return this.queue.shift();
}

Stack.prototype.length = function() {
    return this.queue.length;
}

The queue implementation above enforces the FIFO property of a queue, but again it is not the most efficient implementation. Both enqueue and dequeue are O(n) operations. To make both operations constant time, you could implement the queue with a doubly linked list.