COSC 311 WINTER 2013 HW#2 (Distributed 1/24, Due 1/31/2013)

1. Assume a circular queue, implemented using 'keep one slot empty'.
Queue is size 4.
Insert the following: a, b, c, d.
The insert(d) will fail because of full queue.

What are the values of head and tail before the attempt to insert(d)?


2, Assume a circular queue, implemented using head and count (no tail).
Queue is size 4.
Insert: a, b, c, d, e.
The insert(e) will fail because of full queue.

What are the values of head and count before the attempt to insert(e)?


3. Assume a circular queue, implemented using mirroring (using head, tail, hb, ht;
hb is a boolean operator to indicate even or odd # of wraparounds on delete,
ht is a boolean operator to indicate even or odd # of wraparounds on insert)
Queue is size 4.
Insert: a, b, c, d, e
The insert(e) will fail because of full queue.

Assume values are initialized as follows:
head = 0; tail = 0; hb = false; tb = false;
What are the values of head, tail, hb and tb before the attempt to insert(e)?

4. Using the circular queue data structure described in (1).
Starting from a freshly initialized queue, do the following:
insert(a); insert(b); insert(c); 
delete(); delete(); delete();               // the queue is now empty
insert(d); insert(e); insert(f); insert(g);

The insert(g) will fail because of full queue.
What are the values of head and tail before the attempt to insert(g)?

5. Using the circular queue data structure described in (2).
Starting from a freshly initialized queue, do the following:
 
insert(a); insert(b); insert(c); insert(d);
delete(); delete(); delete(); delete();              // the queue is now empty
insert(e); insert(f); insert(g); insert(h); insert(i)

The insert(i) will fail because of full queue.
What are the values of head and count before the attempt to insert(i)?


6. Using the circular queue data structure described in (3).
Starting from a freshly initialized queue, do the following:

insert(a); insert(b); insert(c); insert(d);
delete(); delete(); delete(); delete();              // the queue is now empty
insert(e); insert(f); insert(g); insert(h); insert(i)

The insert(i) will fail because of full queue.
What are the values of head, tail, hb and ht before the attempt to insert(i)?



7. Suppose you have a double-ended queue, implemented as a doubly-linked list, with the
data as shown:

head                        tail
 |                           |
 \/                          \/
  a        b        c        d
  ---->    ---->    ---->    null
  null    <----    <----    <---- 
            ^
            |
            p                  q --> b1
                                   null
                                   null

Give code to insert the new node (q) between p and p.next (i.e., datum b1 goes between data b and c)
without using any other variables other than head, tail, p, q, and the list itself.