Transcript Stacks

Stacks, Queues, and Deques
- Ed. 2, and 3.: Chapter 4
- Ed. 4: Chapter 5
Stacks, Queues, and Deques
• Stacks
- Stack ADT – interface
- Stack implementation
• Queues
- Queue ADT – interface
- Queue implementation
• Deques
- Deque ADT – interface
- Deque implementation
• Sample case study application
Stacks
A stack is an interesting data structure with a lot of applications.
In such a data structure, we are dealing with a collection of objects.
Objects can be added to or removed from the collection, one at a
time, as plates in a spring-loaded, cafeteria plate dispenser.
Stacks
Definition: A stack is a container of objects that are inserted and
removed according to the last-in first-out (LIFO) principle.
push
Two fundamental operations:
push: Insert an object to the container.
pop: Remove an object from the container.
pop
The Stack Abstract Data Type
An array of integers is not a stack. However, if we enforce the
LIFO principle, it becomes a stack.
A stack S is an abstract data type (ADT) that supports following
two fundamental methods:
push(o): Insert object o at the top of the stack
Input: Object; Output: None.
pop(): Remove from the stack and return the top object on
the stack; an error occurs if the stack is empty.
Input: None; Output: Object
Other supporting methods:
size(): Return the number of objects in the stack.
Input: None; Output: Integer
isEmpty(): Return a Boolean indicating if the stack is empty.
Input: None; Output: Boolean
top(): Return the top object on the stack, without removing
it; an error occurs if the stack is empty.
Input: None; Output: Object
This table shows a series of stack operations and their effects.
The stack is initially empty.
Operation
Output
S
push(5)
-
(5)
push(3)
-
(5,3)
pop()
3
(5)
push(7)
-
(5,7)
pop()
7
(5)
top()
5
(5)
pop()
5
()
pop()
“error”
()
isEmpty()
true
()
push(9)
-
(9)
push(7)
-
(9,7)
push(3)
-
(9,7,3)
push(5)
-
(9,7,3,5)
size()
4
(9,7,3,5)
pop()
5
(9,7,3)
push(8)
-
(9,7,3,8)
pop()
8
(9,7,3)
pop()
3
(9,7)
5
3
5
5
A Stack Interface in Java
public interface Stack {
public void push( Object element );
public Object pop()
throws StackEmptyException;
public int size();
public boolean isEmpty();
public Object top()
throws StackEmptyException;
}
When we define an interface, we just indicate that
a class which implements it should provide all the
methods specified in it.
Here is the definition of the exception handler.
public class StackEmptyException extends RuntimeException
{
public StackEmptyException( String err ) {
super( err );
}
}
A Simple Array-Based
Implementation
To implement a stack with an array, we need:
1. An array of the given size
2. An index t for the top element (Normally, t is implemented
as a variable of type int. Initially, t is set to –1.)
S:
0
1
……
t
N-1
Algorithms:
size():
return the number t + 1
S:
0
1
……
t
N-1
Algorithms:
isEmpty():
return true if t < 0; otherwise, false.
S:
0
1
t + 1 = 0 or
t = -1 or
t<0
……
t
N-1
Algorithms:
top():
if the stack is empty
throw a StackEmptyException
else
return element S[t]
S:
0
1
……
t
N-1
push(o):
if stack size is N
throw a StackFullException
else
increase the index t by 1
store the object to S[t]
S:
0
1
……
t t+1
N-1
push
pop():
if stack is empty
throw a StackEmptyException
else
save the element S[t] to a variable e
make the element S[t] a null object
decrease the index t by 1
return e
S:
0
1
……
N-1
t
pop
Java code (a class implementing Interface Stack)
public class ArrayStack implements Stack {
public static final int CAPACITY = 1000;
private int capacity;
private Object S[];
private int top = -1;
public ArrayStack() {
this( CAPACITY );
}
public ArrayStack( int cap ) {
capacity = cap;
S = new Object[ capacity ];
}
public int size() {
return ( top + 1 );
}
public boolean isEmpty() {
return( top < 0 );
}
public void push( Object obj ) throws StackFullException
{
if( size() == capacity )
throw new StackFullException( "Stack overflow" );
S[ ++top ] = obj;
}
public Object top() throws StackEmptyException {
if( isEmpty() )
throw new StackEmptyException( "Stack is empty."
);
return S[ top ];
}
public Object pop() throws StackEmptyException {
Object elem;
if( isEmpty() )
throw new StackEmptyException( "Stack is
Empty." );
elem = S[ top ];
S[ top-- ] = null;
return elem;
}
}
public class StackFullException extends RuntimeException
{
public StackFullException( String err ) {
super( err );
}
}
Stacks in the Java Virtual
Machine
Recall that programs written in Java must be compiled by a Java
compiler. The product is a byte code, the instructions for Java
virtual machines. To run the Java program, the Java virtual
machine will execute the byte code instructions one by one.
The Java virtual machine provides a stack called Java method
stack for each running program. Data in the stack are organized
into structures called frames. For each method, a frame is
pushed into the stack. Within the frame are the local variables
and arguments for the method.
fool:
PC=320
m = 7
cool:
PC=216
j = 5
k = 7
main:
PC=14
i = 5
Java stack
14
216
320
main() {
int i = 5;
...
cool( i );
...
}
cool( int j ) {
int k = 7;
...
fool( k );
...
}
fool( int m ) {
...
}
Java program
Sample Case Study Application
We want to write a program to calculate the span of the stock’s
price on a given day.
The span of the stock’s price on a given day: The maximum
number of the consecutive days up to the current day (including the
current day) such that the stock price on each of those days has been
less than or equal to the price on the current day.
Exemplary data:
Price of 7-year bonds:
April
9
48.97
April
10
47.54
April
11
45.83
April
12
46.34
April
13
45.68
April
14
46.95
April
15
48.17
April
9
April
10
April
11
April
12
April
13
April
14
April
15
1
1
1
2
1
4
6
Spans:
Let us use some symbols to represent the problem:
Stock Price:
April
9
p0
April
10
p1
April
11
p2
April
12
p3
April
13
p4
April
14
p5
April
15
p6
April
9
s0
April
10
s1
April
11
s2
April
12
s3
April
13
s4
April
14
s5
April
15
s6
The problem is how to calculate the span of a given day.
Analysis – property I:
Since price quotes start with a given day (day 0, which is April 9
in this example), we have:
si  i + 1
Spans:
s i:
April
9
April
10
April
11
April
12
April
13
April
14
April
15
1
1
1
2
1
4
6
s1 = 1
s2 = 1
s3 = 2
s4 = 1
s5 = 4
s6 = 6
1+1
2+1
3+1
4+1
5+1
6+1
s0 = 1
i + 1: 0 + 1
Analysis – property II:
For a given day i, if the span is 1, it means
pi-1 > pi or (The price of day pi-1 is higher than that of
i=0
day pi.)
If the span is 2, it means: pi-1  pi and pi-2 > pi .
If the span is 3, it means: pi-2  pi , pi-1  pi, and pi-3 > pi.
If the span is 4, it means: pi-3  pi , pi-2  pi, pi-1  pi, and
pi-4 > pi.
In general, if the span of pi is k, it means:
pi-k-1  pi, pi-k-2  pi, … pi-1  pi, and pi-k > pi.
s0=1
s6=6
s1=1
s5=4
s3=2
s2=1
p0
p1
p2
s4=1
p3
p4
p5
p6
An Algorithm Without Using a
Stack
Let us consider an algorithm without using a stack.
To find out the span for a given day i:
1. Assign value 0 to a variable k
2. Compare pi-k with pi.
3. If pi-k  pi, increment the value in k and go to step 2.
4. Step 2 and 3 are repeated until pi-k > pi or k > i. The span is the
value in the variable k.
To find out the spans for all the days, the procedure has to be
repeated with i = 0, 1, …, n - 1. Therefore, the complete algorithm
has two loops: One for the days and another is to find the span for
a given day. The spans are stored in an array s.
for i = 0 to n -1
assign value 0 to a variable k
repeat until pi-k > pi or k > i
compare pi-k with pi.
if pi-k  pi
increment the value in k
save the value of k to s[i]
i
p1 p2
pi
……
……
pn-1
k
for a certain i
s[i]
The running time of this algorithm is proportional to the square
of n, the number of days, namely,
running time = O(n2)
(We say a quantity D is O(n2) if there exists a real constant c and
an integer n0  1 such that D  cn2 for every integer n  n0.)
Such an algorithm is called a quadratic-time algorithm.
Using a stack, however, we can cut down the running time
dramatically.
An Algorithm Using a Stack
Note that the span si on a certain day i can be easily computed
if we know the closest day preceding day i, such that the price
on that day is higher than the price on day i.
If such a preceding day exists for a day i, let us denote it with
h(i), and otherwise let us define h(i) = -1. Then, si = i – h(i).
si = i – h(i).
Example:
p0
48.97
p1
47.54
p2
45.83
p3
46.34
p4
45.68
p5
46.95
p6
48.17
h(0)
-1
h(1)
0
h(2)
1
h(3)
1
h(4)
3
h(5)
1
h(6)
0
s0
1
s1
1
s2
1
s3
2
s4
1
s5
4
s6
6
The problem is how to compute h(i) efficiently?
Step 1:
p0 = 48.97. h(0) = -1, s0 = 0 - h(0) = 0 – (-1) = 1
0
Day 0. It is possible that h(1) = 0.
Step 2:
p1 = 47.54. Pop days with prices less than or equal to p1.
At this point of time, we have only one element in the stack.
It is 0 and p0 > p1. So h(1) = 0, s1 = 1 - h(1) = 1 – 0 = 1.
1
0
Day 1. It is possible that h(2) = 1.
Step 3:
p2 = 45.83. Pop days with prices less than or equal to p2.
At this point of time, we have two elements in the stack.
The top one is 1 and p1 > p2. So h(2) = 1, s2 = 2 - h(2) = 2 – 1 = 1.
2
Day 2. It is possible that h(3) = 2.
1
0
Step 4:
p3 = 46.34. Pop days with prices less than or equal to p3.
The top one will be taken out since p3 > p2.
The second one is 1 and p1 > p3. So h(3) = 1, s3 = 3 - h(3) = 3 – 1 = 2.
3
1
0
Day 3. It is possible that h(4) = 3.
Step 5:
p4 = 45.68. Pop days with prices less than or equal to p4.
The top one is 3 and p3 > p4. So h(4) = 3, s4 = 4 - h(3) = 4 – 3 = 1.
4
3
Day 4. It is possible that h(5) = 4.
1
0
Step 6:
p5 = 46.95. Pop days with prices less than or equal to p3.
The top two will be taken out since p5 > p4 and p5 > p3.
The third one is 1 and p1 > p5. So h(5) = 1, s5 = 5 - h(5) = 5 – 1 = 4.
5
1
0
Day 5. It is possible that h(6) = 5.
Step 7:
p6 = 48.17. Pop days with prices less than or equal to p3.
The top two will be taken out since p6 > p5 and p6 > p1.
The third one is 0 and p0 > p6. So h(6) = 0, s6 = 6 - h(6) = 6 – 0 = 6.
6
0
Day 6. The price on day 6. The process stops.
Java Implementation
public void computeDailyHighSpan( Quote Q[]) {
int prevHigh;
Stack D = new ArrayStack();
for( int i = 0; i < Q.length; i++ ) {
while( !D.isEmpty() &&
Q[ i ].getPrice() >= (( Quote )D.top()).getPrice() )
D.pop();
if( D.isEmpty() )
prevHigh = -1; //prevHigh used to store h(i)
h(0)
else
prevHigh = (( Quote )D.top()).getDay();
h(i)
Q[ i ].setSpan( i - prevHigh );
D.push( Q[ i ]);
}
}
public class Quote {
private int day, price, span;
public Quote( int d, int p ) {
setDay( d );
setPrice( p );
}
public void setDay( int d ) { day = d; }
public int getDay() { return day; }
public void setPrice( int p ) { price = p; }
public int getPrice() { return price; }
public void setSpan( int s ) { span = s; }
public int getSpan() { return span; }
}
Note:
What in the stack are the objects of class Quote rather than the
days.
Each object of class Quote has the day, stock price and the
span.
public class DailyHighSpan { … …
public static void main(String args[]) {
Quote Q[] = new Quote[10];
System.out.println("Input:" + "\n");
for (int i = 0; i < 10; i++) {
Q[i] = new Quote(i,(int)(Math.random()*100));
System.out.print(Q[i].getPrice(); );
System.out.print('\t');
//System.out.print("-");
}
System.out.println();
try{
computeDailyHighSpan(Q);
}
catch(EmptyStackException e) {}
}