thet

//The stack we discussed last week is a LIFO data structure

THIS GIVEN CLASS IS CALLED OurQueue //Last In First Out //It is also the simplest possible data structure //It maintains a top, and can interact with that top

//The queue is a FIFO data structure //First In First Out //This is only slightly more complex than the stack //Instead of a top, we need to know top and bottom //We call these the head and tail of the queue //The head is the first element in, and therefore the first to go out //The tail is the last element in

//Like with OurStack, we follow the name of the interface/class with //Note, it doesn't actually have to be E, that is just what we normally use //We usually use either E for element or T for type //Sometimes K for key or V for value //These are called Generics //It is a parameterizable type - which basically means that we can make //a queue of Integers, Characters, Strings, Stacks, etc. public interface OurQueue {

/** * Returns true if the queue is empty * @return true if empty, false otherwise */ public boolean isEmpty(); /** * Returns (without removing) the element at the head of the queue * @return element at head of the queue */ public E peek(); /** * Removes and returns the element at the head of the queue * Remove is sometimes called dequeue * @return element at head of the queue */ public E remove(); /** * Add the given element to the end of the queue (after the current tail - it becomes the new tail). * Add is sometimes called enqueue * @param element element to add */ public void add(E element); /** * Returns the size of the queue * @return the size of the queue */ public int size(); }

LinkedQueue You will implement the Queue interface by writing a new class called LinkedQueue. This class will build the queue using Node objects that are linked together. There will be no array in this class. Use the LinkedStack as a model. With the LinkedStack, we had a top variable that identified the top Node in the stack. With a LinkedQueue, you will have two such variables: head identifies the first Node in the queue tail identifies the last Node in the queue head tail You always add to the tail and remove from the head. Complete the LinkedQueue class by doing the following: 1) Add the inner class Node that is exactly like the Node class in LinkedStack. 2) Add two fields for head and tail. These are like top in LinkedStack. 3) You do not need a constructor method, but you can add one that sets both head and tail to null. 4) Complete the remove method. This is similar to the pop method in LinkedStack. Here's a special case: if the queue is empty after removing the element, you must set tail to null. 5) Complete the add method. This is not quite the same as the push method in LinkedStack because you're adding to the end of the queue, not the beginning. Look at the diagram of the queue above to figure out what you need to do here. Here's a special case: If the queue is empty, you need to set both head and tail to the new Node. 6) Complete the peek, size, and isEmpty methods. 7) Test the LinkedQueue class by writing a main method to make sure you can add and remove elements successfully