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.
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.