Chapter 14: Queues - Notes

Chapter Scope

• Queue processing

• Using queues to solve problems

• Various queue implementations

• Comparing queue implementations

Queues

• A queue is a collection where elements are added at one end (rear) and removed from the other end (front).

• Queues are managed using the FIFO (First-In, First-Out) principle.

• Elements are removed in the order they arrive.

• Real-world examples of queues:

  • Checkout line at a grocery store

  • Cars at a stoplight

  • Assembly line

Queue ADT Overview

• Queue Abstract Data Type (ADT)

• Basic operations:

  • Enqueuing: Adding an element to the rear of the queue.

  • Dequeuing: Removing an element from the front of the queue.

• Implementation of queues can be done using:

  • Arrays

  • Linked lists

The Queue ADT

• A queue is a restricted list where:

  • Insertion (enqueue) occurs at one end (rear).

  • Deletion (dequeue) occurs at the other end (front).

• Basic operations:

  • enqueue: Inserts an element at the rear of the list.

  • dequeue: Deletes the element from the front of the list.

• Queues follow the First-In, First-Out (FIFO) principle.

Enqueue and Dequeue

• Enqueue: Inserts an element at the rear of the queue.

• Dequeue: Removes an element from the front of the queue.

• Analogy: Like checkout lines, queues have a front and a rear.

Queue ADT

• Similar to a stack, a queue is a list.

• Insertion is done at one end, while deletion is performed at the other end.

• Accessing elements follows a First-In, First-Out (FIFO) order.

• Analogy: Customers in a checkout line – the first customer in line is the first one served.

Standard Queue Operations

• enqueue: Adds an element to the rear of the queue.

• dequeue: Removes an element from the front of the queue.

• first: Examines the element at the front of the queue (without removing it).

• isEmpty: Determines if the queue is empty.

• size: Determines the number of elements in the queue.

• toString: Returns a string representation of the queue.

Implementing a Queue with Links

• Uses both front and rear references because operations occur at both ends of the queue.

Implementing a Queue with Links (Enqueue Example)

• Adding element E to the rear of the queue requires updating the rear reference to point to the new element.

Implementing a Queue with Links (Dequeue Example)

• Removing an element from the front involves updating the front reference to the next element in the queue.