TOPIC 4 QUEUE

Topic 4: Queues

  • CSC248 – Fundamental of Data Structures

  • Prepared by: NYCJ@KPPIM, UiTM

  • Branch: Perlis Campus Arau

Introduction to Queues

  • Definition: A queue is a sequence of elements where:

    • Insertion (enqueue) occurs only at the back of the sequence.

    • Removal (dequeue), retrieval, and modification are allowed only at the front of the sequence.

  • Characteristics:

    • FIFO (First-In-First-Out) data structure.

    • Examples include:

      • Cars in line at a drive-through.

      • Fans waiting to buy tickets to a game.

      • Customers in a checkout line.

      • Airplanes waiting to take off.

Queue Operations

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

  • Dequeue: Removes the first element from the queue.

  • IsEmpty: Checks whether the queue is empty.

Usage of Queue Data Structure

  • Single Processor Systems: Only one application can be serviced at a time, requiring a queue for processor time.

  • Spooling in Printing: In a network with a single printer, print jobs are placed in a queue until the printer becomes available.

  • Networking: Routing nodes process one packet at a time, necessitating a queue.

  • File Server Requests: File access requests from clients are also queued until served.

Queue Implementation

  • Queues can be implemented using linked lists.

    • Elements can be stored anywhere in memory.

    • Enqueue adds elements at the back of the list, while dequeue removes from the front.

Queue Class Definition

  • The Queue class extends the LinkedList class.

  • Key Features:

    • Default Constructor: Initializes a new queue.

    • enqueue(Object): Inserts element at the end.

    • dequeue(): Removes and returns the front element.

    • getFront(): Retrieves the front element without removal.

    • getEnd(): Retrieves the end element without removal.

    • isEmpty(): Checks if the queue is empty (inherited from LinkedList).

Queue Applications

  • Searching for specific elements within the queue.

  • Performing operations such as calculating averages, and determining minimum and maximum values.

  • When traversing, elements must be dequeued; to retain them, remove data temporarily stored in another queue.

Creating and Using a Queue in Code

  • Creating a Queue:

    • Queue theQueue = new Queue();

    • Queue tempQueue = new Queue();

  • Adding Elements into a Queue:

    for(int i = 0; i < 5; i++) {
    String sID = JOptionPane.showInputDialog("Enter student id: ");
    String sName = JOptionPane.showInputDialog("Enter name: ");
    String sPart = JOptionPane.showInputDialog("Enter part: ");
    String sCGPA = JOptionPane.showInputDialog("Enter CGPA: ");
    int iID = Integer.parseInt(sID);
    int iPart = Integer.parseInt(sPart);
    double dCGPA = Double.parseDouble(sCGPA);
    Student stud = new Student(iID, sName, iPart, dCGPA);
    theQueue.enqueue(stud);
}

  • Displaying Elements in a Queue:

    Object data;
Student S;
while (!theQueue.isEmpty()) {
    data = theQueue.dequeue();
    S = (Student) data;
    System.out.println(S.toString());
    tempQueue.enqueue(S);
}

Finding Minimum and Maximum Values in a Queue

  • Initialize values:

    double max = -99999.99;
double min = 99999.99;
Student bestStudent = null;
Student weakStudent = null;

  • Process the queue to find max and min:

    while (!theQueue.isEmpty()) {
    data = theQueue.dequeue();
    S = (Student) data;
    if (S.getCGPA() > max) { max = S.getCGPA(); bestStudent = S; }
    if (S.getCGPA() < min) { min = S.getCGPA(); weakStudent = S; }
}

Restoring the Original Queue

  • Elements from the temporary queue are reinserted:

    while (!tempQueue.isEmpty()) {
    theQueue.enqueue(tempQueue.dequeue());
}