CSC236 Data Structures - Problem Set: Queues

Problem Set: Queues

Show what is contained in the queue qq (draw the queue, showing the order of items from front to back) and the value of ch1 and ch2, or a and b, after the completion of each of the following operations:


a. ArrayUnboundedQueue<Character> qq = new ArrayUnboundedQueue<Character>();
   qq.enqueue('a');
   qq.enqueue('b');
   ch1 = qq.dequeue();
   qq.enqueue('b');
   qq.enqueue('f');
   qq.enqueue('z');
   ch2 = qq.dequeue();
   qq.enqueue(ch2);
   ch2 = qq.dequeue();


b. QueueInterface<Integer> qq = new LinkedQueue<Integer>();
   qq.enqueue(4);
   qq.enqueue(8);
   qq.enqueue(2);
   a = qq.dequeue();
   b = qq.dequeue();
   qq.enqueue(a+b);
   qq.enqueue(a*b);
   a = qq.dequeue();
   qq.enqueue(a+b);

Show what is written by the following segments of code:


a. LinkedQueue<Integer> qq = new LinkedQueue<Integer>();
   qq.enqueue(5);
   qq.enqueue(6);
   qq.enqueue(7);
   qq.enqueue(8);
   x = qq.dequeue();
   y = qq.dequeue();
   qq.enqueue(x);
   qq.enqueue(y+1);
   x = qq.dequeue();
   qq.enqueue(y);
   while (!qq.isEmpty()) {
      x = qq.dequeue();
      System.out.println(x);
   }


b. ArrayUnboundedQueue<Integer> qq = new ArrayUnboundedQueue<Integer>();
   x = 2;
   qq.enqueue(4);
   qq.enqueue(x);
   y = qq.dequeue();
   qq.enqueue(y+3);
   qq.enqueue(0);
   z = qq.dequeue();
   x = y + z;
   qq.enqueue(x);
   qq.enqueue(x-1);
   qq.enqueue(x);
   while (!qq.isEmpty()) {
      x = qq.dequeue();
      System.out.println(x);
   }


c. QueueInterface<Integer> qq = new ArrayUnboundedQueue<Integer>();
   x = 5;
   y = 7;
   qq.enqueue(x);
   qq.enqueue(5);
   qq.enqueue(y);
   y = qq.dequeue();
   qq.enqueue(2);
   qq.enqueue(x);
   qq.enqueue(y);
   z = x - y;
   if (z == 0)
      while (!qq.isEmpty()) {
         x = qq.dequeue();
         System.out.println(x);
      }
   else
      System.out.println("the end");


d. ArrayUnboundedQueue<Integer> qq = new ArrayUnboundedQueue<Integer>();
   qq.enqueue(5);
   qq.enqueue(6);
   qq.enqueue(10);
   a = qq.dequeue();
   b = qq.dequeue();
   qq.enqueue(a+2);
   qq.enqueue(a-b);
   qq.enqueue(b+a);
   qq.enqueue(a*b);
   while (!qq.isEmpty()) {
      c = qq.dequeue();
      System.out.println(a + " " + b + " " + c);
   }

Show what is on the ArrayUnboundedQueue qq initially (draw the queue, showing the order of items from front to back), and then show the contents of front, back, count, and the array after each of the following operations. Show the contents of value for any remove operations, and indicate if there is an attempt to add to a full queue or remove from an empty queue. For each problem, start with the queue shown (not the result of the previous problem.)


    [0] [1] [2] [3] [4]
a.   A   B   C   D   E       front = 1     back = 4     numElements = 4
                             qq.enqueue('F'));

    [0] [1] [2] [3] [4]
b.   A   B   C   D   E       front = 2     back = 0     numElements = 4
                             value = qq.dequeue();

    [0] [1] [2] [3] [4]
c.   A   B   C   D   E       front = 4     back = 3     numElements = 5
                             qq.enqueue('G'));

    [0] [1] [2] [3] [4]
d.   A   B   C   D   E       front = 2     back = 1     numElements = 0
                             value = qq.dequeue();

    [0] [1] [2] [3] [4]
e.   A   B   C   D   E       front = 3     back = 0     numElements = 3
                             qq.enqueue('H'));

    [0] [1] [2] [3] [4]
f.   A   B   C   D   E       front = 1     back = 3     numElements = 3
                             value = qq.dequeue();

Write a client function to copy qq1 to qq2 and leave qq1 unchanged.
Write a method of the LinkedQueue class to return a queue which is a copy of the invoking object (this). Do not use other methods of the queue class in your code.
Write a method of the ArrayUnboundedQueue class to return a queue which is a copy of the invoking object (this). Do not use other methods of the queue class in your code.
Write a client function to count and return the number of integers in a queue which are less than zero. When your function is finished the queue should be unchanged.

Explain what the following code does to qq, which is an ArrayUnboundedQueue<Integer>:


     ArrayStack<Integer> st = new ArrayStack<Integer>();
     while (!qq.isEmpty()) {
        value = qq.dequeue();
        st.push(value);
     }
     while (!st.isEmpty()) {
        value = st.top();
        st.pop();
        qq.enqueue(value);
     }

Assume you have two queues qq1 and qq2. Write a client function called match that will count and return the number of elements in the same position of the two queues which are equal. The queues may not be the same length. When your function is finished the queues should be unchanged.
Sometimes it is useful to have additional methods in the Queue class. For example, users may want to remove all items from a Queue. Write a method for the ArrayUnboundedQueue class which will remove all items from the Queue. The method should throw QueueUnderflowException if the Queue is already empty. Do not use other methods of the queue class in your code.
```
public void removeAll()
```
Write the function described in the previous problem for the LinkedQueue. Do not use other methods of the queue class in your code.
Sometimes it is useful to have additional methods in the Queue class. For example, users may need to remove an item that is not at the front of the Queue, such as when a user wants to cancel a print job which is waiting in a print queue. Write a method for the ArrayUnboundedQueue class which will remove the item passed as a parm from the Queue. The method should throw NoSuchElementException if the element is not found in the Queue. Do not use other methods of the queue class in your code.
```
public void removeItem(T item)
```
Write the function described in the previous problem for the LinkedQueue class. Do not use other methods of the queue class in your code.