OO Programming and Data Structures | CS 241

06 Prove : Homework - Data Structures

Queues

Outcomes

At the end of this study, successful students will be able to:

  1. Articulate the strengths and weaknesses of Queues.

  2. Use Queues in Python to solve problems.

Preparation Material

Please read the following:

Using Queues in Python

Python has some built-in classes for queues that are designed for more complex scenarios such as when multiple processes are trying to access the queue at the same time (see: Python Documentation: Queues).

For simple queues, however it is recommended to use the Deque class, that we also used for linked lists. (It is a double-ended queue, built as a doubly-linked list.)

To use a Deque object, you simply call the .append() method to add an item to the back of the queue, and the .popleft() method to remove and return the first item from the front of the queue.

Homework Assignment

Use a queue (i.e., a Python Deque) to keep track of students that are requesting help from a TA. When a student asks for help, they are placed in the back of the queue. When a TA is available to help, the person at the front of the queue is removed from the queue and helped.

Instructions

Follow these steps to guide you through the process:

  1. Create a Student class with the following properties:

    Student
    name : string
    course : string
    __init__()
    prompt()
    display()

  2. Create a HelpSystem class with the following properties:

    HelpSystem
    waiting_list : deque
    __init__()
    is_student_waiting() : boolean
    add_to_waiting_list(Student)
    help_next_student()

    The is_student_waiting() method should return True if there are currently students in the waiting_list, and false if not.

    The add_to_waiting_list(Student) method should return receive a Student as a parameter and add them to the waiting list.

    The help_next_student() method should first check if there is a student waiting (i.e., call the method for this), and if not, display "No one to help". If there is a student waiting then it should remove them from the waiting_list and display, "Now helping John with CS 241" assuming that John is the name of the student, and CS 241 is the course.

  3. Create a main function that gives the user the option to add a new student, or to have a student be helped. It begins by creating a HelpSystem object, and then calls the appropriate methods on it (including creating a student to pass to the method as necessary).

  4. Test your program with various scenarios to ensure that it works. Make sure to include boundary conditions, such as not having any students.

  5. You must use a deque for this assignment. Do not simply use a list. (It would have O(1) insertion time, but O(n) removal time!)

Sample Output


Options:
1. Add a new student
2. Help next student
3. Quit
Enter selection: 2

No one to help.

Options:
1. Add a new student
2. Help next student
3. Quit
Enter selection: 1

Enter name: John
Enter course: CS 241

Options:
1. Add a new student
2. Help next student
3. Quit
Enter selection: 1

Enter name: Emily
Enter course: CS 345

Options:
1. Add a new student
2. Help next student
3. Quit
Enter selection: 2

Now helping John with CS 241

Options:
1. Add a new student
2. Help next student
3. Quit
Enter selection: 2

Now helping Emily with CS 345

Options:
1. Add a new student
2. Help next student
3. Quit
Enter selection: 2

No one to help.

Options:
1. Add a new student
2. Help next student
3. Quit
Enter selection: 3

Goodbye

TestBed

To keep your focus squarely on the queue functions, and not on the formatting constraints, an auto-grading testBed script is not provided for this assignment. Please test it thoroughly yourself and then answer the questions in the quiz.

Submission

You are encouraged to work with others on the programming and the quiz.

When you have a good understanding of this data structure and have completed the programming project, take the accompanying I-Learn Quiz. It has questions about how the data structure works, and also, has places for your to report on the parts of the programming assignment that you completed.