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.
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:
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:
Now that you have understood how to represent a queue using an array, implement the supportive queue operations.
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++:
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++:
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++:
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++:
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++:
Menu-Driven Program for 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.
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.
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.
- 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!
