Notes on Queues in Data Structures

Introduction to Data Structures

• Definition: A way of storing and organizing data.
• Previously Discussed Structures: Arrays, Linked Lists, Stacks.
• Current Topic: Queue as a data structure.

What is a Queue?

• Type: Linear data structure / Abstract Data Type (ADT).
• Purpose: To define features/operations of a queue without detailed implementation.
• Implementation: Can be implemented using arrays, linked lists, or stacks (discussed in next video).

Real-Life Analogy - Movie Ticket Counter

• Scenario: First in line gets served first.
• FIFO Principle: First In, First Out.
  • The person who arrives first gets the ticket first.

Characteristics of Queue

• Order: It is an ordered list.
• Principle: Follows FIFO rules.
• Insertion/Deletion:
  • Insertion (Enqueue): Performed at one end (Rear/Tail).
  • Deletion (Dequeue): Performed at the other end (Front/Head).

Technical Representation

• Ends:
  • Front: Where deletion occurs.
  • Rear: Where insertion occurs.
• Operations:
  • Enqueue (NQ): Adding data to the queue.
  • Dequeue (DQ): Removing data from the queue.
• Logical Representation: Two ends, one for insertion and one for deletion.
• Example: If 2 and 3 are in the queue, Front points to 2 and Rear points to 3.

Queue Operations

1. Enqueue (NQ): Add an element to the rear.
2. Dequeue (DQ): Remove an element from the front.
3. Front/Peak: Returns the element at the front without removal.
4. Is Full: Returns true if the queue is full.
5. Is Empty: Returns true if the queue is empty.

Implementation Details (Using Arrays)

• Initial State: Front and Rear set to -1 to indicate an empty queue.
• Capacity: Define the size of the queue (e.g., 5).
• Enqueue Operations:
  • Increment Rear and add element at Rear index.
• Dequeue Operations:
  • Increment Front and remove element at Front index.
• Underflow/Overflow Conditions:
  • Underflow: Attempting to dequeue from an empty queue.
  • Overflow: Attempting to enqueue into a full queue.

Time Complexity

• All operations (NQ, DQ, Front, Is Full, Is Empty) take constant time O(1).

Drawbacks of Standard Queue

• Wastage of space as elements are only added at the rear and removed from the front—leading to potential overflow even when there are free spaces in the array.
• Solution: Circular Queue (to be discussed later).

Applications of Queues

• Single Shared Resource: Such as printers where requests are queued.
• Customer Service: Calls placed on hold are managed using queues.
• Process Management in OS: Processes are put in queues to be executed by the CPU.

Conclusion

• In the next video, we will discuss implementations of queues using arrays, linked lists, and stacks.
• Reminder: Review the applications of queues and their operations for better understanding.