Login / Register
Follow Us
0
0
Register Free!
Register Free!
Online Mock Tests & Exam Preparation | Target Exams
माध्यम चुनें / Select Medium:
Eng (English) Hindi (हिन्दी)
CBSE • कक्षा XII • Computer Science • अध्याय 4
अनुमानित समय: 45 Mins
प्रगति: अध्ययनरत

कतार (Queue in Data Structures)

In CBSE Class 12 Computer Science, "Queue" provides an exhaustive master resource on First-In-First-Out (FIFO) linear data structures. This comprehensive chapter deconstructs the dual-ended Queue Abstract Data Type, FRONT and REAR pointer mechanics, primitive operations (`enqueue`, `dequeue`, `peek`, `isEmpty`), Queue Underflow and Overflow boundary conditions, list-based and `collections.deque` implementations in Python, and critical computing applications including operating system process scheduling, print spooling, and breadth-first search (BFS) graph traversals aligned with the 2026–27 CBSE curriculum.

अध्याय CBT ऑनलाइन टेस्ट दें सभी अध्याय देखें
प्रस्तावना अध्याय अवधारणाएँ सिंटेक्स एवं प्रमुख कमांड अध्याय सारांश स्व-मूल्यांकन अभ्यास टेस्ट दें

How Do Ticket Counters, Operating Systems, and Web Servers Ensure Fair First-Come-First-Served Service?

Imagine standing in line at a movie theater ticket counter. The person who arrived first gets served first, and newcomers join the back of the line. If someone pushed straight to the front, chaos would erupt. In computer systems, thousands of requests arrive simultaneously: five employees sending PDF documents to a single office printer, fifty web clients clicking "Purchase" during a flash sale, and hundreds of background processes competing for CPU time. How does an operating system manage shared resources so that every task is handled fairly in the exact order it arrived without starvation or data collisions? It uses the Queue data structure.

यह अध्याय क्यों महत्वपूर्ण है

Queues are the heartbeat of modern asynchronous computing, cloud architecture, and networking. Message brokers like Apache Kafka and RabbitMQ, microservice architectures, and operating system scheduling algorithms (Round Robin, First-Come-First-Served) are built entirely on queue abstractions. Mastering queue pointers, avoiding inefficient array shift operations, and understanding FIFO semantics is vital for building high-scale distributed systems.

अध्ययन से पूर्व (आवश्यक ज्ञान)

  • Linear data structures and list operations from Stack (Chapter 3).
  • Python list methods: `append()`, `pop()`, and length checking.
  • Conceptual understanding of First-In-First-Out (FIFO) access discipline.

इस अध्याय के लक्ष्य

  • Define a Queue linear data structure and explain the First-In-First-Out (FIFO) / First-Come-First-Served (FCFS) principle.
  • Contrast the dual-ended pointer architecture of Queues (FRONT for removal, REAR for insertion) with single-ended Stacks.
  • Implement the 4 core primitive operations: `enqueue(item)`, `dequeue()`, `peek()`, and `isEmpty()`.
  • Identify and prevent Queue Underflow and analyze time complexity trade-offs in list implementations.
  • Construct production-grade Python implementations using lists and explore high-performance `collections.deque`.
  • Evaluate practical applications of queues in operating systems (printer spooling, CPU task scheduling) and network routers.

अध्याय रूपरेखा एवं प्रगति

1 1. The FIFO Access Principle & Queu...
2 2. Python Implementation & The Shif...
3 3. Real-World Applications of Queue...

सम्पूर्ण सैद्धांतिक एवं वैचारिक अध्ययन

1. The FIFO Access Principle & Queue ADT

Understand

A Queue is a linear data structure that operates under the FIFO (First-In, First-Out) principle. Unlike a stack which operates at a single end (TOP), a queue operates across two distinct ends:

  • REAR (Tail): The end where new elements are inserted (Enqueue operation).
  • FRONT (Head): The end where existing elements are removed (Dequeue operation).
Core Primitive Operations:
  • `enqueue(item)`: Inserts a new element at the REAR of the queue.
  • `dequeue()`: Removes and returns the element at the FRONT of the queue. If the queue is empty, triggers Queue Underflow.
  • `peek()` / `front()`: Returns the value of the front element *without* removing it.
  • `isEmpty()`: Returns `True` if the queue contains zero elements, `False` otherwise.

2. Python Implementation & The Shift Complexity Trade-Off

Understand & Complexity Analysis

When implementing a queue using a standard Python list, developers must choose which end represents FRONT and REAR:

Standard CBSE List-Based Approach:

Use the end of the list (`lst[-1]`) as REAR (insertion via `lst.append()`), and the beginning (`lst[0]`) as FRONT (deletion via `lst.pop(0)`):

def create_queue():
    return []

def isEmpty(queue):
    return len(queue) == 0

def enqueue(queue, item):
    queue.append(item)  # Inserted at REAR in O(1) time
    print(f"Enqueued: {item} | Queue: {queue}")

def dequeue(queue):
    if isEmpty(queue):
        print("Queue Underflow Error: Queue is empty!")
        return None
    # Removed from FRONT (index 0): requires O(n) shift!
    removed = queue.pop(0)
    print(f"Dequeued: {removed} | Remaining Queue: {queue}")
    return removed

def peek(queue):
    if isEmpty(queue):
        print("Queue Underflow!")
        return None
    return queue[0]  # Front item
Advanced Engineering Note: `lst.pop(0)` on a Python list requires shifting all subsequent elements leftward in memory, yielding $O(n)$ time. In production Python, the high-performance collections.deque (double-ended queue based on doubly linked blocks) is used to achieve $O(1)$ operations at both ends (`append()` and `popleft()`).

3. Real-World Applications of Queues in Computer Science

Real-Life Systems
  1. Print Spooling: When multiple users send documents to a networked printer, documents are buffered in a FIFO print queue on disk. The printer services jobs in exact order of arrival.
  2. CPU Process Scheduling (FCFS & Round Robin): In multi-tasking operating systems, processes waiting for CPU execution reside in the Ready Queue. The scheduler dispatches the process at the front of the queue.
  3. Network Packet Buffering: Routers hold incoming network packets in FIFO queues when packet arrival rates temporarily exceed transmission link bandwidth.
  4. Breadth-First Search (BFS): Graph and tree traversal algorithms use queues to explore nodes level-by-level in concentric rings from a starting vertex.

प्रोग्रामिंग सिंटेक्स, स्टेटमेंट्स एवं भाषा अनुवादक नियम

FIFO Access Law
$$\text{Exit Sequence}(e_1, e_2, \dots, e_n) = (e_1, e_2, \dots, e_n)$$
Exact preservation of arrival order.
Queue Time Complexity (List-based)
$$T(\text{enqueue}) = O(1), \quad T(\text{dequeue}) = O(n)$$
pop(0) requires linear element shifting in dynamic lists.

Queue FIFO Data Flow Architecture

Queue Linear Data Structure (FIFO Discipline) 10 ↑ FRONT 20 30 40 ↑ REAR DEQUEUE Exits from FRONT ENQUEUE Enters at REAR Dual-Ended Architecture: FIFO (First-In, First-Out) First element entered is guaranteed to be the first element removed.

अध्याय का सार संक्षेप एवं 10 मुख्य निष्कर्ष

मुख्य बिंदु 1
A Queue is a linear data structure operating under the First-In, First-Out (FIFO) principle.
मुख्य बिंदु 2
Elements are inserted at the REAR end (Enqueue) and removed from the FRONT end (Dequeue).
मुख्य बिंदु 3
`enqueue(x)` adds an item to the rear; `dequeue()` removes and returns the front item.
मुख्य बिंदु 4
Queue Underflow occurs when attempting to dequeue or peek from an empty queue.
मुख्य बिंदु 5
In Python lists, using `lst.append()` for enqueue is $O(1)$, but `lst.pop(0)` for dequeue is $O(n)$ due to left-shifting.
मुख्य बिंदु 6
High-performance production queues use Python's `collections.deque` with $O(1)$ `append()` and `popleft()`.
मुख्य बिंदु 7
Print spoolers use queues to service documents in exact order of arrival.
मुख्य बिंदु 8
Operating system CPU schedulers use ready queues for First-Come-First-Served and Round Robin scheduling.
मुख्य बिंदु 9
Network routers use packet buffers organized as queues to absorb bursty network traffic.
मुख्य बिंदु 10
Breadth-First Search (BFS) in graph theory uses queues to explore vertices in increasing order of distance.

स्व-मूल्यांकन अभ्यास (Check Your Understanding)

मूल वैचारिक स्पष्टता की जांच के लिए नैदानिक प्रश्न। पहले स्वयं हल करें, फिर उत्तर देखें।

1
Differentiate between a Stack and a Queue based on access discipline, number of operational ends, and primary operations.
उत्तर एवं व्याख्या देखें
उत्तर: • Access Discipline: Stack operates under LIFO (Last-In, First-Out); Queue operates under FIFO (First-In, First-Out).
• Operational Ends: Stack operates exclusively at a single end (TOP) for both insertion and deletion; Queue operates across two distinct ends (REAR for insertion, FRONT for deletion).
• Primary Operations: Stack uses `push` and `pop`; Queue uses `enqueue` and `dequeue`.
Stack is single-ended LIFO (push/pop); Queue is double-ended FIFO (enqueue at rear, dequeue at front).
2
Given an initially empty queue, trace the queue contents and FRONT/REAR positions after each operation:
`enqueue(10)`, `enqueue(20)`, `dequeue()`, `enqueue(30)`, `enqueue(40)`, `dequeue()`, `peek()`.
उत्तर एवं व्याख्या देखें
उत्तर:
  1. enqueue(10) → Queue: [10], FRONT: 10, REAR: 10
    2. enqueue(20) → Queue: [10, 20], FRONT: 10, REAR: 20
    3. dequeue() → Removes 10; Queue: [20], FRONT: 20, REAR: 20
    4. enqueue(30) → Queue: [20, 30], FRONT: 20, REAR: 30
    5. enqueue(40) → Queue: [20, 30, 40], FRONT: 20, REAR: 40
    6. dequeue() → Removes 20; Queue: [30, 40], FRONT: 30, REAR: 40
    7. peek() → Returns 30 (FRONT item); Queue remains [30, 40].

Track elements from left (FRONT) to right (REAR). Enqueue appends; Dequeue removes from left.
3
What is Queue Underflow? Write a Python function `safe_dequeue(q)` that guards against underflow.
उत्तर एवं व्याख्या देखें
उत्तर: Queue Underflow occurs when a program attempts to remove (dequeue) an item from an empty queue (`len(queue) == 0`).
Code:
def safe_dequeue(queue):
    if len(queue) == 0:
        print("Queue Underflow Error: Queue has no elements!")
        return None
    return queue.pop(0)

Check len(queue) == 0 before executing pop(0).
4
Why does using a standard Python list for a queue suffer from a performance bottleneck during `dequeue()`? How is this resolved in professional Python?
उत्तर एवं व्याख्या देखें
उत्तर: When using a standard Python dynamic list, `enqueue` using `lst.append()` takes $O(1)$ constant time. However, `dequeue` using `lst.pop(0)` removes the first element, forcing Python to shift all remaining $n-1$ elements in memory one index to the left, resulting in an inefficient $O(n)$ linear time complexity. In professional Python, this is solved by using collections.deque, which is implemented as a doubly linked block list, enabling $O(1)$ constant time for both `append()` and `popleft()`.
pop(0) requires shifting elements (O(n)); collections.deque provides O(1) popleft().
5
Explain the role of a Queue in Operating System Print Spooling.
उत्तर एवं व्याख्या देखें
उत्तर: A computer processor operates billions of times faster than a physical mechanical printer. When multiple applications send print jobs simultaneously, the operating system cannot wait for each document to finish printing. Instead, it places print jobs in a FIFO queue managed by a background daemon called the Print Spooler. The spooler dispatches print jobs to the printer strictly in the order they arrived, freeing up applications immediately.
Buffers print jobs in FIFO order so fast CPUs are not stalled waiting for slow printers.
6
Write a Python program implementing a customer service queue with options to: 1. Add Customer, 2. Serve Customer, 3. View Next Customer, 4. Exit.
उत्तर एवं व्याख्या देखें
उत्तर: 
queue = []
def service_desk():
    while True:
        print("\n1. Add Customer  2. Serve Customer  3. View Next  4. Exit")
        ch = input("Enter choice: ")
        if ch == "1":
            name = input("Customer name: ")
            queue.append(name)
            print(f"{name} added to queue.")
        elif ch == "2":
            if queue:
                print(f"Serving customer: {queue.pop(0)}")
            else:
                print("No customers waiting!")
        elif ch == "3":
            print(f"Next in line: {queue[0]}" if queue else "Queue empty.")
        elif ch == "4":
            break

append() to add at rear; pop(0) to serve from front.
7
What is a Circular Queue? What limitation of linear array-based queues does it overcome?
उत्तर एवं व्याख्या देखें
उत्तर: In a fixed-size linear array queue, dequeuing elements leaves empty slots at the front of the array that cannot be reused once the REAR pointer reaches the end, falsely reporting Queue Overflow even when space exists. A Circular Queue connects the last position back to the first position in a ring using modulo arithmetic (`rear = (rear + 1) % capacity`), allowing vacant front slots to be fully reused.
Wraps rear and front pointers around using modulo arithmetic to reuse empty slots.
8
How does Breadth-First Search (BFS) in graph traversal use a queue?
उत्तर एवं व्याख्या देखें
उत्तर: BFS explores vertices level by level. It enqueues the starting node. In each step, it dequeues a node, visits it, and enqueues all of its unvisited neighboring nodes into the rear of the queue. The FIFO property guarantees that all nodes at distance $d$ are completely visited before any node at distance $d+1$ is processed.
Enqueues neighbors and dequeues sequentially to explore vertices level-by-level.
अध्याय का अध्ययन पूर्ण हुआ?
अभ्यास के लिए तैयार?

ऑनलाइन CBT टेस्ट देकर तैयारी का मूल्यांकन करें

झारखण्ड बोर्ड परीक्षा पैटर्न पर आधारित बहुविकल्पीय प्रश्नों का ऑनलाइन टेस्ट दें। तुरंत परिणाम, समय विश्लेषण और प्रत्येक प्रश्न का विस्तृत हल प्राप्त करें।

फाउंडेशन टेस्ट
15 MCQs • मूल अवधारणाएँ
एडवांस्ड टेस्ट
15 MCQs • HOTS और ट्रैप्स

कक्षा 12 Computer Science के सभी अध्याय

अध्याय 1: पायथन में अपवाद प्रबंधन (Exception Handling) अध्याय 2: पायथन में फाइल हैंडलिंग (File Handling) अध्याय 3: स्टैक (Stack in Data Structures) अध्याय 4: कतार (Queue in Data Structures) अध्याय 5: क्रमबद्धता (Sorting) अध्याय 6: खोज विधियां (Searching) अध्याय 7: डेटा की समझ (Understanding Data) अध्याय 8: डेटाबेस अवधारणाएं (Database Concepts) अध्याय 9: स्ट्रक्चर्ड क्वेरी लैंग्वेज (SQL) अध्याय 10: कंप्यूटर नेटवर्क अध्याय 11: डेटा संचार (Data Communication) अध्याय 12: सुरक्षा पहलू (Security Aspects)

AI अध्ययन मित्र

त्वरित शंका समाधान

कतार (Queue in Data Structures) में कोई संदेह या प्रश्न है? हमारे AI अध्ययन मित्र से तुरंत समझें।