CS210 ALGORITHMS & DATA STRUCTURES I

LABORATORY 2

30/09/05

Mr. T. Lysaght

STACK DATA STRUCTURE

The purpose of this Laboratory session is the implementation of the Stack data structure using Arrays and ArrayLists.

  1. Design a Stack Class, ArrayStack, to implement the operations of the Stack data structure using an array.  Implement the class using the following methods:

ArrayStack (int size)  //  Sets the size of the stack and initializes instance variables

Push (int S)  //  Add an element to the Top of the stack

Pop()     // remove the Top element of the stack (decrement the TopOfStack)

Top()    // Return the Top element of the stack

print()   //prints the array in reverse order giving the TopOfStack first

IsEmpty()  //Returns True if the stack is empty

IsFull()  // Returns True if the stack is full

MakeEmpty()  //move TopOfStack to -1

 

There are three instance variables in the class:

 

private int Maxsize // the capacity of the stack or size of the array

private int TopOfStack // index of Top of stack

private int [] Sarray;

 

Write a Tester program to test the stack program. 

 

                                                                                                         i.      Push 4 integers onto the stack

                                                                                                       ii.      Print the top element of the stack.

                                                                                                      iii.      Pop the stack.  Print the top element and then print the complete stack.

                                                                                                     iv.      Empty the stack.  Attempt to print the top element.

 

2.      Implement the above stack program using an ArrayList.  Implement the ArrayList stack class, ArrayListStack, using ArrayList methods.  Use method add() to implement Push,  remove() to implement Pop, get() to implement Top.  Use any other ArrayList methods where needed e.g., size(). Use the generalised for loop where appropriate, e.g.,  given an array data of Doubles,  calculate the sum of all elements:

                                   

sum = 0;

for (double e: data)

       sum = sum + e. 

 

3.      Use the ArrayStack Class to test for matching brackets from a string input of brackets e.g., “{ { { } } }”.

Java also has its own Stack class, Stack, included in java.util.Stack with the following methods

push(data type variable)

pop()

peek()  //identical to Top

             Alternatively use these methods to add and remove brackets from the stack.