Sy BCS || Semester 3 || Data Structure 1 || 5.Queue || Complete Chapter || SPPU || NEP Pattern ||

Summary

The lecture introduces queues, compares their implementations and variants, and walks through the functions used in a basic menu-driven C program.

Queue Fundamentals

A queue is an ordered collection in which insertion happens at the rear (enqueue) and deletion happens at the front (dequeue).

Queues follow FIFO (First In, First Out): the element added first is removed first. This contrasts with a stack, where the most recently added item is removed first.

A peek operation returns or displays the front element without deleting it.

Common Operations and Conditions

• Enqueue: Adds an element at the rear.
• Dequeue: Removes and returns the element at the front.
• Peek: Inspects the front element without removing it.
• isFull / overflow check: Detects whether a queue is full.
• isEmpty / underflow check: Detects whether a queue is empty.

Queue Applications

Queues are used to manage work or data in order, including:

• Waiting lists for shared resources such as printers, disks, and CPUs.
• Asynchronous data transfer between processes, including through pipes, files, and sockets.
• Buffers in media applications and devices, such as MP3 or CD players.
• Maintaining the order of songs in a playlist.
• Handling interrupts in an operating system.

Static and Dynamic Implementations

Static Queue Using an Array

• Uses a fixed-size array whose memory is allocated at compile time.
• Tracks front and rear positions using indexes.
• Stores elements in contiguous memory.
• Is simple and generally fast, but its capacity cannot grow during execution.
• A linear array queue can report overflow when the rear reaches the end, even if earlier slots were freed by deletions. A circular queue can reuse those slots.

Dynamic Queue Using a Linked List

• Represents each element as a node containing data and a pointer to the next node.
• Uses a front pointer to refer to the first node and a rear pointer to refer to the last.
• Allocates nodes at runtime, allowing the queue to grow or shrink as elements are added or removed.
• Avoids a fixed array limit, provided memory is available, but uses extra memory for pointers and requires pointer manipulation.

The instructor describes enqueue and dequeue as constant-time operations in these implementations.

Types of Queues

1. Simple or linear queue

   • Inserts at the rear and deletes from the front.
   • Follows FIFO.

2. Circular queue

   • Treats the final position as connected to the first, forming a ring.
   • Reuses spaces freed at the beginning of the queue.
   • Is more space-efficient than a linear array queue, though its implementation is somewhat more involved.

3. Priority queue

   • Associates a priority with each element, and serves elements according to priority.
   • The example orders larger values ahead of smaller ones.
   • Handles elements with equal priority in FIFO order.

4. Double-ended queue (deque)

   • Allows insertion and deletion at both the front and the rear.

C Program Outline

The instructor describes a fixed-size, array-based linear queue with a maximum size of five and front and rear indexes initially set to -1.

• Insertion (enqueue):
  • Checks whether the rear has reached the last array position; if so, reports overflow.
  • If the queue is empty, initializes the front position.
  • Advances the rear and stores the new value there.
• Deletion (dequeue):
  • Checks whether the queue is empty; if so, reports underflow.
  • Otherwise, advances the front to remove the front element.
• Display:
  • If the queue is empty, reports that it has no elements.
  • Otherwise, prints the elements from the front index through the rear index.

The program is presented as a menu-driven exercise that brings these operations together. As described, it uses a linear array queue, so it does not reuse freed slots at the beginning as a circular queue would.

The lecture closes by marking the end of the queue chapter and the data-structures syllabus covered in the series.

Speakers or Sources Featured

• Instructor/host: The speaker presenting the lesson for Kadam’s Study Centre.
• Other speakers or external sources: None identified in the subtitles.