Tutorial 9, CPSC 331, Winter 2017

home page -  news -  syllabus -  schedule -  assignments -  tutorials -  java -  references -  Mike Jacobson

Tutorial 1 -  Tutorial 2 -  Tutorial 3 -  Tutorial 4 -  Tutorial 5 -  Tutorial 6 -  Tutorial 7 -  Tutorial 8 -  Tutorial 9 -  Tutorial 10 -  Tutorial 11 -  Tutorial 12 -  Tutorial 13 -  Tutorial 14 -  Tutorial 15 -  Tutorial 16 -  Tutorial 17 -  Tutorial 18 -  Tutorial 19 -  Tutorial 20 -  Tutorial 21 -  Tutorial 22 -  Tutorial 23 -  Tutorial 24

 Queues

About This Exercise

This exercise can be used by students to make sure that they are familiar with the properties, implementations, and applications of queues that have been discussed in class. Students should read through and try to solve the problems on this exercise before attending the tutorial.

Expected Background

It is assumed that students have attended the lecture in which queues were discussed and carefully reviewed the online lecture notes that are available.

The material on queues in Chapter 10 of Introduction to Algorithms is also recommended.

Warmup Exercises — To Check That You Understand the Basics

It is to be expected that all of the questions in this first section can be answered by any student who has successfully completed the prerequisites for this course, attended the lecture in which queues were discussed, and read through the material about this that is listed above.

Teaching assistants will not be spending very much time in tutorials discussing these questions! Students should look at them anyway to make sure that they know how to answer them.

Students who do have difficulty with these questions, after completing the suggested reading, should contact the course instructor to get extra help.

  1. Give a brief description of a (simple) queue. What operations does this abstract data type support?

  2. While the applications of stacks tend to be somewhat specialized, queues are more generally useful, especially for applications in simulation, How (or why) is that the case?

  3. Consider the following queue.

    A Simple Queue

    This can be implemented as a “circular queue” (with an array of length 8) as follows.

    Implementation as Circular Queue

    1. Draw the queues (using both types of pictures that are shown, above) that would result if you performed the following sequence of operations on the above queue.

      1. add(‘e’)
      2. remove()
      3. remove()
      4. add(‘f’)
      5. add(‘g’)
      6. remove()
      7. remove()

      Make sure to include the values of “front,” “rear,”and “size” in each case.

    2. Draw the linked-list implementation of each of the above queues as well.

To Be Discussed in Tutorial

  1. As noted in class, a time- and space-efficient implementation of a bounded queue is a circular queue.

    1. Describe the organization of the queue’s contents within the underlying static array when a circular queue is implemented, noting the following information:

      • possible locations of the front element of the queue,
      • the location of the element that is immediately behind the front element, if the front element is in position i,
      • the location of the element at the rear of the queue if the front element is in position i, the queue has capacity N, and the current size of the queue is n.

    2. Give pseudocode for each queue operation when it is being implemented as a circular queue. Your pseudocode should be detailed enough to be clear that the queue is being implemented as a circular queue, rather than in some other way.

  2. Consider each of the following other ways to implement a bounded queue (with capacity N) using an array of length N. Explain why each implementation is less useful than the “circular queue” described in lectures, even though it is simpler in one way or another.

    1. Make sure that the elements of the queue are always stored at the beginning of the array: If the queue currently includes n elements (where n ≤ N) then these should be stored in positions 0, 1, …, n−1 of the array.

    2. Allow the queue to be used just like it is as described in lectures, except that we cannot wrap around: An attempt to enqueue an element should cause an exception to be thrown, and the queue to be unchanged, if “rear” has value N−1.

  3. Using the above, describe an implementation of an unbounded queue using a static array such that the amortized cost of any sequence of queue operations (beginning with an empty queue) is in Θ(1) in the worst case.

  4. Finally, give pseudocode for the additional methods that must be provided if you extended the implementation of a bounded queue, with a circular queue, in order to provide an implementation of a bounded deque, instead.

Last updated:
http://www.cpsc.ucalgary.ca/~jacobs/Courses/cpsc331/W17/tutorials/tutorial9.html