Transcript Introduction (CB chap. 1 & 2)

Implementing Stacks
Ellen Walker
CPSC 201 Data Structures
Hiram College
Operations on a Stack
•
•
•
•
Create an empty stack
Is the stack empty?
Add a new item to the stack. (Push)
Remove the item that was most recently
added (Pop)
• Retrieve the item that was most recently
added (Peek)
Implementing a Stack
• All items in the stack must be stored
• Only the top item needs to be accessible for retrieval
• Therefore a stack is a restricted form of list
– Use the List interface
– Use an array (as inside ArrayList)
– Use linked nodes (as inside LinkedList)
• Java does none of these - it uses a vector (growable
array)
– But, to understand stacks better, we will consider the 3
options above
Implementing using a List
//Complete code pp. 272-273
public class ListStack < E > {
private List < E > theData;
public Stack < E > {
theData = new ArrayList < E>();
}
//more methods here
}
ArrayList Implementation
• Push adds to the list
– Where? Why?
• Pop removes an item
– Which one?
• Peek looks at the top item
– Where is it?
• ArrayList takes care of resizing the list, details
of implementations
Empty and Push Method
Public boolean empty() {
return theData.size() == 0;
}
public E push (E obj){
//add at end of ArrayList
theData.add (obj);
return (obj);
}
Peek
public E peek() {
if (empty())
throw new EmptyStackException();
//top is at the end of the array
return theData.get(theData.size()-1);
}
Pop
public E pop() {
if (empty())
throw new EmptyStackException();
//top is at the end of the array
//recall: remove returns the object removed
return theData.remove(theData.size()-1);
}
And now more detail…
• Pretend we don’t already have ArrayList or
LinkedList, and had to implement all from
scratch
• Why?
– Understand in detail how stacks work
– See the differences and tradeoffs between array
and linked stacks
– Appreciate how much easier it is to implement a
stack than a list (either type)
Array Implementation
• Push: insert element into the array (where?)
• Peek: retrieve the most recently inserted
element (where is it?)
• Pop: remove the most recently inserted
element (how)?
• Static vs. dynamic array?
Array Push, Pop
• All stack elements go into the array (in order)
• Newest element is last (highest index) in the
array
• Integer variable “top” indicates index of top
• Push increments top
• Pop decrements top
– Popped elements stay in array until overwritten by
new push
Choices for top
• Top points after the top element
– Push: first copy, then increment
– Top: A[top-1]
– Pop(item): first decrement, then copy
• If top points at the top element
– Push: first increment, then copy
– Top: A[top]
– Pop(item): copy item, decrement
Example: Top at
• Empty stack (top = –1)
A[0]=
A[1]=
A[2]=
A[3]=
A[4]=
• Push ‘a’, Push ‘b’, Push ‘c’ (top=2)
A[0]=‘a’ A[1]=‘b’ A[2]=‘c’
A[3]=
A[4]=
A[3]=
A[4]=
A[3]=
A[4]=
• Pop, Pop (top = 0)
A[0]=‘a’ A[1]=‘b’ A[2]=‘c’
• Push ‘z’ (top = 1)
A[0]=‘a’ A[1]=‘z’
A[2]=‘c’
Possible Errors
• Pop from empty stack
• Top of empty stack
– Throw EmptyStackException
• Push if stack is full (CAPACITY items)
– not a problem if resize is allowed (as in ArrayList)
– If not, a FullStackException could be thrown
Class definition (data members)
public class ArrayStack < E >{
// array for the stack
E[ ] theData;
//index of top item
int topOfStack = -1;
Constructor and Check for Empty
//Initial capacity
private static final int INITIAL_CAPACITY = 10;
//Construct an empty stack
public ArrayStack() {
theData = (E[]) new Object[INITIAL_CAPACITY];
}
//Empty?
public boolean empty(){
return top == -1;
}
Push
• //Push an item onto the stack
public E push(E obj){
if (topOfStack == theData.length-1) {
reallocate(); //or could throw an exception
}
//++top increments first, returns new value
theData[++topOfStack] = obj;
return obj
}
Pop
• //Pop an item from a stack and return it
public E Pop(){
if (empty())
throw new EmptyStackException();
else
return theData[topOfStack--];
}
Efficiency of stack
• Push: constant time
– Even though insert into array is not! (why?)
• Pop: constant time
– Even though delete from array is not!
Node (Linked-List) Implementation
• Push: insert element into the list (where?)
• Peek: retrieve the most recently inserted
element (where is it?)
• Pop: remove the most recently inserted
element (how)?
• isEmpty: (how do you know the stack is
empty?)
• What special cases require exceptions?
Linked implementation
• Underlying data structure is a singly linked list
• Push inserts at the beginning of the list
– Exception: cannot allocate a new node
• Pop removes from the beginning of the list
– Exception: empty list (stack)
• Empty stack when top is null
Example (Linked Implementation)
• Empty stack
• Push ‘a’, Push ‘b’, Push ‘c’
c
b
• Pop, Pop
a
• Push ‘z’
z
a
a
Class Definition
Public class LinkedStack {
private Node<E> topOfStackRef = null;
…
private static class Node<E>{
//same as for linked list
}
};
empty & peek
•
//Is the stack empty?
Public boolean empty() {
return (topOfStackRef == null);
}
•
//Get item from top
Public E peek() {
if (empty()) throw new EmptyStackException();
return topOfStackRef.data;
}
Push
• // push (add to beginning of list)
public E push (E obj){
topOfStackRef =
new Node<E>(obj, topOfStackRef);
return obj;
}
Pop
• //Pop and recover old top item
Public E pop(){
if (empty()) throw new EmptyStackException();
else{
E result = topOfStackRef.data;
topOfStackRef = topOfStackRef.next;
return result;
}
}
Nodes vs. Arrays
• Array is simpler, requires extra space (unused
capacity)
• Node uses minimum amount of space
• Push and pop are O(1) either way
• We never need to access the middle of the list.
• Note: replace ArrayList by LinkedList on slide 6 to get
the list functionality without writing any new code.
You must also replace add() by addFirst() in push,
and remove() by removeFirst() in pop.
Postfix Expressions
• Also called RPN (reverse Polish notation)
– Enter first operand, then second operand, then
operator
– (Operands can be recursive expressions)
– Example
•
•
•
•
1+(2*3) becomes 1 2 3 * +
First operand is 1
Second operand is (recursively) 2 3 *
Operator is +
Stacks Evaluate Postfix
• Reading the data:
If you see an operand (number), push it
If you see an operator,
pop the first two items off the stack
perform the operation
push the result back on the stack
• Example: 1 2 3 * +
– Push 1, push 2, push 3, pop 3, pop 2, push 6
– Pop 6, pop 1, push 7
Infix Expressions
• Infix expressions are the kind we use in Java
– 6*3+7
– 6+3*7
– (6+3) * 7
• Order of operation depends on precedence
– Multiplication first, then addition
– Parentheses override order
– Otherwise, left to right
Converting Infix to Postfix
• Operands (numbers) stay in the same order
• Operators go in after their operands are
complete
– 6*3+7 - 6 3 * 7 +
– 6+3*7
637*+
– (6+3) * 7 6 3 + 7 *
• How to decide when to insert the operator?
Algorithm for Infix to Postfix
• For each token
– If it is an operand, insert it immediately in the
result
– If it is an operator
– While stack is not empty AND this operator has
lower precedence than top-of-stack operator
–
pop operator from stack into expression
– push this operator
• Pop remaining operators into expression
Examples
– 6*3+7
63*7+
– 6+3*7
637*+
What about parentheses?
• When you see a left parenthesis, push it on
the stack
• When you see a right parenthesis, pop all
operators back to the left paren
• Why?
– Parentheses delimit a new expression
– Right paren acts like end of expression (pop all
remaining operators at the end)
Example
– (6+3) * 7
63+7*
A Search Problem
• Given a sequence of flight segments, can you
reach one city from the other?
• If there is a flight from A to B, then A and B
are adjacent (A->B)
• If (A->B) and (B->C), we can reach C from A
Recursive Solution (pseudocode)
bool canReach(city A, city B){
If (A == B) return true; //trivial problem
If (adjacent(A,B)) return true; //direct flight
For (each city adjacent to A)
if canReach(city, B) return true;
Return false;
}
Stack-based solution (pseudocode)
bool canReach(city A, city B){
If (A == B) return true; //trivial problem
Else push A onto the stack
While(stack is not empty and top != B)
if the city has an unvisited neighbor
mark the neighbor as visited
push the neighbor on the stack
else pop the stack;
}
If the stack is empty return false;
Otherwise return true (and the path is on the stack!)
}
Comments on stack based search
• No essential difference between recursive
and stack algorithms
• This algorithm is called “depth-first search”
• Path that is found will not necessarily be the
shortest
• Order of visits doesn’t matter for correctness,
but matters significantly for efficiency