Worksheet 1

There are two parts suggested for this workshop.

Using a stack to reverse a string

The aim of this exercise is to use a stack to reverse a string. For example, given the input string

  hello

the program should return

  olleh

Specifically, write a method

  String reverse(String str);

which takes a given string str and returns its reverse, using a Stack which is local to the method. Then use this in a main method which does the input and output. You can find an example of what your code might look like here.

Hint: use the String.length and String.charAt methods from the String class to access the individual characters making up the string and push them, one at a time, onto the stack. Then get a new (empty) string and pop the characters off the stack, one at a time, and concatenate them onto the end of the new string. When the stack is empty, you should have the reversed string.

Adding a peek method to the Stack class

Specifications of the Stack data structure often include a

public Object peek();

method which returns the top item on the stack (the one most recently pushed) without popping it (i.e. it leaves it on the stack). Write your own MyStack interface which includes this method as well as the ones in the Stack interface you have already been shown. Write a MyStackArray class which implements the MyStack interface (it can be the same as StackArray apart from this one method). Then write a MyStackDemo class which tests your implementation.

There is very little coding to do in this exercise. The purpose is to help you understand the relationship between interfaces and implementing classes, how to name such things, and how to store them in appropriate files.

To do this, take a copy, into your working directory, of the file Stack.java from the DataStructures package. Call your version of this file MyStack.java. Change the name of the interface it defines to MyStack, delete the first line

package DataStructures;

and include the declaration

public Object peek();

Now copy the file StackArray.java from the DataStructures package to your working directory, change its name to MyStackArray.java and the name of the class it contains etc. Add a little code to MyStackArray.java to make it implement the MyStack interface.

Now copy StackDemo.java to your working directory, and call it MyStackDemo.java. Replace the line

  Stack s = new StackArray()

by

  MyStack s = new MyStackArray()

and modify the code so that it exercises the MyStack.peek method.

It probably won't work first time. But you will learn a lot by trying to figure out why not.