Lab 2

Queues, Stacks, and Arrays

Computer Science is all about learning tools and then being creative in how we apply them. One common tool is the Queue, in which data can only enter in one end, stay in order, and then exit out the other. This is the same as a line for the cashier; people enter the line in the back, stay in order, and then emerge from the line in the front. You didn't know it, but we have been using many queues. For example, the characters you type into the console enter a queue; they are then removed when you run .nextInt() or .next() or whatever you have chosen from the Scanner class. Notice that you can type as much as you want in the console, and therefore enter a large amount of data into the Queue; the data removed first, though, are still the data you entered first. For this reason, Queues are also called FIFOs, for First-In-First-Out. Queues are great to use whenever you have a lot of data streaming into a system, and you need to handle it in the order it arrived.

Stacks are the opposite of Queues. They allow access to only the newest data. Imagine you have an inbox and people keep giving you paperwork to complete. The newest papers get put on top of the pile, where you will see them before you get to the ones on the bottom. Assuming you do not re-order your inbox, you now need to complete the newest paperwork before getting to the oldest. This is a First-In-Last-Out (FILO) system.

Array are like neither Stacks for Queues. They provide "Random Access", which means that you can get to any piece of data at any time.

It is important to understand the strengths and weaknesses of these three data types. Each one is appropriate some functions and inappropriate for others.

Example code

Copy this file to your lab directory and compile it. It demonstrates both a Queue and a Stack in action. Follow the code to see how the data storage objects change as values are pushed or popped. Once you have a feel for how they work, we are going to build our our Queue object.

Lab Assignment

In this lab, we are going to implement a queue of Strings. Queues traditionally have three methods:

push() adds an element to the end of the queue (the last position)
pop() returns the first element in the queue and removes it from the queue
peek() returns the first element in the queue without removing it.

There are many ways we could implement a queue. We could, for instance, store our strings in an array; each time we pushed or popped our queue, we would have to move everything to a new array of the correct size. That we be expensive and awkward. We need to look for a data structure that is more appropriate for handling FIFO data streams.

Instead, it might have occurred to you that Linked Lists were perfect for this. push() is the same as add2back, and pop() is the same as removing from the front. We're going to need three files: Node.java, Queue.java, and Lab02.java. NOTE - you are not allowed to use Java's Queue, LinkedList, Array, or any other pre-defined storage class. You need to implement a Queue class on your own.

Our classes

Node.java will be the Java equivalent of our familiar C++ Node struct; it needs a pointer to the next Node, and a String containing that node's data.

Queue.java will be our Queue definition. Now, you might have noticed we're going to be running add2back quite a bit, which is actually pretty slow with a standard linked list. However, if we keep a pointer not only to the FIRST node in the list, but also the LAST, then this is very fast as well. So, our Queue is going to consist of these two pointers.

Finally, we have Lab02.java, which consists of the four functions push(Queue q, String s), pop(Queue q), peek(Queue q), and main.

The assignment

Here are the program Requirements:

The main program must be named Lab02.java. You must have two importable class files named Queue.java and Node.java.
You initialize the Queue by passing the program a string on the command-line. The program splits the string into individual words, and each word becomes an element in the Queue. e.g. java Lab02 "This is a test"
Your program must give the user a prompt to enter data. The prompt is a token in the terminal that indicates that the program is expecting you to type something. Use the Greater-Than sign '>' the same as in the example below.
The user should be able to issue three commands to the program: '!pop', '!peek', and '!quit'. Notice the the exclamation point indicates these are commands and not just regular words.
'!pop' should remove the first item from the queue and print it to the screen.
'!peek' should print the first item to the screen but not remove it from the queue.
'!quit' should exit the program gracefully.
Any text other than the above three commands should be split into separate words and pushed onto the end of the queue. Note that you should be able to push the words 'pop', 'push', and 'quit' onto the queue as long as they are not preceded by an exclamation point.
An example run is shown below. Your code should match this functionality:

  taylor@albert:~/ic211Class/Lab02$ java Lab02 Computer Science is a science of abstraction 
  -creating the right model for a problem and devising the appropriate mechanizable techniques 
  to solve it. 
  >!pop
  Computer
  >!pop
  Science
  >!peek
  is
  >!peek
  is
  >!pop
  is
  >!pop
  a
  >add these words to the queue
  >!pop
  science
  >!quit
  taylor@albert:~/ic211Class/Lab02$

What to hand in

You need to hand in the three files that you created:

Lab02.java
Queue.java
Node.java

A helpful note about Strings and equality

For this Lab, you will likely want to check the equality of two Strings. For example, you might be curious if the user entered string userString is the same as the string !quit. Unlike in C++, using the == operator WILL NOT ALWAYS WORK.

The reason is that the == operator, when applied to two objects (such as Strings), checks to see if the two variables are pointing at the same object, NOT to see if they contain the same information. Instead, you want to use the .equals() method. An example:

  String s1 = new String("hello");
  String s2 = new String("hello");
  System.out.println(s1==s2); //Outputs false!

  s2=s1;
  System.out.println(s1==s2); //Outputs true!

  String s3 = new String("hello");
  System.out.println( s1.equals(s3) ); //Outputs true!