The end of the season sale is right around the corner, and all my favorite brands are running flat 50 % off. Time to rush to the mall. So let’s talk about everyone’s second favorite shopping past-time: waiting in line.

Oh yes, standing in the cashier queue. (And thinking about age-old data structure queue too)

Before we discuss the nitty-gritty of data structure queue, let’s talk about something extremely crucial.

What is an Abstract Data Type (ADT)?

At the beginning of the series, we’ve defined data structures as a way of storing and organizing data in an efficient way.

Whenever we study or talk about data structures, it can be done in two ways:

• Mathematical & logical models/ Abstract Data Types(ADT)
• Implementations of Data Structures.

When dealing with mathematical models, we usually look at the abstract view of them. Just a high-level view what all features, operations can be performed by them.

Let’s take a small example of television and try to gauge abstract view of it.

Of many things, high-level abstract view of TV includes below mentioned things:

• It’s an electrical device which can be turned on and off
• It receives signal for programs and displays visuals on the screen
• We can hear the voices(audio) and see moving pictures(video) on the screen

As long as the television is showing proper video and audio of requested channel, we’re never concerned with what integrated circuit unit it is using, chips or which companies are making them.

Similarly, when we deal with data structures, we look at the abstract view, more specifically at abstract data type, what operations they can perform.

So a Queue, Linked List or Stack is an Abstract Data Type (ADT). If we have a queue, we have a first in, first out data structure that we can enqueue and dequeue. (If you don’t quite understand this terminology now, its okay. I’ve explained them in detail in later part of the article)

That’s what we expect a queue to be able to do. But the actual implementation of that queue is abstracted away. It’s not that it is as Secretive as U.S. Government Operations, it’s just, we shouldn’t have to care.

Unlike when we talk about our beloved arrays, we do need to think about things like contiguous memory. However, we are not really interested in that when it’s working with this queue. How a queue is actually implemented is not that important. A queue could be and often is implemented behind the scenes using a dynamic array or a linked list.

How Queue Works:

Back to our shopping example, think of the line of customers waiting to pay their bills at the cashier. In case of multiple people waiting for billing, we often form a queue. Now, the first person in the queue pays his bill and next person takes his place. One gets taken from the front, the others shuffle up to the front of the queue and the process continues.

This is how the queue works in real life. And exactly how it works in our world of data structures too.

Let’s say I emailed the team different document and asked them to take a print and join the conference room. And we’ve only one printer. How will the printer do its job?

You guessed it right.

As the printer can only deal with one thing at a time, it has a built-in queue. You queue up multiple jobs for printing, and it will take those jobs in the order that they were submitted. First in will be first out.

Terminology For Working With Queues:

We usually draw queues horizontally. Here’s a queue of characters with 3 elements:

Like we discussed above, the main property of a queue is the customers form a line and new ones are added at the end(read: rear) and come off of the front of the queue.

Fundamental Set Of Operations:

Listed below are the fundamental set of operations we will need for an abstract data type of queue Q:

• Enter (or Insert) / Q.enqueue(e): Add element e to the back of queue Q.
• Delete (or Remove) / Q.dequeue( ): Remove and return the element from queue Q.

The queue ADT also includes the following supporting methods:

• Q.first(): Return a reference to the element at the front of queue Q, without removing it; an error occurs if the queue is empty.
• Q.is_empty( ): Return True if queue Q does not contain any elements.
• len(Q): Return the number of elements in queue Q;

Order produced by a Queue:

Queues are useful because they produce a certain order in which the contents of the queue are used. Let’s see what order that is by looking at a queue of characters. Now, what would a particular sequence of Enqueue and Dequeue do to this queue:

Now, queue.enqueue(‘d’).

Character ‘d’ is added at the end of the queue.

Now, queue.dequeue() Character ‘a’ is removed from the front of the queue.

You’ll notice that the queue enforces a certain order to the use of its contents. The ordering of the queue is First Thing In is the First thing Out (FIFO).

Implementing a Queue:

Like we discussed above, the idea of a queue as an abstract data type is that we do not care about the actual implementations of this data structure behind the scenes.

It could be implemented as a dynamic array or as a linked list or anything else, we shouldn’t have to worry. All we should be able to do is to add an item to the end(read: rear)of the queue and remove an item from the front of the queue.

Arrays:

Our powerful beast, array, can be used to implement queues. But, fixed size of the array can get problematic as we really don’t know know how big our queue will get. Sure, we can use a dynamic array, but copying contents of our array and allocating more space and memory can lead to efficiency issues.

Linked List:

Things get extremely simple in the linked list. Since memory in the linked list gets dynamically allocated, there’s no need to know about queue size ahead of time.

Enqueuing and Dequeuing methods on the linked list work in constant time or O(1) time complexity as there are pointer references to head and tail node in the linked list. So, no matter what is the size of the queue, the time taken to add or remove an element remains the same, or constant.

Well, someone may ask, what if I want to remove an item from the middle of the queue?

Honestly, if this is the scenario, then you should be looking at different data structure and not queue.

Queues — Language Support:

Different languages use several different words for the idea of removing and adding to the queue. The key behavior remains constant. In C#, it has a straightforward class with two methods. Enqueue to add an object to the end of the queue and Dequeue, to remove and return the object at the beginning

However, Java is bit intimidating. Java has several specialized queue classes. These multiple classes are mainly for different multi-threading and concurrency situations. Although for a simple queue behavior, the LinkedList class that we’ve already seen in the series actually supports queue behavior which makes it act like a queue. In Java, we use the words add and remove when working with queues.

Now, over to Python, it sure has a queue class. This class supports methods like put and get for the idea of removing or adding to the queue. And it is the same case with Ruby. Both Python and Ruby queue class is intended for synchronizing communication across threads. If we want a standard queue behavior which is not targeted at the multithreading.

What is a Priority Queue?

Some programming languages offer a version of a queue with a twist. We call it a priority queue.

Now, back to our shopping cashier line, imagine if the store had a rule if a customer has the store membership card, there is no need to get in the line. They can directly come forward and pay their bill. So, here the customer with the membership card gets higher priority than a normal customer. Or think of Amazon Prime customers. Though all our orders go in the same processing queue, one with Amazon Prime subscription gets the product delivered much faster in a day or so.

Back to our programming world, priority queue allows us to insert elements in the queue with a priority. This priority could be as simple as a number, a number so powerful which can give power to the elements to move to the front of the queue.

Multiple Items With Same Priority:

It may be possible that we may add multiple elements that have the same priority. In this case, the elements will queue up as normal as first in, first out order. If we add another element with much higher priority then it will go ahead of them in the queue and it will be removed from the queue first. Elements will lower priority will queue up as normal behind them.

Deque:

(Pronounced as the deck)

A deque is a specialized kind of queue, it’s a double-ended queue. Think of deque as having a stack and queue data structure at the same time.

Here, we have a collection of the item to which we can add new items. Now, traditional queue allowed us to add only at the back(read: rear), but deque gives us the power to add at the front and well as the back. Similarly, we can remove either from the front or from the rear.

The only restriction is we cannot remove from anywhere else in the collection.

Confusing Terms: Deque vs Dequeue

Dequeue(a verb), is an operation, a method which we can use to queue and deque an element from the queue. In above language support from queue section, we can see C# language has a similar method.

Deque(a noun) is a specialized kind of queue.

Deque — Language Support:

Sure, Priority queues and deques are certainly not things someone will need in a day to day coding, but it's useful to know they're available should you need them. And in many cases, like we saw above, they are made available as optimized and efficient data structures already present in the language.

Applications of Queue Data Structure:

Queues are used to solve a problem or a  situation where you want to efficiently maintain a First-in-first-out(FIFO) order on some entities. These situations arise literally in every type of software development.

Website Server Request:

Imagine you have a website which serves files to thousands of users. Let's say we can handle only 100 requests at one go. So, a fair policy would be first-come-first-serve: serve 100 at a time in order of arrival.

Operating Systems:

Now, imagine in a multitasking operating system, its impossible for CPU cannot run all jobs at once. So jobs must be batched up and then scheduled according to some policy. Again, you guessed it right. Queues are the best option for CPU scheduling and Disk Scheduling.enqueued so that the earlier a job is submitted the earlier it will be printed.

Asynchronously data transfer:

This situation arises when data is not necessarily received at the same rent it was sent out. Examples include IO Buffers, pipes, file IO, etc. If you're a front-end web developer, you might've worked with a famous library called jQuery. The jQuery API uses queues to allow a series of functions to be asynchronously executed on elements in the DOM.

Other Data Structures Like Trees & Graph:

Breadth First Searches(BTS) uses queues. Queues also have applications in graph theory. Trees make use of a queue to perform a breadth-first traversal of a tree.