Chapter Exercises

Exercises

E 1.

Determine the worst case time-complexity for each operation defined in the TicketCounterSimulation class.

E 2.

Hand execute the following code and show the contents of the resulting queue:

  values = Queue()

  for i in range(16) :

    if i % 3 == 0 :

      values.enqueue(i)

E 3.

Hand execute the following code and show the contents of the resulting queue:

  values = Queue()

  for i in range(16) :

    if i % 3 == 0 :

      values.enqueue(i)

    elif i % 4 == 0 :

      values.dequeue()

E 4.

Implement the remaining methods of the TicketCounterSimulation class.

E 5.

Modify the TicketCounterSimulation class to use seconds for the time units instead of minutes. Run an experiment with multiple simulations and produce a table like Table 8.8.1.

E 6.

Design and implement a function that reverses the order of the items in a queue. Your solution may only use the operations defined by the Queue ADT, but you are free to use other data structures if necessary.

Programming Projects

P 1.

Implement the Priority Queue ADT using each of the following:

sorted Python list
sorted linked list
unsorted linked list

P 2.

A deque (pronounced "deck") is similar to a queue, except that elements can be enqueued at either end and dequeued from either end. Define a Deque ADT and then provide an implementation for your definition.

P 3.

Design and implement a ToDo List ADT in which each entry can be assigned a priority and the entries with the highest priority are performed first.

P 4.

Printers can be connected to the network and made available to many users. To manage multiple print jobs and to provide fair access, networked printers use print queues. Design, implement, and test a computer program to simulate a print queue that evaluates the average wait time.

P 5.

Modify your simulation from the previous question to use a priority queue for each print job. The priorities should range from 0 to 20 with 0 being the highest priority. Use a random number generator to determine the priority of each job.

P 6.

Design, implement, and test a computer program to simulate a telephone customer service center. Your simulation should evaluate the average time customers have to wait on hold.

P 7.

Design, implement, and test a computer program to simulate a bank. Your simulation should evaluate the average time customers have to wait in line before they are served by a teller.

P 8.

Redesign the TicketCounterClass to implement a generic simulation class from which a user can derive their own simulation classes.

P 9.

Design, implement, and test a computer program to simulate the checkout at a grocery store. Your simulation must allow for multiple checkout lines and allow customers at the end of a line to move to another checkout line. This simulation differs from the one described in the chapter. For this simulation, you will have to accommodate the multiple checkout lines, decide how a customer chooses a line, and decide if and when a customer moves to a new checkout line.

8.8 Simulation Implementation

Chapter 8. Queues