IT2503 Laboratory Exercise 1 — Queue Operations Notes

Objective

• Understand and apply a user-defined abstract data type (queue) to implement basic FIFO operations.
• Specifically, simulate enqueue and dequeue operations and inspect the front of the queue using peek.
• Illustrate each operation and maintain a clear visual of the queue from front to rear.
• Develop supporting materials: pseudocode, a flowchart, and a compiled write-up suitable for submission.

Requirements and Context

• Topic: Laboratory Exercise on Data Structures and Algorithms (Queue operations).
• Platform expectations (as per transcript): MS PowerPoint illustration of operations, step-by-step queue state drawings, pseudocode generation, and a simple flowchart, compiled in MS Word and submitted as PDF.
• Data structure: Queue (FIFO) implemented via a user-defined abstract data type with operations Enqueue, Dequeue, and Peek.
• List of operations to perform in sequence:
  • ENQUEUE("Apple")
  • ENQUEUE("Banana")
  • ENQUEUE("Cherry")
  • DEQUEUE()
  • ENQUEUE("Durian")
  • PEEK()
  • ENQUEUE("Elderberry")
  • DEQUEUE()
  • DEQUEUE()
  • PEEK()
• After each operation, draw the current state of the queue from front to rear (left to right) and label the queue direction.
• Deliverables: a) updated diagrams, b) pseudocode, c) a simple flowchart, d) a compiled write-up (Word) and final PDF.

Step-by-step Queue Simulation (Front to Rear: Left to Right)

• Initial state before any operation: Front [] Rear (empty queue)

1) ENQUEUE("Apple")

• Queue contents: [ Apple ]
• Front to Rear: Front [ Apple ] Rear

2) ENQUEUE("Banana")

• Queue contents: [ Apple, Banana ]
• Front to Rear: Front [ Apple, Banana ] Rear

3) ENQUEUE("Cherry")

• Queue contents: [ Apple, Banana, Cherry ]
• Front to Rear: Front [ Apple, Banana, Cherry ] Rear

4) DEQUEUE()

• Removes the oldest item: Apple
• Queue contents: [ Banana, Cherry ]
• Front to Rear: Front [ Banana, Cherry ] Rear

5) ENQUEUE("Durian")

• Queue contents: [ Banana, Cherry, Durian ]
• Front to Rear: Front [ Banana, Cherry, Durian ] Rear

6) PEEK()

• Operation does not modify the queue; reports the front element.
• Front is: Banana
• Queue contents remain: [ Banana, Cherry, Durian ]
• Front to Rear: Front [ Banana, Cherry, Durian ] Rear

7) ENQUEUE("Elderberry")

• Queue contents: [ Banana, Cherry, Durian, Elderberry ]
• Front to Rear: Front [ Banana, Cherry, Durian, Elderberry ] Rear

8) DEQUEUE()

• Removes Banana
• Queue contents: [ Cherry, Durian, Elderberry ]
• Front to Rear: Front [ Cherry, Durian, Elderberry ] Rear

9) DEQUEUE()

• Removes Cherry
• Queue contents: [ Durian, Elderberry ]
• Front to Rear: Front [ Durian, Elderberry ] Rear

10) PEEK()

• Operation does not modify the queue; reports the front element.
• Front is: Durian
• Final queue contents: [ Durian, Elderberry ]
• Front to Rear: Front [ Durian, Elderberry ] Rear

Representing the queue states (visual, left-to-right front-to-rear)

• Step 1: Front [ Apple ] Rear
• Step 2: Front [ Apple, Banana ] Rear
• Step 3: Front [ Apple, Banana, Cherry ] Rear
• Step 4: Front [ Banana, Cherry ] Rear
• Step 5: Front [ Banana, Cherry, Durian ] Rear
• Step 6: Front [ Banana, Cherry, Durian ] Rear (PEEK reports front = Banana)
• Step 7: Front [ Banana, Cherry, Durian, Elderberry ] Rear
• Step 8: Front [ Cherry, Durian, Elderberry ] Rear
• Step 9: Front [ Durian, Elderberry ] Rear
• Step 10: Front [ Durian, Elderberry ] Rear (PEEK reports front = Durian)

Pseudocode (enqueue a set of inputs, dequeue one, then peek at front)

• Pseudocode:

Algorithm QueueSimulation(inputs):
    Q <- new Queue()
    for item in inputs do
        Q.enqueue(item)
    Q.dequeue()
    front <- Q.peek()
    return front, Q.contents

• Notes:
  • Assumes a standard Queue interface with methods Enqueue(item), Dequeue(), and Peek() returning the front item without removing it.
  • If Dequeue is called on an empty queue, the operation should safely handle underflow (not shown explicitly in transcript; include guard in real implementation).
  • The inputs in the transcript are: ["Apple", "Banana", "Cherry", "Durian", "Elderberry"] with the Dequeue and Peek steps as described.

Flowchart Illustration (simple textual representation)

• Flowchart symbols used:
  • Start/End: Ovals
  • Processing steps: Rectangles
  • Input/Output: Parallelograms
  • Decision: Diamonds
• Textual flowchart outline:
  Start
  |
  [Input: items] --> [Process: Enqueue each item] --(loop)--> [Decision: more items?] --Yes--> back to Enqueue; --No--> Dequeue one
  |
  [Process: Dequeue]
  |
  [Process: Peek]
  |
  End
• This corresponds to the pseudocode loop over inputs, followed by a Dequeue, then a Peek, and finally end.

Flowchart Symbols and Visual Guide

• Start/End: Ovals labeled Start and End
• Input/Output: Parallelograms for input items and for output results (if shown)
• Process: Rectangles for enqueue, dequeue, and peek operations
• Decision: Diamond for loop control (more inputs?)
• Flow direction: Arrows showing the sequence and the loop back to the input step

Formulas and Notation (Queue sizes and FIFO semantics)

• Let |Q| denote the number of items currently in the queue.
• Initialization:
  $|Q| = 0$
• Enqueue operation (for a valid item):
  $|Q|<em>{ ext{after}} = |Q|</em>{ ext{before}} + 1$
• Dequeue operation (if not empty):
  $|Q|<em>{ ext{after}} = |Q|</em>{ ext{before}} - 1$
• Peek operation does not modify the queue:
  $Q_{ ext{front}} = ext{oldest enqueued item not yet dequeued}$
• Overall, the queue follows FIFO: the element that.entered first is the first to be removed.
• Example runoff for the transcript sequence yields the states shown above.

Connections to Foundations and Real-World Relevance

• Foundational principle: FIFO data structure is essential for resource management where order matters (e.g., print queues, task scheduling, IO buffering).
• Real-world relevance: Web server request queues, customer service line management, operating system process scheduling, and network packet buffering rely on queue semantics to ensure fairness and determinism.
• Relationship to other ADTs: Queue complements stacks (LIFO) and lists; many algorithms build on queues to maintain order while processing elements.
• Practical considerations: capacity limits, circular buffer implementations, and error handling for underflow/overflow in production systems.

Ethical, Philosophical, and Practical Implications

• Fairness and ordering: FIFO enforces a strict order; discussion may include how to handle priority in real systems (where a priority queue might override FIFO semantics).
• Transparency: System logs should reflect the exact sequence of dequeued items to ensure traceability and accountability.
• Efficiency and correctness: Proper handling of edge cases (empty queue, overflow) is essential for robust software.

Grading Rubric (Summary Reference)

• Queue Operation (x5, total 25 points)
  • All operations executed in correct FIFO order; diagrams clearly labeled and complete: ___/25
• Pseudocode Construction (x5, total 25 points)
  • Pseudocode aligns with operations; clear, logical, properly structured: ___/25
• Flowchart Representation (x5, total 25 points)
  • Correct symbols; matches pseudocode and visually clear: ___/25
• Procedure Following and Documentation (x5, total 25 points)
  • Steps followed; documentation clear and sequence maintained: ___/25
• Total Score: 100/100

Quick Reference: Key Takeaways

• FIFO ensures the oldest enqueued item is dequeued first.
• PEEK reveals the current front without modification.
• Enqueue increases the queue size; Dequeue decreases it (when not empty).
• Step-by-step visualization helps validate correctness and teaches the flow of operations in a queue.
• A well-documented pseudocode and a corresponding flowchart provide a solid alternative representation of the same procedure.

Real-World Practice Tip

• When implementing a queue in code, consider using a circular buffer to efficiently utilize space and avoid shifting elements after each Dequeue.
• Always handle edge cases: empty queue on Dequeue or Peek, and potential overflow for bounded queues.