A queue is a collection of items whereby its operations work in a FIFO - First In First Out manner. The two primary operations associated with them are enqueue and dequeue.

I'm sure all of us have been in queues before-- perhaps at billing counters, shopping centers, or cafes. The first person in the line is usually serviced first, then the second, third, and so forth.

We have this concept in computer science as well. Take the example of a printer. Suppose we have a shared printer, and several jobs are to be printed at once. The printer maintains a printing "queue" internally, and prints the jobs in sequence based on which came first.

Another instance where queues are extensively used is in the operating system of our machines. An OS maintains several queues such as a job queue, a ready queue, and a device queue for each of the processes. If you're interested, refer to this link to know more about them.

I hope we've got a solid high-level understanding about what queues are. Let's go ahead and understand how they work!

How do queues work?

Consider a pipe, perhaps a metal one in your bathroom or elsewhere in the house. Naturally, it has two open ends. Imagine that we have some elements in the pipe, and we're trying to get them out. There will be one end through which we have inserted the elements, and there's another end from which we're getting them out. As seen in the figure below, this is precisely how the queue data structure is shaped.

Unlike the stack data structure that we primarily think of with one "open end", the queue has two open ends: the front and rear. They have different purposes-- with the rear being the point of insertion and the front being that of removal. However, internally, the front and rear are treated as pointers. We'll learn more about them in the subsequent sections programmatically.

Note that the element that got inside first is the initial one to be serviced, and removed from the queue. Hence the name: First In First Out (FIFO).

Queue operations and Implementation of queues

Similar to how a stack has push and pop operations, a queue also has two pairwise operations:

1. Enqueue: To add elements
2. Dequeue: To remove elements.

Let's move on and cover each.

Click here to check out our lesson on the stack data structure!

1. Enqueue

The enqueue operation, as said earlier, adds elements to your queue from the rear end. Initially, when the queue is empty, both our front (sometimes called head) and rear (sometimes called tail) pointers are NULL.

Now, let's add an element-- say, 'a' to the queue. Both our front and rear now point to 'a'.

Let's add another element to our queue-- 'b'. Now, our front pointer remains the same, whereas the rear pointer points to 'b'. We'll add another item 'c' and you'll see that that element is also added at the rear end. Note that, a must somehow point to be internally, and b must point to c.

2. Dequeue

To dequeue means to remove or delete elements from the queue. This happens from the front end of the queue. A particular element is removed from a queue after it is done being processed or serviced. We cannot dequeue an empty queue, and we require at least one element to be present in the queue when we want to dequeue. The following figure explains the dequeuing of our previous queue.

Implementation

Let's use python for our implementation. In python, queues can be implemented using three different modules from the python library.

• list (using a list or array is generalizable to most languages)
• collections.deque (language-specific)
• queue.Queue (language-specific)

Using the list class can be a costly affair since it involves shifting of elements for every addition or deletion. This requires O(n) time. But, with the round-robin technique, even with lists, we can achieve the time complexity of O(1). We have shown the implementation below.

Instead, we can also use the 'deque' class, which is a shorthand for 'Double-ended queue' and requires O(1) time, which is much more efficient.

So first-- we can quickly implement a queue using a list or array in most languages! This is intuitive given that they're both linear data structures, and we just need to enforce some constraints on data flow:

1. To enqueue an item in the queue, we can use the list function append.
2. To dequeue an item from the queue, we can use the list function pop(0).
3. If we want the "top-most" (or last element to be processed) item in the queue, we can get the last index of the list using the [-1] index operator.

This is by far the easiest approach, but not necessarily the most performant.

1List<Integer> queue = new ArrayList<Integer>();
2queue.add(1);
3queue.add(2);
4queue.add(3);
5
6System.out.println("Initial queue state: ");
7System.out.println(queue);
8
9System.out.println("Elements dequeued from queue");
10System.out.println(queue.remove(0));
11System.out.println(queue.remove(0));
12System.out.println(queue.remove(0));
13
14
15System.out.println("Queue after removing elements");
16System.out.println(queue);

Note that in C++, I used the standard queue container, which doesn't allow for direct access to its elements. The initial printout of the queue state is achieved by copying the queue to a temporary one and iterating through it. In the Go version, I used slices, which provide direct access to the underlying array, making it easier to print the entire queue.

To make this more efficient with lists, we can create a fixed-sized list and use it with two pointers and modular operations. It will yield a queue with O(1) access and deletion time.

1private static List<Integer> queue = new ArrayList<Integer>(10); // A List with size 10
2
3public static void Enqueue(int value) {
4    queue.add(value);
5}
6
7public static void Dequeue() {
8    queue.remove(0);
9}
10
11public static Boolean IsEmpty() {
12    return queue.size() == 0;
13}
14
15public static int Peek() {
16    return queue.get(0);
17}
18
19public static int Length() {
20    return queue.size();
21}
22
23public static Boolean IsFull() {
24    return queue.size() == 10;
25}

Conclusion

In this article, we began right from the basics of queues then learned the queue operations later scaled to two different approaches in implementing queues using python. We saw how the FIFO approach works in queues and how using collections is effective in terms of time complexity. I recommend you to go through the resources linked in-line with the article for further reading on queues.

One Pager Cheat Sheet

• A queue is a collection of items whereby its operations are arranged in a FIFO (First In First Out) format and involve two main operations: enqueue and dequeue.
• The queue is a data structure with two open ends, the rear for adding elements and the front for removing them, which follows the First In First Out (FIFO) principle.
• Queues work on the First In First Out (FIFO) principle of enqueuing and dequeuing elements.
• A Queue has two main operations - Enqueue to add elements and Dequeue to remove elements.
• The enqueue operation adds elements to the rear end of the queue, and updates the front and rear pointer accordingly.
• To dequeue an element from a queue, it is removed from the front end, if it is present, and at least one element must be in the queue for it to be possible.
• Dequeuing an element from the queue does not affect the front pointer, which remains the same, pointing at the first element added, while the rear pointer increases with new elements.
• We can implement queues using a list, collections.deque, or queue.Queue in python, with the list involving costly O(n) time complexity but with the use of the round-robin technique also requiring O(1) time, or using collections.deque or queue.Queue requiring O(1) time complexity.
• The complexity of implementing a queue with a list class in any programming language is O(n) due to the time needed to shift all items on each addition or deletion.
• We can quickly enqueue and dequeue items in a queue using most languages by either using a list or array, or with more efficient time complexity by implementing a fixed-sized list with two pointers.
• The Linked List implementation of Queues is similar to the Linked List implementation of Stacks we used previously.
• The python library provides the queue class from the Queue module to enable users to implement simple queues and check for the empty and full conditions using the empty() and full() functions respectively.
• We can implement a queue using the deque class from the collections module to append() and popleft() elements from the queue.
• The deque class from the collections module can be used to popleft() the first element and reduce the size of the queue in Python.
• The FIFO approach and using collections are effective approaches for implementing queues in python.