Transcript Review for final

The Stack Class
Final Review
Fall 2005
CS 101
Aaron Bloomfield
1
Motivation
 Same as for Vectors
 We want an easy way to store elements in a object
without having to worry about manipulating arrays
2
Properties of our Stack class
 It needs to have an array to hold the values
 That array will be fixed at size 1000
 We’ll call it ‘array’
 Thus, we also need a value to hold the number of elements in
the stack
 We’ll call it ‘size’
 Our Stack class so far:
public class Stack {
int array[] = new int[1000];
int size = 0;
3
About stacks
 With a stack, you can only add and remove elements from
ONE end
 Both occur from the same end
 Think of a stack of papers – you are always adding a new
paper to the top or removing it from the top
 Adding an element is called pushing an element
 Removing an element is called popping an element
4
Methods in our Stack class






Create a Stack object
Insert and remove elements into/from the Stack
Get the top element
Find if the stack is empty
Print it out to the screen
Search the stack for a value
5
The Stack Constructor
 Ready?
public Stack () {
}
 Rather boring…
 As we initialized the variables earlier, we don’t need to do so
here
 But we could have done here just as well
6
Pushing an element onto the Stack

To add an element onto the Stack, we want to do two things
 Insert it into the array at the proper position
 Increment the size of the array

The code:
public void push (int value) {
array[size++] = value;
}

We could have done this in two lines as well:
public void push (int value) {
array[size] = value;
size = size + 1;
}
7
Popping an element from the Stack

To add an element onto the Stack, we want to do two things
 Find (and return) the top element in the Stack
 Decrement the size of the array

The code:
public int pop () {
return array[--size];
}

We could have done this in two lines as well:
public int pop () {
size = size – 1;
return array[size];
}
8
peek() and empty()
 peek() is a quickie:
public int peek () {
return array[size-1];
}
 empty() is also a quickie:
public boolean empty() {
return size == 0;
}
9
Searching the Stack
 Note that we want to search up to the value in size, not the
entire (1,000 element) array
 The method:
public boolean search (int forwhat) {
for ( int i = 0; i < size; i++ )
if ( array[i] == size )
return true;
return false;
}
10
Printing the Stack
 The method:
public String toString() {
String ret = "Stack[";
for ( int i = 0; i < size; i++ ) {
ret += array[i];
 This is just so that the
if ( i != size-1 )
method doesn’t print a
ret += ", ";
comma after the last
}
element
ret += "]";
 Our for loop body could
also have been:
return ret;
ret += array[i] + ", ";
}
11
Using our Stack
public static void main (String args[]) {
Stack stack = new Stack();
System.out.println ("pushing elements 5 through 10 onto the stack");
for ( int i = 5; i <= 10; i++ )
stack.push(i);
System.out.println (stack);
System.out.println ("peek() returned: " + stack.peek());
System.out.println ("search(9) returned: " + stack.search(9));
int ret = stack.pop();
System.out.println ("pop() returned: " + ret);
System.out.println (stack);
System.out.println ("peek() returned: " + stack.peek());
ret = stack.pop();
System.out.println ("pop() returned: " + ret);
ret = stack.pop();
System.out.println ("pop() returned: " + ret);
System.out.println (stack);
System.out.println ("peek() returned: " + stack.peek());
System.out.println ("search(9) returned: " + stack.search(9));
}
12
Program Demo

Stack.java
13