Transcript Arrays in JAVA

M180: Data Structures & Algorithms in Java
Stacks
Arab Open University
1
Abstract Data Types (ADTs)
• ADT: A specification of a collection of data & the
operations that can be performed on it.
• Stack: Retrieves elements in the reverse of the order
they were added.
push pop, peek
top
3
2
bottom
1
stack
2
Stacks
• Stack: A collection based on the principle of adding
elements and retrieving them in the opposite order.
– Last-In, First-Out ("LIFO")
– Elements are stored in order of insertion.
• We do not think of them as having indexes.
– Client can only add/remove/examine the last element added (the
"top").
• Basic stack operations:
– push: Add an element to the top.
– pop: Remove the top element.
– peek: Examine the top element.
3
Conceptual View of a Stack
Adding an element
New object is added as the
new top element of the stack
(old) top
of stack
new
top
bottom
of stack
bottom
4
Conceptual View of a Stack
Removing an element
Object is removed from the top
of the stack
top
bottom
new
top
bottom
5
Stack Operations
• push: add an element at the top of the stack
• pop: remove the element at the top of the
stack
• peek: examine the element at the top of the
stack
• It is not legal to access any element other
than the one that is at the top of the stack!
6
Java Interfaces
• Abstract method : a method that does not have
an implementation, i.e. it just consists of the
header of the method:
Return type method name (parameter list)
7
Java Interfaces
• Java has a programming construct called an
interface that we use to formally define what
the operations on a collection are in Java.
• Java interface: a list of abstract methods and
constants
– Must be public
– Constants must be declared as final static
8
Java Interface for Stack<T> ADT
public interface StackADT<T>
{
// Adds one element to the top of this stack
public void push (T element);
// Removes and returns the top element from this stack
public T pop( );
// Returns without removing the top element of this stack
public T peek( );
// Returns true if this stack contains no elements
public boolean isEmpty( );
// Returns the number of elements in this stack
public int size( );
// Returns a string representation of this stack
public String toString( );
}
9
Generic Types
What is this <T> in the interface definition?
• It represents a generic type
– For generality, we can define a class (or interface)
based on a generic type rather than an actual type
– Example: we define a Stack for objects of type T
• The actual type is known only when an application
program creates an object of that class
10
Stack limitations
• You cannot loop over a stack in the usual way.
Stack<Integer> s = new Stack<Integer>();
...
for (int i = 0; i < s.size(); i++) {
do something with s.get(i);
}
• Instead, you pull elements out of the stack one at a time.
– common idiom: Pop each element until the stack is
empty.
while (!s.isEmpty()) {
do something with s.pop();
}
Array implementation of stacks
• To implement a stack, items are inserted and removed at the same
end (called the top).
• Efficient array implementation requires that the top of the stack be
towards the center of the array, not fixed at one end.
• To use an array to implement a stack, you need both the array
itself and an integer.
• The integer tells you either:
– Which location is currently the top of the stack, or
– How many elements are in the stack
12
An Array-Based Implementation
An array that implements a stack; its first location references (a) the top of the
stack; (b) the bottom of the stack
13
Pushing and popping
0
1
2
3
stk: 17
23
97
44
4
5
top = 3
6
7
or
8
9
count = 4
• If the bottom of the stack is at location 0, then an empty
stack is represented by top = -1 or count = 0.
• To add (push) an element, either:
– Increment top and store the element in stk[top], or
– Store the element in stk[count] and increment count.
• To remove (pop) an element, either:
– Get the element from stk[top] and decrement top, or
– Decrement count and get the element in stk[count]
14
After popping
0
1
2
3
stk: 17
23
97
44
4
5
top = 2
6
7
8
9
or count = 3
• When you pop an element, do you just leave the “deleted” element
sitting in the array?
• The surprising answer is, “it depends”
– In Java, if the array contains objects, you should set the “deleted” array
element to null
– Why? To allow it to be garbage collected!
15
Defining Stack Operations
public class AStack<T> implements StackADT<T>
{
Integer arr[];
int top,size;
AStack(int n)
{
size = n;
top = -1;
arr = new Integer[size];
}
public boolean isEmpty()
{
if(top == -1)
return true;
else
return false;
}
<< Continue
16
Defining Stack Operations – Cont’
public void pop()
{
if(top>=0)
{
System.out.println("the deleted element is "+arr[top]);
}
else
{
System.out.println("stack is empty");
}
}
<< Continue
17
Defining Stack Operations – Cont’
public void push(T element)
{
if(top==size-1)
{
System.out.println("stack over flow");
}
else
{
top=top+1;
arr[top]=(Integer)element;
System.out.println("added succesfully");
}
}
public T top()
{
if(top>=0)
return (E)arr[top];
else
return null;
}
18
Error checking
• There are two stack errors that can occur:
– Underflow: trying to pop (or peek at) an empty stack
– Overflow: trying to push onto an already full stack
• For underflow, you should throw an exception
– If you don’t catch it yourself, Java will throw an
ArrayIndexOutOfBounds exception
– You could create your own, more informative exception
• For overflow, you could do the same things
– Or, you could check for the problem, and copy everything into
a new, larger array
19
Complete Stack Code
• See the attached MS Word document.
20