Queue in Computer Science: Class 12 NCERT Complete Guide

What is a Queue? Understanding the Basics

A Queue is a linear data structure used in computer science to store elements in an ordered manner. It follows the FIFO (First-In-First-Out) principle, meaning the first element added is the first to be removed. This is different from a stack, which follows Last-In-First-Out (LIFO).

In a queue:

• Insertion happens at the rear (also called the tail).
• Deletion happens at the front (also called the head).

This structure ensures fairness, as elements are processed in the exact order they arrive. Real-life examples include:

• Students lining up for assembly
• Vehicles waiting at a petrol pump
• Customers queuing at a bank counter

These examples clearly show how the first to join is the first to be served.

Understanding queues is crucial for Class 12 NCERT Computer Science students as it forms the base for many applications like task scheduling and managing requests in servers.

Key Operations on a Queue: Enqueue and Dequeue

The two main operations performed on a queue are:

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

These operations maintain the FIFO order. Let's look at how these work:

1. Enqueue Operation:

• Check if the queue is full (in case of fixed size).
• Insert the new element at the rear.
• Update the rear pointer.

2. Dequeue Operation:

• Check if the queue is empty.
• Remove the element from the front.
• Update the front pointer.

Example:

Suppose a queue has elements: A, S, D, F (front to rear).

• After one dequeue, the element 'A' is removed.
• The queue now contains: S, D, F.

This sequence ensures that elements are processed in the order they arrived.

In Class 12 NCERT, these operations are fundamental for understanding how queues work programmatically.

FIFO Principle Explained with Examples

The FIFO (First-In-First-Out) principle means that the first element added to the queue will be the first one to be removed. This principle is central to how queues function.

Real-life Example:

Consider a queue at a bank:

• The first customer to arrive is served first.
• The next customer waits behind, and so on.

This ensures fairness and order.

Computer Science Example:

In CPU scheduling, processes waiting for execution are placed in a queue. The process that arrives first gets the CPU first.

Visual Representation:

This table shows how elements are removed from the front and added at the rear, maintaining FIFO.

Queue vs Stack: Understanding the Differences

Both Queue and Stack are linear data structures but differ in how elements are added and removed.

Understanding these differences helps Class 12 students choose the right data structure for different problems.

Types of Queues and Their Applications

Besides the basic queue, there are several variations used in computer science:

• Simple Queue: Basic FIFO queue with insertion at rear and deletion at front.
• Circular Queue: Rear and front pointers wrap around to use the space efficiently.
• Priority Queue: Elements are dequeued based on priority rather than arrival time.
• Double-Ended Queue (Deque): Insertion and deletion can happen at both ends.

Applications:

• Task Scheduling: Operating systems use queues to manage processes.
• Buffering: Queues temporarily hold data in devices like printers.
• Network Traffic: Routers use queues to manage packet transmission.

Class 12 NCERT syllabus covers simple queues but knowing these types helps in advanced studies.

Implementing a Queue: Array and Linked List Methods

Queues can be implemented in two common ways:

1. Array Implementation:

• Fixed size.
• Rear and front pointers track insertion and deletion.
• Simple but can waste space if elements are dequeued.

2. Linked List Implementation:

• Dynamic size.
• Each node points to the next.
• Front points to the first node, rear to the last.

Worked Example: Array Implementation

Suppose we have an array of size 5:

• Initially, front = -1, rear = -1.
• Enqueue 10: front = 0, rear = 0, queue = [10, _, _, _, _]
• Enqueue 20: rear = 1, queue = [10, 20, _, _, _]
• Dequeue: front = 1, element removed = 10

This example shows how pointers move to manage the queue.

Understanding these implementations is essential for Class 12 students to write efficient code.