Java - Static Queue Assignment

Objectives

• You will implement a static-sized queue using an array
• You will implement queue methods (enqueue/add, dequeue/remove, etc.)
• You will test your static queue in a main() method

Resources

• Queue slides (newer)
• Media:Queues.ppt (older)
• Data Structure Visualizations

Directions

• Create a StaticQueue project
  • Use StaticStack as a template -- you will need to create Queue.java and QueueMain.java

Queue Attributes

• Initialize them to appropriate default values
  • int head
  • int tail
  • int [] queue

Queue Constructors

• default constructor: Queue() - sets the queue array size to 5
• specific constructor: Queue(int size) - sets the queue array size to size

Queue Methods

• void enqueue(int data) - adds data to the tail of the queue if it is not full
  1. check if the queue is not full
     1. check if the queue is empty (in case you want to change head b/c you're adding to an empty queue)
        1. increment the head or set to 0 b/c you're adding the first item to an empty queue
     2. increment the tail
     3. put the data in the tail
• void add(int data) - adds data to the tail of the queue if it is not full
  1. make a method call to enqueue() -- DO NOT COPY AND PASTE enqueue() code
• int dequeue() - removes and returns data from the head of the queue if it is non-empty
  1. check if queue is not empty
     1. save the head into a new int variable named oldHead
     2. increment the head
     3. check if the head is beyond the tail now (because now the queue should be empty and you reset both head and tail
        1. reset both the head and tail to -1 b/c you should have an empty queue now
     4. return the data at the old head
  2. return an error value (Integer.MIN_VALUE) b/c you cannot dequeue from an empty queue
• int remove() - removes and returns data from the head of the queue if it is non-empty
  1. make a method call to dequeue() -- DO NOT COPY AND PASTE dequeue() code
• boolean isFull() - returns true if the queue is full (tail has hit the end of the array), false otherwise
• boolean isEmpty() - returns true if the queue is empty (head and tail are not valid indices), false otherwise
• int peek() - if the queue is not empty, then return data element at the head (but does not remove it), otherwise return Integer.MIN_VALUE
• void print() - prints out the queue from head to tail
• String toString() - returns the String representation of a queue

Testing Queue

• Test your queue class to see if it works (Hint: use the Stack main() as an example)
• Test to make sure special cases work:
  1. What happens to the head when you enqueue/add to an empty queue?
  2. What happens to the tail when you dequeue/remove the last item in the queue?

Circular Queue Challenge

1. What happens if you add and remove a whole bunch of times? i.g. What happens if the head and tail hit the end of the array?
2. Create a new class named CircularQueue
3. Copy and paste your static queue code
4. Add a new attribute named size to keep track of the number of added elements
5. Modify your the code in the rest of circular queue so that both head and tail are able to wrap around back to the beginning. You will need to use your size attribute in several methods (isFull(), print(), and toString())
6. Hint: Any method that changes the head and tail...check if either goes out of bounds...then force it to go back to 0 instead
7. Increase the size when you enqueue() and decrease size when you dequeue()