Chapter 6 – Stacks – the rest
Suppose
you had a language that consisted of strings that read the same forward as
backward (sort of like a palindrome) except that the character in the middle
had to be a ‘$’. So some words in the language are
bag$gab
XUD$DUX
But the word ‘abcde$decba’ is not in the language
The language is defined to be:
L = {w$w’ : w is a possibly empty string of
characters other than $, w’ is the reverse of w}
Can we write a method that will tell us when a
certain string is in the language or not? Yes.
stack.createStack( )
i =0
ch = character at position i in aString
while( ch is not ‘$’) {
stack.push(ch)
++i
ch =
character at position i in aString
}
++i// skip the $
inLanguage = true
while( inLanguage and i < length of aString) {
ch = character
at position i in aString
try {
stackTop
= stack.pop( )
if(stackTop
equals ch)
++i
else
inLanguage
= false
} end
try
catch
(StackException e)
inLanguage
= false
}
if(inLanguage and stack.isEmpty( ) )
aString
is in the language
else
aString
is not in the language
Now it is time to see an actual implementation of a stack in code. As before we will start with an interface which will later be filled in by another class:
public
interface StackInterface {
public boolean isEmpty();
// Determines whether the stack is empty.
// Precondition: None.
// Postcondition: Returns true if the stack
is empty;
// otherwise returns false.
public void popAll();
// Removes all the items from the stack.
// Precondition: None.
// PostCondition: Stack is empty.
public void push(Object newItem) throws
StackException;
// Adds an item to the top of a stack.
// Precondition: newItem is the item to be
added.
// Postcondition: If insertion is
successful, newItem
// is on the top of the stack.
// Exception: Some implementations may throw
// StackException when newItem cannot be
placed on
// the stack.
public Object pop() throws StackException;
// Removes the top of a stack.
// Precondition: None.
// Postcondition: If the stack is not empty,
the item
// that was added most recently is removed
from the
// stack and returned.
// Exception: Throws StackException if the
stack is
// empty.
public Object peek() throws StackException;
// Retrieves the top of a stack.
// Precondition: None.
// Postcondition: If the stack is not empty,
the item
// that was added most recently is returned.
The
// stack is unchanged.
// Exception: Throws StackException if the
stack is
// empty.
} // end StackInterface
As you can see we have defined the methods that the stack data structure will need, but we have not said how we will actually implement them. One of the easiest ways to implement a stack is by using an array. Following is the array implementation of the stack interface.
public
class StackArrayBased
implements StackInterface {
final int MAX_STACK = 50; // maximum size of stack
private Object items[];
private int top;
public StackArrayBased() {
items = new Object[MAX_STACK];
top = -1;
} //
end default constructor
// top is set to
a –1 because when the first item is pushed it will
// be at index 0 in the
array
public boolean isEmpty() {
return top < 0;
} //
end isEmpty
// if top is negative
the stack is empty
public boolean isFull() {
return top == MAX_STACK-1;
} //
end isFull
// if top is 49
(the last index in the array),the stack is full
public void push(Object newItem) throws
StackException {
if (!isFull()) {
items[++top] = newItem;
}
else {
throw new
StackException("StackException on " +
"push:
stack full");
}
// end if
} //
end push
// why do they
do items[++top] = newItem?????
public void popAll() {
items = new Object[MAX_STACK];
top = -1;
} //
end popAll
// Notice the
creation of a new array
public Object pop() throws StackException {
if (!isEmpty()) {
return items[top--];
}
else {
throw new
StackException("StackException on " +
"pop:
stack empty");
}
// end if
} //
end pop
// why do they do
items[top--] ?????
public Object peek() throws StackException {
if (!isEmpty()) {
return items[top];
}
else {
throw new StackException("Stack
exception on " +
"peek -
stack empty");
}
// end if
} //
end peek
} // end StackArrayBased
Now in an
array, you can always get to any element you want right away. Keeping track of “top”
as an index in the array will allow you to get to that item immediately.
But suppose we wanted to use a list as a stack. One
might be tempted to place the top of the stack at the end of the list (similar
to an array) but that would be a mistake because you need to get fast access to
it. So, a better idea is to replace our “head” pointer with a “top” pointer.
Then top always points to the first node in the list. Also the first node is
the one that will either be pushed onto the list or popped from it.
See Figure 6-5 in your textbook for a list based
stack. Notice that top is really pointing to the first node in the list. The
authors just drew the list vertically going down rather than horizontally going
off to the right.
Here is the Stack as implemented using our good old
node definitions:
public
class StackReferenceBased
implements StackInterface {
private Node top;
public StackReferenceBased() {
top = null;
} //
end default constructor
public boolean isEmpty() {
return top == null;
} //
end isEmpty
public void push(Object newItem) {
top = new Node(newItem, top);
} //
end push
// do you see how this inserts the
Node as the first node?
public Object pop() throws StackException {
if (!isEmpty()) {
Node temp = top;
top = top.getNext();
return temp.getItem();
}
else {
throw new StackException("StackException
on " +
"pop:
stack empty");
}
// end if
} //
end pop
// Do you see how
this deletes the first node?
public void popAll() {
top = null;
} //
end popAll
public Object peek() throws StackException {
if (!isEmpty()) {
return top.getItem();
}
else {
throw new
StackException("StackException on " +
"peek:
stack empty");
}
// end if
} //
end peek
} // end StackReferenceBased
Of course along with this interface implementation,
you need all of the Node definitions just like you had before, namely:
public class Node {
private Object item;
private Node next;
public Node(Object newItem) {
item = newItem;
next = null;
} // end constructor
public Node(Object newItem, Node nextNode) {
item = newItem;
next = nextNode;
} // end constructor
public void setItem(Object newItem) {
item = newItem;
} // end setItem
public Object getItem() {
return item;
} // end getItem
public void setNext(Node nextNode) {
next = nextNode;
} // end setNext
public Node getNext() {
return next;
} // end getNext
} // end class Node
It’s no wonder programs can get long very quickly J
If we wanted to get fancier, then we could even
implement the stack as a linked list and use the whole kit-and-caboodle of
stuff we developed there.
Here is the stack:
// Assumes that the classes ListInterface and ListReferenceBased
// are available
public
class StackListBased implements StackInterface {
private ListInterface list;
public StackListBased() {
list = new ListReferenceBased();
} //
end default constructor
public boolean isEmpty() {
return list.isEmpty();
} //
end isEmpty
public void push(Object newItem) {
list.add(1, newItem);
} //
end push
public Object pop() throws StackException {
if (!list.isEmpty()) {
Object temp = list.get(1);
list.remove(1);
return temp;
}
else {
throw new
StackException("StackException on " +
"pop:
stack empty");
}
// end if
} //
end pop
public void popAll() {
list.removeAll();
} //
end popAll
public Object peek() throws StackException {
if (!isEmpty()) {
return list.get(1);
}
else {
throw new
StackException("StackException on " +
"peek:
stack empty");
}
// end if
} //
end peek
} // end StackListBased
Notice the comment that begins this section of code.
This implementation assumes that we have the following already defined.
// ****************************************************
// Interface for the ADT
list
//
****************************************************
public interface
ListInterface {
// list operations:
public boolean isEmpty();
public int size();
public void add(int index, Object item)
throws ListIndexOutOfBoundsException;
public void remove(int index)
throws ListIndexOutOfBoundsException;
public Object get(int index)
throws ListIndexOutOfBoundsException;
public void removeAll();
} // end ListInterface
AND
// ****************************************************
// Reference-based
implementation of ADT list.
//
****************************************************
public class
ListReferenceBased implements ListInterface {
// reference to linked list of items
private Node head;
private int numItems; // number of items in list
public ListReferenceBased() {
numItems = 0;
head = null;
} // end default
constructor
public boolean isEmpty() {
return numItems == 0;
} // end isEmpty
public int size() {
return numItems;
} // end size
private Node find(int index) {
// --------------------------------------------------
// Locates a specified node in a linked list.
// Precondition: index is the number of the desired
// node. Assumes that 1 <= index <= numItems+1
// Postcondition: Returns a reference to the desired
// node.
// --------------------------------------------------
Node curr = head;
for (int skip = 1; skip < index; skip++) {
curr = curr.getNext();
} // end for
return curr;
} // end find
public Object get(int index)
throws ListIndexOutOfBoundsException {
if (index >= 1 && index <= numItems) {
// get reference to node, then data in node
Node curr = find(index);
Object dataItem = curr.getItem();
return dataItem;
}
else {
throw new ListIndexOutOfBoundsException(
"List index out of bounds exception on
get");
} // end if
} // end get
public void add(int index, Object item)
throws ListIndexOutOfBoundsException {
if (index >= 1 && index <= numItems+1) {
if (index == 1) {
// insert the new node containing item at
// beginning of list
Node newNode = new Node(item, head);
head = newNode;
}
else {
Node prev = find(index-1);
// insert the new node containing item after
// the node that prev references
Node newNode = new Node(item, prev.getNext());
prev.setNext(newNode);
} // end if
numItems++;
}
else {
throw new ListIndexOutOfBoundsException(
"List index out of bounds exception on
add");
} // end if
} // end add
public void remove(int index)
throws ListIndexOutOfBoundsException {
if (index >= 1 && index <= numItems) {
if (index == 1) {
// delete the first node from the list
head = head.getNext();
}
else {
Node prev = find(index-1);
// delete the node after the node that prev
// references, save reference to node
Node curr = prev.getNext();
prev.setNext(curr.getNext());
} // end if
numItems--;
} // end if
else {
throw new ListIndexOutOfBoundsException(
"List index out of bounds exception on
remove");
} // end if
} // end remove
public void removeAll() {
// setting head to null causes list to be
// unreachable and thus marked for garbage
// collection
head = null;
numItems = 0;
} // end removeAll
} // end
ListReferenceBased
AND
public class
StackException
extends java.lang.RuntimeException {
public StackException(String s) {
super(s);
} // end constructor
} // end StackException
AND
All of the stuff for our Node definition that we had before. Is Object-Oriented Programming expensive when it comes to the amount of code one has to produce? YES! Is it worth it? YES! Why?
We
have discussed how recursion can be used to check the validity of a Java
identifier. We have discussed how a stack can be used to check the validity of
balanced braces in a java program. What about another computer application, one
that goes all the way down to the CPU when it’s doing arithmetic?
All arithmetic expressions can be put into what is
known as post-fix notation. In this notation, the arithmetic operators are
placed after the values on which they will operate. For example:
4 6 2
* +
The way to read this is:
Read
the 4
Read
the 6
Read
the 2
Read
the *
Do I
have two numbers to multiply? Yes the 6 and the 2 that were read last
Mutiply
the 6 and the 2 to get 12
Replace
the 6, 2, and * with a 12, giving 4 12 +
Read the
plus
Do I
have two numbers to add? Yes the 4 and the 12
Add
the 4 and the 12 to get 16
Replace
the 4 12 + with the 16
Is
there any more to read?
No,
the answer is 16.
Try this one:
6 2 +
3 * 4 / 5 –
Can you do it?
Try following this algorithm that uses a stack:
for (each character ch in the string){
if(ch
is an operand(i.e. a number))
push
its value onto the stack
else
{
operand1
= pop the top of the stack
operand2 = pop the top of the stack
calculate
result with current operator
push
result on to the stack
}
}
CPUs do not like to deal with parentheses and all the other stuff that may be in an arithmetic expression. Using a post-fix notation and a stack is a lot simpler.
Actually you can use stacks to convert regular
arithmetic expressions into postfix notation as well. This would be something a
compiler would do to get code ready for the CPU to execute.
Try converting the following expression to post-fix
notation (without parentheses)!
(( a –
b) * ( c + d ) / (e – f * g)) – (h * ( i
+ j ) )
What problems did you face? What would a method have
to be aware of in order to try one of these conversions? Would the method on
page 271 of your text work?
By the way, you may want to test out one of the stack implementations we went ver before with this little test program:
public
class StackTest {
public static final int MAX_ITEMS = 15;
public static void main(String[] args) {
StackArrayBased stack = new
StackArrayBased();
Integer items[] = new Integer[MAX_ITEMS];
for (int i=0; i<MAX_ITEMS; i++) {
items[i] = new Integer(i);
if (!stack.isFull()) {
stack.push(items[i]);
}
// end if
}
// end for
while (!stack.isEmpty()) {
// cast result of pop to Integer
System.out.println((Integer)(stack.pop()));
}
// end while
} //
end main
}
A few exercises for your next assignment:
Page
290, problems 1, 6, 9 and 10