Operations on Different Types of Queues

---

1. Introduction

A queue is a linear data structure in which insertion and deletion take place at different ends.

The basic operations are:

• Enqueue – insertion of an element

• Dequeue – deletion of an element

• Front/Peek – accessing the front element

• Rear – accessing the last element

• isEmpty() – checking whether the queue is empty

• isFull() – checking whether the queue is full

The implementation and exact conditions for these operations vary for:

1. Simple/Linear Queue

2. Circular Queue

3. Priority Queue

---

2. Operations on a Simple / Linear Queue

A linear queue follows the FIFO (First In, First Out) principle.

For an array implementation, two variables are generally maintained:

front
rear

Initially:

front = -1;
rear = -1;

---

3. Enqueue Operation in Linear Queue

Enqueue inserts a new element at the rear of the queue.

Algorithm: ENQUEUE

Input: Element ITEM

Steps:

1. Check whether the queue is full.

2. If full, report Queue Overflow.

3. If the queue is initially empty, set front = 0.

4. Increment rear.

5. Store ITEM at queue[rear].

6. Stop.

Pseudocode

ENQUEUE(ITEM)

1. If rear == MAX - 1
       Print "Queue Overflow"
       Return

2. If front == -1
       front = 0

3. rear = rear + 1

4. queue[rear] = ITEM

5. Return

---

4. Dequeue Operation in Linear Queue

Dequeue removes an element from the front.

Algorithm: DEQUEUE

Steps:

1. Check whether the queue is empty.

2. If empty, report Queue Underflow.

3. Store queue[front] in ITEM.

4. If front == rear, reset both to -1.

5. Otherwise increment front.

6. Return the deleted element.

Pseudocode

DEQUEUE()

1. If front == -1
       Print "Queue Underflow"
       Return

2. ITEM = queue[front]

3. If front == rear
       front = -1
       rear = -1
   Else
       front = front + 1

4. Return ITEM

---

5. Front Operation

The front operation returns the first element without deleting it.

Algorithm

FRONT()

1. If front == -1
       Print "Queue is Empty"
       Return

2. Return queue[front]

---

6. Rear Operation

The rear operation returns the last element.

REAR()

1. If front == -1
       Print "Queue is Empty"
       Return

2. Return queue[rear]

---

7. C Program: Linear Queue

#include <stdio.h>

#define MAX 5

int queue[MAX];
int front = -1;
int rear = -1;

void enqueue(int value)
{
    if (rear == MAX - 1)
    {
        printf("Queue Overflow\n");
        return;
    }

    if (front == -1)
        front = 0;

    rear++;
    queue[rear] = value;

    printf("%d inserted into queue\n", value);
}

void dequeue()
{
    if (front == -1)
    {
        printf("Queue Underflow\n");
        return;
    }

    printf("%d deleted from queue\n", queue[front]);

    if (front == rear)
    {
        front = -1;
        rear = -1;
    }
    else
    {
        front++;
    }
}

void display()
{
    int i;

    if (front == -1)
    {
        printf("Queue is Empty\n");
        return;
    }

    printf("Queue elements: ");

    for (i = front; i <= rear; i++)
        printf("%d ", queue[i]);

    printf("\n");
}

int main()
{
    enqueue(10);
    enqueue(20);
    enqueue(30);

    display();

    dequeue();
    display();

    enqueue(40);
    enqueue(50);

    display();

    return 0;
}

Output concept

10 20 30
↓
20 30
↓
20 30 40 50

---

8. Limitation of Linear Queue

Suppose the queue has capacity 5:

10 20 30 40 50

After deleting three elements:

_ _ _ 40 50

Although three positions are empty, rear is already at the last position.

Therefore, a new insertion may produce overflow.

This problem is addressed by the Circular Queue.

---

9. Circular Queue

In a circular queue, the last position is logically connected to the first position.

When the rear reaches the last position, it can wrap around to position zero.

---

10. Circular Queue Conditions

For a common circular queue implementation using one unused array position:

Empty condition

front == -1

Full condition

(rear + 1) % MAX == front

Moving rear

rear = (rear + 1) % MAX;

Moving front

front = (front + 1) % MAX;

The modulo operator makes the index wrap around.

---

11. Enqueue in Circular Queue

Algorithm

ENQUEUE(ITEM)

1. If (rear + 1) % MAX == front
       Print "Queue Overflow"
       Return

2. If front == -1
       front = 0
       rear = 0
   Else
       rear = (rear + 1) % MAX

3. queue[rear] = ITEM

4. Return

---

12. Dequeue in Circular Queue

Algorithm

DEQUEUE()

1. If front == -1
       Print "Queue Underflow"
       Return

2. ITEM = queue[front]

3. If front == rear
       front = -1
       rear = -1
   Else
       front = (front + 1) % MAX

4. Return ITEM

---

13. C Program: Circular Queue

#include <stdio.h>

#define MAX 5

int queue[MAX];
int front = -1;
int rear = -1;

void enqueue(int value)
{
    if ((rear + 1) % MAX == front)
    {
        printf("Circular Queue Overflow\n");
        return;
    }

    if (front == -1)
    {
        front = 0;
        rear = 0;
    }
    else
    {
        rear = (rear + 1) % MAX;
    }

    queue[rear] = value;

    printf("%d inserted\n", value);
}

void dequeue()
{
    int value;

    if (front == -1)
    {
        printf("Circular Queue Underflow\n");
        return;
    }

    value = queue[front];
    printf("%d deleted\n", value);

    if (front == rear)
    {
        front = -1;
        rear = -1;
    }
    else
    {
        front = (front + 1) % MAX;
    }
}

void display()
{
    int i;

    if (front == -1)
    {
        printf("Queue is Empty\n");
        return;
    }

    printf("Queue elements: ");

    i = front;

    while (1)
    {
        printf("%d ", queue[i]);

        if (i == rear)
            break;

        i = (i + 1) % MAX;
    }

    printf("\n");
}

int main()
{
    enqueue(10);
    enqueue(20);
    enqueue(30);
    enqueue(40);

    display();

    dequeue();
    dequeue();

    display();

    enqueue(50);
    enqueue(60);

    display();

    return 0;
}

---

14. Working Example of Circular Queue

Assume:

MAX = 5

Insert:

10, 20, 30, 40

Then delete:

10, 20

The available positions can be reused.

Now insert:

50, 60

The new elements can occupy the positions that became free at the beginning of the array.

This is the main advantage of circular queue.

---

15. Complexity of Circular Queue

Operation	Time Complexity
Enqueue	O(1)
Dequeue	O(1)
Front	O(1)
Rear	O(1)
isEmpty	O(1)
isFull	O(1)
Display	O(n)

Space complexity:

$$O(n)$$

where n is the queue capacity.

---

16. Priority Queue

In a priority queue, every element has an associated priority.

Deletion is performed according to priority.

For example:

Element	Priority
A	3
B	1
C	2

If priority 1 means highest priority, then:

B → C → A

will be the service order.

---

17. Priority Queue Operations

The basic operations are:

Insert

Adds an element with a priority.

Delete

Removes the element having the highest priority.

Peek

Returns the highest-priority element without removing it.

Display

Displays the elements and their priorities.

---

18. Array Implementation of Priority Queue

A simple implementation can use a structure:

struct Item
{
    int data;
    int priority;
};

For example:

Data       Priority

100           3
200           1
300           2
400           1

If smaller priority number means higher priority, the next element selected will have priority 1.

If multiple elements have the same priority, FIFO ordering can be maintained by the implementation.

---

19. C Program: Priority Queue

The following implementation maintains elements in priority order, with smaller priority number representing higher priority.

#include <stdio.h>

#define MAX 5

struct Item
{
    int data;
    int priority;
};

struct Item pq[MAX];
int size = 0;

void insert(int data, int priority)
{
    int i;

    if (size == MAX)
    {
        printf("Priority Queue Overflow\n");
        return;
    }

    i = size - 1;

    while (i >= 0 && pq[i].priority > priority)
    {
        pq[i + 1] = pq[i];
        i--;
    }

    pq[i + 1].data = data;
    pq[i + 1].priority = priority;

    size++;

    printf("%d inserted with priority %d\n",
           data, priority);
}

void deleteHighestPriority()
{
    int i;

    if (size == 0)
    {
        printf("Priority Queue Underflow\n");
        return;
    }

    printf("%d deleted with priority %d\n",
           pq[0].data, pq[0].priority);

    for (i = 0; i < size - 1; i++)
    {
        pq[i] = pq[i + 1];
    }

    size--;
}

void peek()
{
    if (size == 0)
    {
        printf("Priority Queue is Empty\n");
        return;
    }

    printf("Highest priority element: %d\n",
           pq[0].data);
}

void display()
{
    int i;

    if (size == 0)
    {
        printf("Priority Queue is Empty\n");
        return;
    }

    printf("Data\tPriority\n");

    for (i = 0; i < size; i++)
    {
        printf("%d\t%d\n",
               pq[i].data,
               pq[i].priority);
    }
}

int main()
{
    insert(100, 3);
    insert(200, 1);
    insert(300, 2);
    insert(400, 1);

    display();

    peek();

    deleteHighestPriority();

    display();

    return 0;
}

---

20. Priority Queue Complexity

For the sorted-array implementation above:

Operation	Complexity
Insert	O(n)
Delete highest priority	O(n)
Peek	O(1)
Display	O(n)
Space	O(n)

The complexity of a priority queue depends strongly on its implementation.

For example, a binary heap can provide:

• Insert: O(log n)

• Delete highest/lowest priority: O(log n)

• Peek: O(1)

---

21. Queue Using Linked List

A linked-list queue generally maintains:

front
rear

Each node contains:

data
next

Conceptually, the queue consists of dynamically allocated nodes.

---

22. Enqueue in Linked-List Queue

The new node is inserted at the rear.

Algorithm

ENQUEUE(ITEM)

1. Create a new node.
2. Store ITEM in the node.
3. Set new node's next = NULL.
4. If queue is empty:
       front = rear = new node
5. Otherwise:
       rear->next = new node
       rear = new node
6. Return.

---

23. Dequeue in Linked-List Queue

The node is removed from the front.

Algorithm

DEQUEUE()

1. If front == NULL
       Print "Queue Underflow"
       Return

2. temp = front

3. front = front->next

4. If front == NULL
       rear = NULL

5. Delete/free temp

6. Return deleted element

---

24. C Implementation: Queue Using Linked List

#include <stdio.h>
#include <stdlib.h>

struct Node
{
    int data;
    struct Node *next;
};

struct Node *front = NULL;
struct Node *rear = NULL;

void enqueue(int value)
{
    struct Node *newNode;

    newNode = (struct Node *)malloc(sizeof(struct Node));

    if (newNode == NULL)
    {
        printf("Memory allocation failed\n");
        return;
    }

    newNode->data = value;
    newNode->next = NULL;

    if (front == NULL)
    {
        front = rear = newNode;
    }
    else
    {
        rear->next = newNode;
        rear = newNode;
    }

    printf("%d inserted\n", value);
}

void dequeue()
{
    struct Node *temp;

    if (front == NULL)
    {
        printf("Queue Underflow\n");
        return;
    }

    temp = front;

    printf("%d deleted\n", front->data);

    front = front->next;

    if (front == NULL)
        rear = NULL;

    free(temp);
}

void display()
{
    struct Node *temp;

    if (front == NULL)
    {
        printf("Queue is Empty\n");
        return;
    }

    temp = front;

    printf("Queue: ");

    while (temp != NULL)
    {
        printf("%d ", temp->data);
        temp = temp->next;
    }

    printf("\n");
}

int main()
{
    enqueue(10);
    enqueue(20);
    enqueue(30);

    display();

    dequeue();

    display();

    return 0;
}

---

25. Complexity of Linked-List Queue

When both front and rear pointers are maintained:

Operation	Time Complexity
Enqueue	O(1)
Dequeue	O(1)
Front	O(1)
Rear	O(1)
Display	O(n)

Space complexity:

$$O(n)$$

The major advantage is that the queue can grow dynamically until available memory is exhausted.

---

26. Comparison of Queue Implementations

Feature	Linear Array	Circular Array	Linked List
Memory	Fixed	Fixed	Dynamic
FIFO	Yes	Yes	Yes
Space reuse	Limited	Excellent	Dynamic
Enqueue	O(1)	O(1)	O(1)
Dequeue	O(1)	O(1)	O(1)
Random access	Possible	Possible	Not direct
Implementation	Easy	Moderate	Moderate
Memory overhead	Low	Low	Pointer overhead

---

27. Important Difference: Linear vs Circular Queue

Linear Queue	Circular Queue
Linear arrangement	Circular logical arrangement
Rear moves toward the end	Rear can wrap around
May waste unused array locations	Reuses available locations
Simpler implementation	Slightly more complex
Suitable for basic applications	Suitable for continuous buffering

---

28. Important Difference: Simple Queue vs Priority Queue

Simple Queue	Priority Queue
FIFO	Priority-based
Arrival order determines service	Priority determines service
All elements generally have equal status	Elements have different priorities
Used in ordinary waiting-line systems	Used in priority-based scheduling

---

29. Applications of Different Queues

Linear Queue

• Basic scheduling

• Printer jobs

• Customer service systems

Circular Queue

• CPU round-robin scheduling

• Circular buffers

• Network buffering

• Streaming data

Priority Queue

• CPU scheduling

• Event-driven simulation

• Network packet prioritization

• Emergency service systems

• Graph algorithms such as Dijkstra's algorithm

Linked-List Queue

• Dynamic task management

• Operating-system processes

• Applications where queue size is not known in advance

---

30. Queue Operations: Complexity Summary

Operation	Linear Queue	Circular Queue	Linked Queue	Sorted Array Priority Queue
Enqueue/Insert	O(1)	O(1)	O(1)	O(n)
Dequeue/Delete	O(1)	O(1)	O(1)	O(n)
Peek	O(1)	O(1)	O(1)	O(1)
Display	O(n)	O(n)	O(n)	O(n)
Space	O(n)	O(n)	O(n)	O(n)

Note: Priority queue complexity depends on the implementation.

---

31. Important Exam Example

Consider a circular queue of size 5.

Perform:

Enqueue(10)
Enqueue(20)
Enqueue(30)
Enqueue(40)
Dequeue()
Dequeue()
Enqueue(50)
Enqueue(60)

The important concept is that after deleting 10 and 20, the circular queue can reuse the positions that became available.

Students should be able to trace:

• front

• rear

• array positions

• overflow condition

• underflow condition

This is a frequently useful examination exercise.

---

32. Common Errors in Queue Programs

Error 1: Incorrect Empty Condition

Using only:

rear == -1

without considering how front and rear are managed can lead to incorrect behavior.

---

Error 2: Forgetting Underflow

Always check whether the queue is empty before dequeue.

---

Error 3: Forgetting Overflow

Always check whether the queue is full before insertion in a fixed-size array queue.

---

Error 4: Incorrect Circular Increment

Circular queues require:

(rear + 1) % MAX

rather than simply:

rear + 1

---

Error 5: Incorrect Operand/Element Order

For queues, insertion occurs at the rear, while deletion occurs at the front.

---

33. Important Viva Questions

Q1. What is a queue?

A queue is a linear data structure that follows FIFO.

Q2. Where does insertion take place?

At the rear.

Q3. Where does deletion take place?

At the front.

Q4. What is queue overflow?

Attempting to insert an element when no space is available.

Q5. What is queue underflow?

Attempting to delete an element from an empty queue.

Q6. Why is circular queue used?

To efficiently reuse available array positions.

Q7. Which operator is commonly used for circular movement?

The modulo % operator.

Q8. What is a priority queue?

A queue in which elements are processed according to their priority.

Q9. Can a queue be implemented using a linked list?

Yes.

Q10. What is the main difference between stack and queue?

Stack follows LIFO, whereas queue follows FIFO.

---

34. Important University Examination Questions

Short Answer

1. Define enqueue and dequeue.

2. Define queue overflow and underflow.

3. What is a circular queue?

4. Why is circular queue better than linear queue in some applications?

5. What is a priority queue?

6. What is the role of front and rear?

7. Explain the modulo operation in circular queues.

Long Answer

1. Explain all basic operations of a linear queue with algorithms.

2. Write and explain a C program for implementing a circular queue.

3. Explain the limitations of linear queues and how circular queues overcome them.

4. Explain priority queue with suitable example.

5. Implement a queue using a linked list.

6. Compare linear queue, circular queue and priority queue.

Programming Questions

1. Write a C program to implement a linear queue.

2. Write a C program to implement a circular queue.

3. Write a C program to implement a queue using linked list.

4. Implement a priority queue using an array.

5. Write functions for enqueue(), dequeue(), peek() and display().

6. Trace the contents of a circular queue after a given sequence of operations.

---

35. Complete Unit-2 Conceptual Flow

The four topics covered in this unit can now be connected as follows:

Stack

→ LIFO
→ PUSH / POP / PEEK
→ Expression Conversion
→ Expression Evaluation

Queue

→ FIFO
→ ENQUEUE / DEQUEUE
→ Linear Queue
→ Circular Queue
→ Priority Queue
→ Linked-List Queue

---

36. Final Summary 

Topic	Core Concept
Topic 1	Stack ADT and Operations
Topic 2	Expression Conversion and Evaluation
Topic 3	Queue ADT and Types
Topic 4	Operations on Different Types of Queues

Most Important Concepts for Students

• Stack → LIFO

• Queue → FIFO

• PUSH → Stack insertion

• POP → Stack deletion

• ENQUEUE → Queue insertion

• DEQUEUE → Queue deletion

• Linear Queue → Simple FIFO

• Circular Queue → FIFO with wrap-around

• Priority Queue → Priority-based processing

• Linked Queue → Dynamic implementation

This completes the four major topics of Unit 2 with algorithms, C implementations, complexity analysis, examples, applications, and examination-oriented questions.