CompSci Notes Mar 30

Class Arrangement

• No class reminder for Friday, only two days of class this week.

Previous Topics Discussed

• Stack applications:

  • Infix notation and its conversion to postfix and prefix notation.

  • Evaluating postfix expressions.

  • Practical application in the upcoming lab involving a calculator using infix to postfix conversion.

  • Example: Input: "2 + 3 * 5"

• Calculator GUI will allow user to type infix expressions and convert to postfix.

Introduction to Queues

• Definition:

  • A queue is a data structure known as a First In, First Out (FIFO) data structure.

  • Items can be inserted at one end (the rear) and removed from the other end (the front).

• Real-world examples:

  • Lining up for food or buying tickets.

• Queue operations:

  • Enqueue: Adding an item to the rear of the queue.

  • Dequeue: Removing an item from the front of the queue.

  • Other operations include:

  • isEmpty(): Returns true if the queue is empty, false otherwise.

  • peek(): Allows you to look at the front item without removing it.

  • size(): Returns the number of items in the queue.

Queue Implementation in Java

• Java does not have a built-in queue class; there is a Queue interface implemented by various classes.

• LinkedList can be used to implement a queue.

  • Example:
    Queue<Integer> queue = new LinkedList<>();

• Importance of implementing methods such as peek(), remove(), and add() for managing queue elements.

Stack vs. Queue

• Stacks operate on a Last In, First Out (LIFO) basis, meaning the last element added is the first to be removed.

• Example of method to reverse queues using a stack:

  • A method removes elements from a queue and pushes them onto a stack, then pops them back to the queue, effectively reversing the order.

  • Public Stack mystery(Queue q):

  • The method creates a stack, pushes all queue elements onto it, and then re-adds them to the queue in reversed order.

Example Analysis of Code Output

• Code involves:

  • Using a queue and handling user input with booleans.

  • Depending on the boolean input, the code either prints the index or enqueues it for later retrieval.

• Sample input: true, false, false, true, true yields output 1, 4, 5, 2, 3.

• Analyzing possible outputs:

  • Can we achieve 13542?

  • Impossible due to the order of enqueue operations.

  • To achieve 12345?

  • Requires either all true or all false inputs:

    • All trues: Print each number on input.

    • All falses: Queue each number and print at the end.

Sort Algorithm Introduction

• Basic introduction and importance of sorting algorithms, specifically Radix Sort.

• Radix Sort leverages the concept of queues, allowing for a structured approach to sorting.

• Particularly effective for fixed-width data such as:

  • Telephone numbers (10 digits).

  • ZIP codes (5 or 8 digits).

  • Product IDs.

How Radix Sort Works

• Radix Sort processes numbers by their digits, implementing a queue for each digit's place value (like buckets).

• Each number is sorted based on the least significant digit to the most significant digit:

  • Example Process:

  • Initialization of an array of queues (buckets).

  • Distributing numbers into buckets based on current digit being examined.

  • Emptying the buckets and reassembling the queue for the next digit.

• Illustration:

  • Given numbers like 841, 420, 144, etc., they are distributed into buckets based on their lowest digit, combined, and then redistributed based on the next digit, and so forth until the list is sorted.

Detailed Example of Radix Sort Processing Steps

Initialization

• Start with a queue containing numbers, arrays of queues are initialized for digits (0-9).

Stepwise Processing

1. Read initial queue (e.g., 840, 201, 441...).

2. Empty the queue into buckets based on the least significant digit.

3. Reassemble the queue from the buckets.

4. Repeat the process for the next significant digit until all digits are processed.

Final Notes

• Sorting strings or any data of a known character set also utilizes the same bucket strategy.

• Key points for buckets and indexing with characters:

  • Buckets are indexed based on the characters' ASCII or Unicode values.

  • E-commerce or other data contexts may have varying digit lengths but are consistent in character set.

• Challenges and considerations:

  • The algorithm is efficient for data of fixed length but less practical for data with high variability in lengths.

• Note about syntax in Java: Generic types in Java can lead to compile-time errors when creating arrays of generics, thus utilizing a linked list is emphasized for queues.

Conclusion

• Completed lesson on queues and radix sort. Reminder to turn in assignments when due. Next class on Wednesday.