Your One-Stop Solution for Queue Implementation Using Array

It is common to use the queue data structure across all the branches of computer sciences to solve various problems related to the asynchronous transfer of data. Round-robin algorithm in operating systems interrupts handling mechanism in computer architecture. Routers and switches in networking utilize queues to maintain data in a hierarchy. So, in this C++ tutorial for beginners, you will implement a queue data structure with 1-D arrays.

How to Implement Queue Using Arrays?

The queue is a linear collection of distinct entities like an array. The fact that the queue possesses some restrictions while performing insertion and deletion is vital. In the case of a queue, it can perform both insertion and deletion only at specific ends, i.e., rear and front nodes. Whereas arrays do not follow any order for these operations. You can illustrate this dissimilarity between a queue and an array using pointers in C++. 

You can represent queues in the form of an array using pointers: front and rear. 

For example, the array shown in the diagram below consists of 11 characters having S at the front and N at the rear node.

Queue_Representation_Using_Array

The figure above shows the queue of characters forming the word “SIMPLILEARN”. And since N is the last inserted element, its position becomes the rear node. However, if you want to insert more values into the queue, the rear pointer will also increase one by one every time. After you perform an insertion operation on the queue shown in the figure above, the queue will look like below:

Insertion_in_Queue

The value of the rear pointer becomes 11, whereas the front pointer remains the same.

After deleting an element from the queue, the value of the front pointer will change from 0 to 1. The queue will look like below: 

Deletion_in_Queue

Now that you have understood how to represent a queue using an array, implement the supportive queue operations.

Here's How to Land a Top Software Developer Job

Full Stack Developer - MERN StackExplore Program
Here's How to Land a Top Software Developer Job

Execution of Supportive Queue Operations

The three supportive queue operations that check the state of a queue are isFull(), isEmpty(), and Peek(). These functions do not depend on the number of elements inside the queue or the size of the queue; that is why they take constant execution time, i.e., O(1) [time-complexity]. Here you will implement all the following supportive functions. 

isFull() Operation

This function checks if the queue is full or not. If the queue is full, then the insertion of elements is not possible in a queue. This condition is known as overflow error. You need to perform the following steps while carrying this operation:

Pseudocode:

Function isFull()

       If Rear == Maxsize -1:

          Return “Queue is Full”

       End IF                              

 End isFull()

Function in C++:

isFull_implementation

isEmpty() Operation

This function validates if the queue is empty. If both the front and rear nodes are pointing to null memory space (-1), then you can consider the queue as empty. The pseudocode for this operation is:

Pseudocode:

  Function isEmpty               

         If Rear == -1  && Front ==  -1:

            Return “Queue is Empty”

         End IF                     

  End isEmpty()

Function in C++:

isEmpty_implementation

Peek() Operation

This function helps in extracting the data element where the front is pointing without removing it from the queue. The pseudocode for Peek() function is as follows -

Pseudocode:

  Function Peek                     

          If Rear == -1  && Front ==  -1:

             Return “Queue is Empty”

          Else

             Return queue[front]

          End if

  End isFull()

Code in C++:

Peek_implementation.

This is all about supportive queue operations. Next, you will implement primary queue operations that manipulate the flow of data in a queue.

Implementation of Enqueue Operation

The process of inserting elements into the queue is known as Enqueue operation. You perform this operation at the rear node of the queue. The pseudocode for this operation is as follows:

Pseudocode:

  Function Enqueue()        

           If Rear = MAXSIZE -1:

              Return “Overflow Error”

           ElseIF (Front = -1 and Rear = -1):

              Set Front = Rear = 0

           Else   

              Set Rear = Rear + 1

           End if

  Set Queue[Rear} = NUM

  End Enqueue()

Code in C++:

Enqueue_implementation

Implementation of Dequeue Operation

The Dequeue operation is a process of removing elements from the queue. It can only delete an element when there is at least an element to delete, i.e., Rear > 0 (queue shouldn’t be empty). This function follows the steps listed below while deleting an element from the queue: 

Pseudocode:

  Function Dequeue()                    

           If Rear == -1  && Front ==  -1:

              Return “Underflow Error”                     

           Else   

              Set Rem = Queue[Front]

              Set Front = Front +1

           End IF

  End Dequeue()

Code in C++:

Queue_implementation_using_Array

Now that you are clear with the building blocks of queue operation, it’s time to dive in further and formulate a menu-driven C++ program to visualize a queue using an array data structure. You are going to use the switch statement to take input from the user and control the flow of the program. 

C%2B%2B_code-Queue_Implementation_Using_Array.

C%2B%2B_code2-Queue_Implementation_Using_Array.

C%2B%2B_code3_Queue_Implementation_Using_Array.

Queue_Impl_arr/C%2B%2B_code-Queue_Implementation.

Have a look at the results of the menu-driven program for queue implementation using an array. Here, you must insert 3 elements (12,112,45) into a queue with the help of case- 1). And later you will display them with the function display(). Shown below is the output. 

Complete_Execution-Queue_implementation_Using_Array.

Here's How to Land a Top Software Developer Job

Full Stack Developer - MERN StackExplore Program
Here's How to Land a Top Software Developer Job

Drawbacks of Queue Implementation Using Array

Although this method of creating a queue using an array is easy, some drawbacks make this method vulnerable. Here, you will explore the drawbacks of queue implementation using array one-by-one:

  • Memory Wastage: The memory space utilized by the array to store the queue elements can never be re-utilized to store new queue elements. As you can only insert the elements at the front end and the value of the front might be quite high, it can never reuse the blank space before that. 

For example, consider the array shown in the figure above. The size of the queue is 10, and the front pointer has already reached location 5, thus wasting newly created empty spaces.

Memory_wastage-Queue_implementation_using_array.

  • Deciding the array size: In this method, you have to predetermine the size of an array. And the fact that you can extend the queue at the runtime depending upon the problem makes this method unresistant, as it is almost impossible to extend an array size at runtime. 
Advance your career as a MEAN stack developer with the Full Stack Web Developer - MEAN Stack Master's Program. Enroll now!

Conclusion

In this tutorial, you learned about implementing a queue using one-dimensional arrays. An array is a simple linear data structure that can only store data elements with the same data type, whereas a queue supports data elements with multiple data types. Implementation of this queue feature is not possible with the help of 1-D arrays. Here, you also saw the development of queue operations starting with their pseudocode and ending with C++ program implementation.

If you are looking for more comprehensive learning that goes beyond C++ and covers the most in-demand programming languages and skills needed today, Simplilearn’s Skillup Software Development Course will prove to be just right for you. Explore now and get started! 

On that note, do you have any questions related to this tutorial on queue implementation using array? If you have, please place them as comments at the end of this page. Our experts will respond to them soon!

About the Author

SimplilearnSimplilearn

Simplilearn is one of the world’s leading providers of online training for Digital Marketing, Cloud Computing, Project Management, Data Science, IT, Software Development, and many other emerging technologies.

View More
  • Disclaimer
  • PMP, PMI, PMBOK, CAPM, PgMP, PfMP, ACP, PBA, RMP, SP, and OPM3 are registered marks of the Project Management Institute, Inc.