Stack

Queue

1. Find your Num class from the queues day. It has the following methods and instance variables.

Num

Instance Variables

int n

Methods

public Num (int s)
public Num ()
public int getNum ()
public void setNum (int s)
public boolean equals (Num s)
public int compareTo (Num s)
public String toString()

2. Make another file. Paste this into it. Save it to the same folder as Num.

public class queue
{
private int count;
Num data[] = new Num [50];

public class Queue
{
private Num data[] = new Num [50];
int count;
int head;

public Queue ()
{
count = 0;
head = 0;

}

public void enqueue (int value)
{ //Post: item is added to queue
int tail = (head + count) % data.length;
data [tail] = new Num (value);
count++;
}

public void enqueue (Num value)
{ //Post: item is added to queue
int tail = (head + count) % data.length;
data [tail] = value;
count++;
}

public Num dequeue ()
{ //Pre: queue is not empty
//Post: first enqueue item is removed and returned
Num temp = data [head];
count--;
head = (head + 1) % data.length;
return temp;
}

public Num peek ()
{ //Pre: queue is not empty
//Post: the top value (next to be removed) is returned
return data [head];
}

public int size ()
{ //Post: returns the number of elements in the queue
return count;
}

public boolean isFull ()
{ //Post: returns true iff the queue is full
return (count == 50);
}

public boolean isEmpty ()
{ //Post: returns true iff the queue is empty
return (count == 0);
}

public boolean empty ()
{ //Post: returns true iff the queue is empty
return isEmpty ();
}

public void clear ()
{ //Post: removes all elements from queue
while (!isEmpty ())
dequeue ();
}

public String toString ()
{ //Post: the contents of the queue are displayed.
//First element is first on the left.
int size = count;
String hold = "";
for (int i = 0 ; i < size ; i++)
{
Num temp = dequeue ();
hold += temp + " ";
enqueue (temp);
}
return hold;
}
}

3. Make a third file. Paste this into it. Save it to the same space as the first two.

public class QueueRun
{
public static void main (String args[])
{
new QueueRun ();
}

public QueueRun ()
{
Queue q = new Queue ();
q.enqueue (1);
q.enqueue (2);
q.enqueue (3);
System.out.println (q.dequeue ());
System.out.println (q.dequeue ());
System.out.println (q.dequeue ());
}
}

4. (Answer on paper) a. What was the order things were "enqueued" onto the queue?
b. What was the order things were "dequeued" off the queue?
c. How do these compare?

Pronunciation Guide: Queue is pronounced "Q" or "cue". Dequeue is de-Q, enqueue is en-Q. A queue is an old fashioned word for a line where you wait for something. It is still used commonly in England where you "queue for the bus" or "queue for the cashier".

5.. This code has both a queue and a stack.

a. What is the queue's output? What is the stack's?
b. How does enqueue compare to push?
c. How does dequeue compare to pop?
d. How are a stack and queue different?

public class QueueRun
{
public static void main (String args[])
{
new QueueRun ();
}

public QueueRun ()
{
Queue q = new Queue ();
q.enqueue (1);
q.enqueue (2);
q.enqueue (3);
System.out.println (q.dequeue ());
System.out.println (q.dequeue ());
System.out.println (q.dequeue ());
System.out.println ();
Stack s = new Stack ();
s.push (1);
s.push (2);
s.push (3);
System.out.println (s.pop ());
System.out.println (s.pop ());
System.out.println (s.pop ());
}
}

6. What is the output of each of the following? Explain why the output of the following two programs is the same - that didn't happen with Stacks.

public class QueueRun
{
public static void main (String args[])
{
new QueueRun ();
}

public QueueRun ()
{
Queue q = new Queue ();
q.enqueue (1);
q.enqueue (2);
System.out.println (q.dequeue ());
q.enqueue (3);
System.out.println (q.dequeue ());
q.enqueue (4);
System.out.println (q.dequeue ());
System.out.println (q.dequeue ());
}
}

public class QueueRun
{
public static void main (String args[])
{
new QueueRun ();
}

public QueueRun ()
{
Queue q = new Queue ();
q.enqueue (1);
System.out.println (q.dequeue ());
q.enqueue (2);
q.enqueue (3);
System.out.println (q.dequeue ());
System.out.println (q.dequeue ());
q.enqueue (4);
System.out.println (q.dequeue ());
}
}

7. Write the code to declare a queue and add 3, 4, 5 to it. Remove off 3.

8. A mental representation of a queue is a line waiting for a cashier. What is a 'enqueue' operation with a line? What is a 'dequeue' operation on a line of people?

9. What method in the queue class would be used to do the following:

a. print out the size
b. find out the top element
c. see if it is full
d. see if it is empty

10. A queue is called a FIFO (first in, first out) structure. Why is that?

11. Queues are used to code many things on computers. Explain why a queue is used to store the jobs for a printer in a lab with many networked computers.

12. Why don't these operations exist in the queue class?

a. print out the middle element
b. sort it.
c. print out the 6th element

13. Over time, 1, 2, and 3 are enqueued onto a queue in that order. If you vary the times you dequeue, is it possible to print out each of the following?

123, 231, 213, 132, 321, 312

Can you get the others? Prove it.