Lab 12 -- Queues

Answer Sheet

Exercise 1

Determine whether each of the following characteristics apply to a stack, a queue, both, or none.

A. An element is inserted at a special place called the top.

B. An element is inserted at a special place called the rear.

C. The structure can hold only one type of data element.

D. An element is deleted at the front.

E. The ith position may be deleted.

F. An element is deleted at the top.

G. The structure is a LIFO structure.

H. The structure is a FIFO structure.

I. The structure is a restricted access structure.

Exercise 2

Suppose q is an instance of the Queue class and assume that the previous array implementation is used. Also, assume that the size of the array is 5. Show q after all of the following operations have been completed assuming the queue is empty to start with. Show how the front, rear and elements change.


     q.enqueue(39);
     q.enqueue(22);
     item1 = q.dequeue();
     q.enqueue(59);
     item2 = q.dequeue();
     item3 = q.dequeue();

	Array Holding Queue		Information about Queue
0		front =
1		rear =
2		item 1 =
3		item 2 =
4		item 3 =

Exercise 3

Redraw the circular queue after all of the following operations have been completed:


     item = q.dequeue;
     q.enqueue(96);
     item = q.dequeue;

	Array Holding Queue		Information about Queue
0		front =
1		rear =
2		item 1 =
3		item 2 =

Exercise 4

Give the algorithm for dequeue.

Exercise 5

Suppose we are using a linked list implementation of the queue which was used in Exercise 3. After the statements in Exercise 3 are executed, draw the picture of the resulting queue using this pointer implementation.

front \|							rear \|
						...........		\

Exercise 6

{ Script }

Exercise 7

{ Script }

Exercise 8

Modify main12.cc to "generate 100 random real numbers ....." 25 times and calculate and print the average of the maximum size of the queue for the 25 times. If you were implementing the queue as an array, what size array would you feel comfortable using?

Turn in a script file showing the new code and a run.