Deque Using Stacks

Overview

In class, you learned how to implement a deque using a linked list or an array. You can also use stacks to implement a deque which is what you will do in this assignment. It may be easier to start by implementing a queue using stacks since there are only two methods which inserts or removes a value from the queue rather than the four methods which inserts or removes a value from the deque.

You could use just one stack to implement a queue. Remember, inserting a value into a stack puts the value at the top of the stack. If you enqueue (insert) each value into the queue implemented using a single stack then the front of the queue is at the bottom of the stack and the back of the queue is at the top of the stack. To dequeue (remove) a value from the queue requires gaining access to the value at the front of the queue which is at the bottom of the stack. Therefore, a second stack can help in the coding of the queue using stacks implementation.

The code you write for the methods of the queue class do not have to be long or complex. The methods should not move the values from one stack to the other any more than is absolutely necessary. You can use an example on paper to see and compare the values of the queue in the stacks in relation to how those same values appear in the abstract view of the queue.

Download the files Queue.java and QueueUsingStacks.java for the framework for the QueueUsingStacks class. Youre only using this class to help in coding the DequeUsingStacks class as described on the next page. Remember, the size, isEmpty, and first methods of the queue are the exact same methods in the deque. The enqueue method of the queue is the addLast method of the deque. The dequeue method of the queue is the removeFirst method of the deque.

Design

1. You will write the implementation for the DequeUsingStacks class. Download the files Deque.java and DequeUsingStacks.java for the framework for the DequeUsingStacks class.

You will write the code for all the methods of the DequeUsingStacks class except for the constructor.

The definition of each method you have to implement in the DequeUsingStacks class:

• int size() Return the number of data values currently in the deque.
• boolean isEmpty() Return true if the deque is empty; otherwise, return false.
• AnyType first() If the deque is empty then return null; otherwise, return the data value at the front of the deque.
• AnyType last() If the deque is empty then return null; otherwise, return the data value at the back of the deque.
• void addFirst(AnyType newValue) Add the data value newValue at the front of the deque.
• void addLast(AnyType newValue) Add the data value newValue at the back of the deque.
• AnyType removeFirst() If the deque is empty then return null; otherwise, remove and return the data value at the front of the deque.
• AnyType removeLast() If the deque is empty then return null; otherwise, remove and return the data value at the front of the deque.

If needed, you can write additional methods to help in your implementation of any method of the DequeUsingStacks class but they must be defined as private. You cannot add any additional data members to the DequeUsingStacks class. You cannot add any nested classes to the DequeUsingStacks class.

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

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

Assuming youre using Eclipse to create your project, you will store the input file assignment2.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, you will have to figure out where to store the input file.

The input consists of one or more commands (size, is_empty, first, last, add_first, add_last, remove_first, remove_last) with each command on a separate line. Each command can appear more than once in the input file.

The code you write to implement each command is NOT written in the DequeUsingStacks class but elsewhere in the program. The code for a command will call the appropriate method of the DequeUsingStacks class in order to accomplish the goal of the command.

Have the output for each command print on a separate line. Print a blank line after the output printed for the command.

The size command has your program print the number of values in the deque.
For example, if the deque contains 5 strings: size
Prints: The deque contains 5 strings.

The is_empty command has your program print the message The deque is empty or The deque is not empty.
For example: is_empty

The first command has your program print the string at the front of the deque.
For example, if the string at the front of the deque is New York City: first
Prints: The string at the front of the deque is "New York City".
But, if the deque is empty then the first command returns null and your program should print the message The deque was empty.

The last command has your program print the string at the back of the deque.
For example, if the string at the back of the deque is Salt Lake City: last
Prints: The string at the back of the deque is "Salt Lake City".
But, if the deque is empty then the last command returns null and your program should print the message The deque was empty.

The add_first command is the word add_first followed by a space followed by the rest of the characters on the line, a string. The add_first command has your program add that string at the front of the deque.
For example: add_first San Francisco
Prints: Added the string "San Francisco" to the front of the deque.

The add_last command is the word add_last followed by a space followed by the rest of the characters on the line, a string. The add_last command has your program add that string at the back of the deque.
For example: add_last Washington, D.C.
Prints: Added the string "Washington, D.C." to the back of the deque.

The remove_first command has your program remove and print the string at the front of the deque.
For example, if the string at the front of the deque is New York City: remove_first
Prints: Removed the string "New York City" from the front of the deque.
But, if the deque is empty then the remove_first command returns null and your program should print the message The deque was empty.

The remove_last command has your program remove and print the string at the back of the deque.
For example, if the string at the back of the deque is Salt Lake City: remove_last
Prints: Removed the string "Salt Lake City" from the back of the deque.
But, if the deque is empty then the remove_last command returns null and your program should print the message The deque was empty.

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

public static void main(String args[]).

The main method will open the file assignment2.txt, create a DequeUsingStacks 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."

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!