Queue in Computer Science: Class 12 NCERT Explained Simply

What Is a Queue and Why Is FIFO Important?

A Queue is a linear data structure where elements are added at one end called the rear and removed from the other end called the front. This behaviour follows the First In First Out (FIFO) principle, meaning the first element added will be the first to be removed.

This FIFO principle ensures fairness and order, much like a queue of people waiting in line at a bank. The person who arrives first is served first. In computer science, this is crucial for managing tasks, scheduling processes, and handling data streams.

Key points about FIFO:

• Elements are processed in the exact order they arrive
• Prevents starvation of any element in the queue
• Ensures predictable behaviour in systems

Understanding FIFO helps grasp how queues maintain order and fairness in both real-life and computing scenarios.

Basic Operations on a Queue: Enqueue and Dequeue

The two primary operations on a queue are:

• Enqueue: Adding an element at the rear of the queue
• Dequeue: Removing an element from the front of the queue

These operations maintain the FIFO order.

How Enqueue Works

When you enqueue, the new element joins the rear end. For example, if the queue has elements [A, B, C], and you enqueue D, the queue becomes [A, B, C, D].

How Dequeue Works

When you dequeue, the element at the front is removed. Using the previous example, dequeue removes A, leaving [B, C, D].

Important Notes:

• If the queue is empty, dequeue operation cannot be performed (underflow condition).
• If the queue is full (in fixed size implementations), enqueue cannot be performed (overflow condition).

Worked Example:

Suppose a queue initially empty, perform these operations:

1. Enqueue 10 2. Enqueue 20 3. Enqueue 30 4. Dequeue (removes 10)

Queue after operations: [20, 30]

Queue vs Stack: Understanding the Differences

Queues and stacks are both linear data structures but differ in how elements are added and removed.

Why This Matters for Class 12 Students

Understanding these differences helps in choosing the right data structure for different problems, a key skill in computer science exams and practical applications.

Real-Life Examples and Applications of Queue

Queues are everywhere in daily life and computing:

• Bank or Ticket Counters: People form a queue and are served in the order they arrive.
• Printer Queue: Print jobs are processed in the order they are sent.
• CPU Scheduling: Processes are scheduled in a queue to ensure fair CPU time.
• Call Center Systems: Incoming calls are queued and answered sequentially.

Why Use Queues?

• They ensure fairness and order
• Manage resources efficiently
• Simplify complex scheduling tasks

By relating queue concepts to familiar situations, students can better understand and remember their functionality.

Types of Queues: Simple, Circular, and Priority

Besides the basic queue, there are several variations:

1. Simple Queue: Linear queue with fixed front and rear ends. It can suffer from "queue full" problem even if space is available at the front.

2. Circular Queue: The rear connects back to the front, making the queue circular. This efficiently uses space by reusing freed slots.

3. Priority Queue: Elements are removed based on priority rather than arrival time. Higher priority elements are dequeued first.

Example: Circular Queue

If a queue has size 5 and elements [10, 20, 30] at positions 0,1,2, after dequeueing 10, the front moves to position 1. Enqueueing 40 will place it at position 3. When rear reaches the end, it loops back to the start if space is free.

Understanding these types helps solve different problems efficiently.

Implementing Queue in Programming: Key Points for Class 12

In Class 12 NCERT Computer Science, queues are often implemented using arrays or linked lists.

Array Implementation

• Use two pointers: front and rear
• Enqueue increments rear, dequeue increments front
• Fixed size may cause overflow

Linked List Implementation

• Dynamic size
• Front and rear pointers point to nodes
• Enqueue adds node at rear, dequeue removes node from front

Pseudocode for Enqueue

`` function enqueue(queue, element): if queue is full: return "Overflow" else: rear = (rear + 1) % size # for circular queue queue[rear] = element ``

Pseudocode for Dequeue

`` function dequeue(queue): if queue is empty: return "Underflow" else: element = queue[front] front = (front + 1) % size # for circular queue return element ``

These implementations are fundamental for exam coding questions and understanding data structures.