Page 100 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Unit 4: Queues

4. A more efficient queue representation is obtained by regarding the array of elements of a Notes

queue to be ..............................
5. A queue could be implemented using a .................................
6. Reverse Polish Notation is also called ................................
7. ................................ is used in time-sharing multi-user systems where programs of high

priority are processed first amid programs with the same priority form a standard queue.
8. A queue exhibits the ............................... property.
9. A queue could be implemented using ...................... and ...........................

10. A ............................. is a collection of elements such that each element has been assigned a
priority.

4.7 Review Questions

1. Write a segment of code to create a copy of a given queue. Let q1 be the given queue and q2
be the copy. All the elements of q2 must be equal to q1. Do not assume any implementation
of a queue.
2. Describe the application of queue.
3. How will you insert and delete an element in queue?

4. Write a C program to implement a double-ended queue, which is a queue in which
insertions and deletions may be performed at either end. Use a linked representation.
5. Write the following methods for linked queues:

(a) The method empty,
(b) The method retrieve,
(c) The destructor,
(d) The copy constructor,

(e) The overloaded assignment operator.

6. Assemble specification and method files, called queue.h and queue.c, for linked queues,

suitable for use by an application program.
7. For a linked Extended_queue, the function size requires a loop that moves through the
entire queue to count the entries, since the number of entries in the queue is not kept as a
separate member in the class. Consider modifying the declaration of a linked Extended_
queue to add a count data member to the class. What changes will need to be made to all the
other methods of the class? Discuss the advantages and disadvantages of this modifi cation
compared to the original implementation.
8. Write an implementation of the Extended_queue method full. In light of the simplicity
of this method in the linked implementation, why is it still important to include it in the
linked class Extended_queue?

9. Give a formal definition of the term deque, using the definitions given for stack and queue

as models. Recall that entries may be added to or deleted from either end of a deque, but
nowhere except at its ends.
10. Give two reasons why dynamic memory allocation is valuable.

LOVELY PROFESSIONAL UNIVERSITY 95