Easy Notes Of Data structure using C unit-5 @Computer Diploma

Description

5.1 Introduction to Queue

Queue as an ADT (Abstract Data Type)

The queue is a linear data structure that follows the First-In, First-Out (FIFO) principle. This means the element that was inserted first is the first one to be removed, much like a waiting line of people.

• Key Terminology:
  • Front (or Head): The end of the queue where elements are removed (Deletion/Dequeue).
  • Rear (or Tail/Back): The end of the queue where new elements are added (Insertion/Enqueue).
• ADT Concept: As an ADT, a Queue is defined by its logical behavior (FIFO) and the set of operations performed on it, completely independent of its underlying implementation (array or linked list).

Queue Representation in Memory

A queue can be efficiently implemented in memory using two primary methods:

1. Representation using Array (Sequential Allocation):
   • The queue elements are stored in contiguous memory locations.
   • Two pointers, front and rear, are used to track the respective ends of the queue.
   • Challenge: A major drawback of a simple array implementation is the potential for inefficient memory usage due to the movement of the front pointer, which can lead to a situation where the queue is logically empty or has space, but the rear pointer has hit the end of the array (false overflow). This drawback is mitigated by using a Circular Queue.
2. Representation using a Linked List (Dynamic Allocation):
   • The queue is implemented using a sequence of nodes, where each node contains data and a pointer to the next node.
   • The Front pointer points to the first node, and the Rear pointer points to the last node.
   • Advantage: This method is more memory efficient and dynamic, as the queue size can grow or shrink at runtime, avoiding the overflow issues of a fixed-size array (assuming memory is available). Both insertion and deletion can be performed in $O(1)$ time complexity by maintaining both front and rear pointers.

5.2 Types of Queues

The basic concept of the FIFO queue is extended into several specialized types:

1. Linear Queue (Simple Queue): The standard queue where insertion happens only at the rear and deletion happens only at the front. When implemented with a linear array, it suffers from the “false overflow” problem.
2. Circular Queue: An improved array-based implementation where the last element is connected back to the first element, forming a circle. This allows for better memory utilization by reusing the empty spaces created at the beginning after deletions. It uses the modulo operator to wrap the front and rear indices around the array boundaries.
3. Concept of Priority Queue:
   • A special type of queue where each element is associated with a priority.
   • Elements are not removed based on the FIFO principle; instead, the element with the highest priority is removed first.
   • If two elements have the same priority, they are served based on their order of arrival (FIFO).
   • Commonly implemented using a Heap data structure for efficient priority-based operations.
4. Double-Ended Queue (Deque / pronounced “Deck”):
   • A queue structure where elements can be inserted and deleted from both the front and the rear ends.
   • It is a generalized structure that can function as both a queue (by restricting operations to opposite ends) and a stack (by restricting operations to one end).
   • Sub-types: Input-Restricted Deque (deletion from both ends, insertion at one end) and Output-Restricted Deque (insertion at both ends, deletion from one end).

5.3 Queue Operations

The core functionality of a queue is defined by a set of basic operations:

• INSERT (Enqueue): Adds a new element to the rear of the queue.
  • Condition Check: Must check for Queue Full condition before insertion (relevant for array-based or fixed-size implementations).
• DELETE (Dequeue): Removes the element from the front of the queue.
  • Condition Check: Must check for Queue Empty condition before deletion.
• Peek/Front: Returns the value of the element at the front of the queue without removing it.
• isFull(): A function to check if the queue is at its maximum capacity.
• isEmpty(): A function to check if the queue contains no elements.

Queue Operation Conditions

• Queue Full (Overflow): Occurs when an attempt is made to insert a new element into a queue that is already at its capacity (e.g., when the rear pointer reaches the array’s end in a simple linear queue, or under specific conditions in a circular queue).
• Queue Empty (Underflow): Occurs when an attempt is made to delete or retrieve an element from a queue that contains no elements (i.e., the front and rear pointers indicate an empty state).

5.4 Applications of Queue

Queues are essential in numerous computing scenarios where processing must occur in a strict time-ordered sequence:

• Operating Systems:
  • CPU Scheduling: Managing the sequence of processes waiting for CPU time (e.g., FCFS – First Come First Serve scheduling).
  • I/O Buffers (Spooling): Managing jobs like print requests in a printer queue, ensuring jobs are printed in the order they were submitted.
  • Handling Interrupts: Processing system interrupts in the order they occur.
• Computer Networks:
  • Packet Buffering: Routers and switches use queues to temporarily hold data packets arriving faster than they can be processed or transmitted.
• Algorithmic Applications:
  • Breadth-First Search (BFS): A graph traversal algorithm that explores all neighbor nodes at the present depth level before moving on to nodes at the next depth level, naturally using a queue to manage the nodes to visit.
• Simulation: In event-driven simulations, queues are used to manage the order of events.
• Data Transfer: Used in asynchronous data transfer between processes (like pipes, file I/O) where data production and consumption rates may differ.