Undo Assignment

Overview

Stacks are often used to provide undo support in applications like a Web browser or text editor. While support for undo can be implemented with an unbounded stack, many applications provide only limited support for such an undo history, with a fixed-capacity stack. When push is invoked with the stack at full capacity, rather than throwing an exception, a more typical semantic is to accept the pushed element at the top while leaking the oldest element from the bottom of the stack to make room. In this assignment, you give an implementation of such a LeakyStack abstraction, using a circular array.

Design

1. You will write an array implementation for the LeakyStack class where the array is used as a circular array. Download the files Stack.java and LeakyStack.java for the framework for the LeakyStack class. You will write the code for all the methods except for the default constructor. For the methods top and pop, have them return null if the stack is empty rather than throwing an exception. You cannot add additional methods or any nested classes to the LeakyStack class. As needed, you can only add additional data members of datatype int to the LeakyStack class. You cannot add additional data members of any other datatype to the LeakyStack class.

The code you write for each method must have a worst-case runtime of O(1)! Hence, you will not need to shift values in the array.

The idea of a circular array is an array where we use it as if the back of the array wraps around to the front of the array. Normally, the first element of the array (element 0) has no predecessor and the last element of the array (element n-1) has no successor. In a circular array, the predecessor of element 0 is element n-1 and the successor of element n-1 is element 0. For example, the array called data below has 8 elements whose indices range from 0 to 7. 0	1	2	3	4	5	6	7
data:

2. The input to your program will read from a plain text file called assignment1.txt. This is the statement youll use to open the file:

FileInputStream fstream = new FileInputStream("assignment1.txt");

Assuming youre using Eclipse to create your project, youll store the input file assignment1.txt in the parent directory of your source code (.java files) which happens to be the main directory of your project in Eclipse. If youre using some other development environment, youll have to figure out where to store the input file.

The input consists of one or more commands (size, is_empty, push, pop, top) with each command on a separate line.

The size command has your program print the number of values in the LeakyStack.

For example: size

The isEmpty command has your program print the message The LeakyStack is empty or The LeakyStack is not empty.

For example: is_empty

The push command is the word push followed by a space followed by a string. The push command has your program push the string on top of the LeakyStack.

For example: insert http://www.qc.cuny.edu

The pop command has your program pop the string off the top of the LeakyStack and print the string. If the LeakyStack is empty then print the message The LeakyStack is empty.

For example: pop

The top command has your program get the string off the top of the LeakyStack and print the string. If the LeakyStack is empty then print the message The LeakyStack is empty.

For example: top

Have the output for each command print on a separate line.

3. Create a driver class and make the name of the driver class Assignment1 and it should only contain only one method:

public static void main(String args[]).

The main method will open the file assignment1.txt, create a LeakyStack object which stores strings, and have a loop to process each command in the file. The main method itself should be fairly short and will pass the command to another class to perform the command.

4. Tip: Make your program as modular as possible, not placing all your code in one .java file. You can create as many classes as you need in addition to the classes described above. Methods should be reasonably small following the guidance that "A function should do one thing, and do it well." A class to handle opening the input file and reading from it would be a good idea!

5. Do NOT use your own packages in your program. If you see the keyword package on the top line of any of your .java files then you created a package. Create every .java file in the src folder of your Eclipse project

6. Do NOT use any graphical user interface code in your program!

7. Document and comment your code thoroughly.