Skip to content
Home » Data Structure – Queue Basics

Data Structure – Queue Basics

    Queue is a linear data structure and an abstract data type which is defined using some basic data type in programming languages. A queue data structure is implemented using an array or a linked-list type in a programming language.

    There are two pointers that mark both ends of a queue.

    • Front
    • Rear

    A queue works on FIFO principle, First In, First out, any element that goes first must come out first.

    Figure 1 - Queue Data Structure
    Figure 1 – Queue Data Structure

    There are 3 operations performed on a queue

    • Enqueue – insert element at the rear of the queue.
    • Dequeue – remove elements from the front of the queue.
    • Display – display elements of queue.

    Enqueue Operation

    The enqueue operation is performed in rear end of the queue. You cannot insert into queue data structure if queue is full. When the queue has space, the enqueue operation insert an element and update the ‘rear’ pointer by incrementing it.

    For example

    The current status of a queue is given below.

    Figure 2 - Enqueue Operation on Queue
    Figure 2 – Enqueue Operation on Queue

    Q [1] = 44 and front = 1, Q [3] = 66 and rear = 4

    We will insert element 77 at the rear end of the queue, i.e., Q [4] = 77.

    new status of the queue after enqueue operation will be following.

    Figure 3 - After Enqueue Operation on Queue
    Figure 3 – After Enqueue Operation on Queue

    Dequeue Operation

    Dequeue operation removes an element from the front of the queue. But the queue must not be empty for dequeue operation to work. An element from the front is removed and ‘front’ pointer is updated.

    For example

    Consider the status of a queue given below

    Figure 4 - Dequeue Operation on Queue
    Figure 4 – Dequeue Operation on Queue

    Q [1] = 34 and front = 1

    You decided to delete Q [1], after deletion front = 1 + 1 = 2

    The current queue is shown in following diagram,

    Figure 5 - After Dequeue Operation on Queue
    Figure 5 – After Dequeue Operation on Queue

    Display Operation

    This is a simple operation where we traverse through the entire queue and display the list of elements. This function is the same for both array and linked-list implementation of a queue data structure.

    Types of Queues

    There are different types of queues data structure about which we will learn in future lessons. The list of queues is given below.

    • Circular Queue – where there is not end to the queue and elements are added or deleted in circular motion.
    • Priority Queue – elements of queue are in a specific order.
    • Double-Ended Queue – queue elements can be deleted or inserted from both ends.

    Queue Empty and Queue full Scenario

    Before inserting or deleting from queue we must check for two conditions

    • Is the queue empty?
    • Is the queue full?

    Let’s see each scenario in more detail.

    Queue Empty Scenario

    When queue is initiated both front = rear = 1, but after that when front==rear then it means that the queue is empty and we cannot delete from the queue because that will be an underflow.

    For example

    Consider an array based empty queue, where front = rear = 1.

    Figure 6 - Queue is initialized with front = rear = 1
    Figure 6 – Queue is initialized with front = rear = 1

    We inserted 55

    Q [1] = 55, rear = 1 + 1 = 2, front = 1

    This is shown in the following diagram.

    Figure 7 - Inserted 55 at the rear
    Figure 7 – Inserted 55 at the rear

    We inserted another element 66, now the queue is

    Q [2] = 66, rear = 2 + 1 = 3, front = 1

    Figure 8 - Inserted 66 at the rear
    Figure 8 – Inserted 66 at the rear

    Now, let’s start deleting all the elements. Delete the first element 55. Then the queue status is as follows.

    Rear = 3, front = 1 + 1 = 2 and Q [2] = 66

    The element Q [1] = 55 is deleted.

    Figure 9 - Deleted 55 at the front of the queue
    Figure 9 – Deleted 55 at the front of the queue

    Next, we delete the element Q [2] = 66. The status of the queue after deletion is shown below.

    Figure 10 - Deleted 66 at the front of the queue
    Figure 10 – Deleted 66 at the front of the queue

    Now, front = 2 + 1 = 3, rear = 3 and since,

    Front == rear

    The queue is empty.

    Queue Full Scenario

    To insert into a queue, you need to check if the queue is full, so when the front == rear + 1, then the queue is full. Any attempt to insert a new element will result in queue overflow.

    For example,

    Current status of a queue is as follows

    Figure 11 - Queue status at the beginning
    Figure 11 – Queue status at the beginning

    In the diagram above,

    Q [1] = 44 and front = 1. Also Q [4] = 77 and rear = 5

    Now we want to insert a new element 88 at Q [5].

    The new status of the queue will be

    Q [1] = 44 and front = 1, Q [5] = 88 and rear + 1 = 5 + 1 = 6

    This is shown in the queue data structure diagram below.

    Figure 12 - Queue status at the after inserting 88
    Figure 12 – Queue status at the after inserting 88

    Now finally, you will insert at Q [6] = 99. The status of the queue becomes

    Q [1] = 44 and front = 1, Q [6] = 99 and rear + 1 = 6 + 1 = 7.

    Figure 12 - Queue status at the after inserting 88
    Figure 13 – Queue status at the after inserting 99

    The rear value is greater than queue length. Then

    rear + 1 = 7 mod 6 = 1

    But,

    front = rear + 1 = 1

    Then the queue is full and we cannot insert more elements.

    References

    A.A.Puntambekar. 2009. Data Structures And Algorithms. Technical Publications.

    E.Balaguruswamy. 2013. Data Structures Using C. McGraw Hill Education.

    Thomas H. Cormen, Charles E. Leiserson, Ronald Rivest, Clifford Stein. 2009. Introduction to Algorithms. MIT Press.