Queue Data Structure and Implementation using Array and LinkedList | Complete Tutorial

 

👋 Welcome to Appsblee! So, definitely, you are now searching what queue and stack are. Then really what are those? So let’s first take the queue. When we get the general meaning of queue, it can be a verb or noun. As a noun, it is a line. There is a queue of people waiting for the 🚌. This is a simple queue example. Here also we can get the same concept. 

🚶‍♀️Queue is a data structure that is a linear collection of data that are added and removed according to the "First-In-First-Out" order. Generally, if you are in a queue it is also processed as first in first serve manner. If we are in a queue, the first person will go in first and he will get his job done first and go first. 

👀 Imagine that you need to perform some work, but other people are waiting in a queue to get their work done. In such a scenario, you need to wait for your turn until the people before you are done. Similarly, in a queue, if there are other elements present, you need to apply specific methods to enter and retrieve the elements.

There are mainly three basic operations in a queue: 

    1. Enqueue
    2. Dequeue
    3. Peek

The enqueue method is used to add new elements to the queue, and they will be added to the rear of the queue. That means the end of the queue. The dequeue method is used to delete the front element in the queue. Finally, the peek method is used to retrieve the element in the front without deleting it. In the queue, there is no way to add/delete, or retrieve elements from the middle. That means there is no access for the middle elements instead of the front(start) and rear(end).

The queue has two main pointers: 

    1. Front

    2. Rear

The front pointer points to the first element in the queue, and the rear pointer points to the current existing element of the queue.

Whenever the queue is empty, the front element should be null, and the rear location should be one index behind the front location. For instance, if the front is located at index 6, the rear location should be the 5th index. Because when we are adding elements only the rear move. If we add 3 new elements then the rear move to the 8th location in the Empty Queue state above.

If the Queue is full, then the rear should be at the last location of the array. The front can be anywhere. If both the front and the rear are at the last location(end of the array). Then there is only 1 element in the array and the array is full. Because the rear is at the last location.

Enqueue Operation

Dequeue Operation

Basic operations in Summary

Queue can be implemented using,

    1. Array

    2. LinkedList

When we are implementing a queue, we have to be concerned about mainly several operations.

   1.  isEmpty()

   2. isFull()

   3. Enqueue()

   4. Dequeue()

   5. Peek()

👉 Implement Queue using Array

As a first step, we have to decide the size of the queue when we are implementing the queue using an array. It can be listed as the disadvantage of implementing a queue using an array and the reason to implement a queue using LinkedList.

After the decision, we can create the array and add the elements to the array. For example, it is a queue with elements 1,2,3,4,5,6. we can implement and place the elements below. We have to create an array with a length of 6.

💡In here we should remember that the current size of an array is always can be obtained by reducing 1 to the size of the array. In this case, the length of an array is 6. Then the max size of an array is 6-1 = 5. So to store 6 elements we have to initialize an array with the length of 6. (We initialize the size as 5 here because we consider the starting index as 0). That means from the 0th index to the 5th index we can store 6 elements.

To implement the basic operation of the queue in an array we should check isEmpty() for the dequeue operation and isFull() for the enqueue operation, we have to check whether the array is empty or not. if an array is empty, we can’t get the first element of the array and remove it because there are no elements. for this isEmpty() wants to be determined. Also in the enqueue operation, we should consider about if the array is full or not because the array is a fixed-size data structure when it is full of elements we can’t add new elements to it, and for this isFull() method is needed.

Enqueue()

Before adding a new element to an array in an enqueue operation, we need to check if the array is full or not. If the array is not full, we can add the new element to the next available index location.

For example, let's say we have an array of size 5 with 3 elements already in it. If we are asked to enqueue a new element, we need to do the following:

1. Examine the existing array.

2. Increment the Rear and Add the new element.

Dequeue()

Here we should first consider whether the array is empty or not. If the array is not empty, we can do the dequeue operation.

       1. So the existing array is,

       2. We should remove the first element of the array because, as in a queue, the first element that enters the queue should be the first one to leave.

      3. So the front should be pointed to the index position of the next element in the array.

Peek()

It is important to check if the array is empty before performing a peek operation on it. If the array is empty, then no element can be retrieved. However, if the array is not empty, we can retrieve the first element of the queue without removing it using the peek operation.

💡It is important to note that the peek operation does not remove the first element, whereas the dequeue operation does.

For example, when we use the peek operation, we can retrieve the first element without deleting it. On the other hand, with the dequeue operation, we retrieve the first element and remove it.

Let’s consider the above example.

Here we get the first element without deleting it.

When implementing a queue using an array, there is a memory wastage during the dequeue operation.  So Let's consider the same example.

The space occupied by the first element is emptied, but it cannot be used again, which leads to memory wastage. To prevent this memory wastage we can implement the circular queue structure.

👉 Implement Queue using LinkedList 

Let's explore how to create a queue using LinkedList. Suppose we have a queue with three elements, namely 1, 2, and 3. We can add these elements to the linked list without worrying about its size. In contrast, when working with arrays, we need to initialize and determine their size in advance. Therefore, the queue implemented using LinkedList will look like the following.

We will now explore how to implement basic operations.

Enqueue() Operation

When we perform an enqueue operation, we must insert the item at the end of the queue.

Dequeue() Operation

We should remove the items from the beginning because we inserted the elements at the end. Therefore, the first element that we added is now at the beginning. So, when we remove items, we should remove elements from the beginning.

Peek() Operation

In this operation, we retrieve the first element instead of deleting it.

What do you think about the information provided? Did you find it useful and informative? Were you able to get the answer to the question related to your goals? Do you think the answer is in a queue or a stack? If you are curious to know more about the stack and find the correct answer to your question, don't wait any longer and read on here. Furthermore, if you have any further questions, feel free to leave a comment below. We would love to answer your queries. Let's explore another exciting topic.