Tutorial Playlist

Data Structure Tutorial

Overview

Arrays in Data Structures: A Guide With Examples

Lesson - 1

All You Need to Know About Two-Dimensional Arrays

Lesson - 2

All You Need to Know About a Linked List in a Data Structure

Lesson - 3

The Complete Guide to Implement a Singly Linked List

Lesson - 4

The Ultimate Guide to Implement a Doubly Linked List

Lesson - 5

The Fundamentals for Understanding Circular Linked List

Lesson - 6

The Ultimate Guide to Stacks and Queues Data Structures

Lesson - 7

Implementing Stacks in Data Structures

Lesson - 8

Your One-Stop Solution for Stack Implementation Using Array

Lesson - 9

Your One-Stop Solution for Queue Implementation Using Array

Lesson - 10

Your One-Stop Solution for Stack Implementation Using Linked-List

Lesson - 11

Your One-Stop Solution to Learn Depth-First Search(DFS) Algorithm From Scratch

Lesson - 12

All You Need to Know About Linear Search Algorithm

Lesson - 13

All You Need to Know About Breadth-First Search Algorithm

Lesson - 14

A One-Stop Solution for Using Binary Search Trees in Data Structure

Lesson - 15

The Best Tutorial to Understand Trees in Data Structure

Lesson - 16

A Complete Guide to Implement Binary Tree in Data Structure

Lesson - 17

A Holistic Look at Using AVL Trees in Data Structures

Lesson - 18

All You Need to Know About Tree Traversal in Data Structure

Lesson - 19

The Best Guide You’ll Ever Need to Understand B-Tree in Data Structure

Lesson - 20

The Best Guide You'll Ever Need to Understand Spanning Tree in Data Structure

Lesson - 21

Your One-Stop Solution for Graphs in Data Structures

Lesson - 22
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 tutorial, you will implement a queue data structure with 1-D arrays in C++.

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.

Full Stack Web Developer Course

To become an expert in MEAN StackView Course
Full Stack Web Developer Course

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.

Add Another Star to Your Performance Evaluation

Learn from industry experts for FREEStart Learning
Add Another Star to Your Performance Evaluation

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.