CIS-610 Data Structures and Algorithms

Home Work #4						Due:	10/14/1999


1. What set of conditions is necessary and sufficient for a sequence of insert and remove operations on a single
empty queue to leave the queue empty without causing underflow? What set of conditions is necessary and sufficient
for such a sequence to leave a nonempty queue unchanged.

2. How you would implement a queue of stacks? A stack of queue?. Write routines to implement the appropriate
operations for each of these data structure.
 

3. Show how to implement a queue of integers by using an array queue[100], where queue[0] is used to indicate the
front of the queue, queue[1] is used to indicate its rear, and queue[2] through queue[99] are used to contain the
queue elements. Show how to initialize such an array to represent an empty queue and write routines remove, insert,
and empty for such an implementation.

4.  Write an algorithm to perform each of the following operations:

a. Concatenate two lists
b. Reverse a list so that the last element becomes the first, and so on.
c. Delete the nth element from a list.
d. Insert an element after the nth element of a list.

5. Write an algorithm for pqinsert and pqmindelete for an ascending priority queue implemented as an unordered list
and as an ordered list.

6. Write an algorithm to perform each of the following operations, assuming that each list contains a header node
containing the number of elements in the list:

a. Append an element at the end of the list.
b. Delete every other element in the list.
c. Combine two ordered lists into a single ordered list.
d. Insert an element after the nth element of a list.