Introduction to Queue Data Structure in C

Back to: Data Structures and Algorithms Tutorials

Introduction to Queue Data Structure in C Language:

In this article, I will give you an introduction to the Queue Data Structure, and we will discuss some of its applications. Then, we will discuss the abstract data type of Queue, i.e., Queue ADT.

What is Queue?

A queue is a logical data structure that operates on the FIFO principle, meaning “First In, First Out.” There are many examples of queues in our daily lives, such as people standing in a queue to avail services or submit their applications and cars waiting in line.

Even on our phone calls, if the lines are busy, we receive a message stating that we are in a queue and to please wait. Similarly, when calling customer care, we may hear a message indicating that we are in a queue and that representatives are currently busy. Thus, we encounter queues in various situations. Queues are commonly used in various applications and algorithms, making queues one of the basic data structures.

Here, we have an example of a queue where people are standing and waiting in line to avail of services or complete their tasks. A queue operates on the FIFO (First In, First Out) discipline. The queue has two ends: the front end and the rear end.

If a person wants to join a queue, they should come and stand at the end of the queue, which is the rear end. We can call this “insertion,” so insertion is done at the rear end. If a person wants to leave the queue, they will exit from the front end. We can call this “deletion,” so deletion is done from the front end. Therefore, insertion is done from one end, and deletion is done from another end. Both ends are utilized in a queue.

If you recall, in the stack, insertion and deletion are done from the same end. However, in a queue, we insert from the rear end and delete from the front end. Now, let’s take a look at the Abstract Data Type (ADT) of a Queue.

ADT (Abstract Data Type) of Queue:

Let’s look at the data.

Data:

First, we need space to store elements or objects.

• Space for storing elements.

Next, we need a front pointer to delete the elements. It may point to or before the first element in the queue, but it will be used for deletion.

• Front Pointer for deletion.

Next, we need a rear pointer to insert the elements. It may point to the last element or after the last element, but it will be used for insertion.

• Rear Pointer for insertion.

This is all about the data that will be stored in the queue. Now, let us look at the operations that we can perform on a queue.

Operations:

• enqueue(x): It is used to insert an element in the queue. Insertion will be done from the rear end.
• dequeuer(): It is used to delete an element in the queue. Deletion of an element will be done from the front end.
• isEmpty(): This function will check whether the queue is empty or not.
• isFull(): This function will check whether the queue is full or not.
• first(): this function will return the first element of the queue.
• last(): This function will return the last element of the queue.

If desired, additional functions such as display () to print all the elements of the queue and count () to return the total number of elements in the queue can be added. Therefore, you can include functions as per your requirements. This constitutes the queue’s Abstract Data Type (ADT). A queue can be implemented using either of these two physical data structures: Array or Linked List. In the upcoming articles, we will learn how to implement a queue using an array and then using a linked list.

In the next article, I will discuss how to Implement a Queue using a Single Pointer in C Language. In this article, I give a brief Introduction to a Queue Data Structure. I hope you enjoy this article on Queue Data Structure.