Queue data structure in C++ and operations

What is a data structure?

So what is a data structure? A data structure is a way of organizing, formatting and storing data so that you may access it as efficiently as possible and modify it if need be.

On earth we're dealing with "stacks", "queues" etc, maybe on other planets they have a different concept of what a data structure should be and it's goal. For us it's a way of dealing with data.

What then is a queue data structure?

Definition

The queue data structure like "stacks" is a Linear Abstract Data Type. If you'd like to read more about what exactly an Abstract Data Type is please read this article, where I've broken it down.

Queue data structures consist of ordered elements of the same data type. They follow the "FIFO" principle which stands for First In First Out. This means that addition and deletion operations occur on the first element that is added to the queue.

The most basic thing about queues is..

A queue is a list/collection of elements with the constraint that:

Insertion and deletion must happen at 2 opposite ends. Insertion happens at 1 end of the queue called "END/REAR" and deletion of an element happens at the other end known as "FRONT/HEAD" of the queue.

How to Queue?

Queues can be implemented in 2 ways:

1. Via arrays
2. Via linked lists

Mostly we don't write our own implementation of a data structure, we use in-built implementations provided by a programming language.

Difference between a stack and queue

In a stack we follow the *LIFO principle (Last In First Out) and remove the most recently added item.

Whereas,in a queue, we follow the FIFO principle (First In First Out) and remove the item which was added first

Queue operations

These operations are functions that perform a specific task.

1. Insertion or Enqueue: The process to add an element into a queue i.e. push() an element into the queue at the rear end
2. Deletion or Dequeue: The process of removing an element from a queue i.e. pop() from the front end of the queue. Typically the dequeue operation returns an element that it deletes.
3. isEmpty(): Query whether the queue is empty or not.
4. front() or peek(): Query the element at the front of the queue

Some examples

Enqueue/Insertion/push()

1. Initially the head and rear end of the queue are the same i.e. the front and end will be at the same index/position in the queue.

1. Now let's add an element into the array implementation of a queue, i.e. enqueue/push/insert an element into index 0 of an array. With only 1 element in the queue, the end now points towards the next empty position in the array where an element can be inserted or pushed into.

1. Similarly, if we add the 2nd element into the queue, the end/tail moves ahead and now points to the next position where the 3rd element can be inserted

Dequeue/Deletion/pop()

There are 2 ways to dequeue or pop() an element from an array.

1st method:

In this method, the 1st element is removed from the front or head, and then the remaining elements are moved one position forward to the head.

2nd method:

In the 2nd method, the element is removed from the front/head of the queue as required. And then the head/front moves and points to what is now the 1st element in the queue. Because of moving the head one position forward, the length of the queue reduces by 1.