Transcript Stack and Queue

Implementing and Using Stacks
many slides taken from Mike Scott, UT Austin
1
Stacks
Stacks are a straight forward and simple
data structure
Access is allowed only at one point of the
structure, normally termed the top of the
stack, so the operations are limited:
– push (add item to stack)
– pop (remove top item from stack)
– top (get top item without removing it)
– clear
– isEmpty
– size
2
Stack Operations
Assume a simple stack for integers.
Stack s = new Stack();
s.push(12);
s.push(4);
s.push( s.top() + 2 );
s.pop()
s.push( s.top() );
//what are contents of stack?
3
Stack Operations
Write a method to print out contents of stack
in reverse order.
4
Common Stack Error
Stack s = new Stack();
// put stuff in stack
for(int i = 0; i < 7; i++)
s.push( i );
// print out contents of stack
// while emptying it
for(int i = 0; i < s.size(); i++)
System.out.println( s.pop() );
// Output? Why?
// Crossover error
5
Corrected Version
Stack s = new Stack();
// put stuff in stack
for(int i = 0; i < 7; i++)
s.push( i );
// print out contents of stack
// while emptying it
int limit = s.size();
for(int i = 0; i < limit; i++)
System.out.println( s.pop() );
//or
// while( !s.isEmpty() )
//
System.out.println( s.pop() );
6
Balanced Symbol Checking
In processing programs and working with
computer languages there are many
instances when symbols must be balanced
{},[],()
A stack is useful for checking symbol balance.
When a closing symbol is found it must match
the most recent opening symbol of the same
type.
Algorithm?
7
Algorithm for Balanced
Symbol Checking
Make an empty stack
read symbols until end of file
– if the symbol is an opening symbol push it onto
the stack
– if it is a closing symbol do the following
• if the stack is empty report an error
• otherwise pop the stack. If the symbol popped does
not match the closing symbol report an error
At the end of the file if the stack is not empty
report an error
8
Algorithm in practice
list[i] = 3 * ( 44 - method( foo( list[ 2 * (i + 1) +
foo( list[i - 1] ) ) / 2 *) - list[ method(list[0])];
Processing a file
– Tokenization: the process of scanning an input
stream. Each independent chunk is a token.
Tokens may be made up of 1 or more
characters
9
Mathematical Calculations
What is 3 + 2 * 4? 2 * 4 + 3? 3 * 2 + 4?
The precedence of operators affects the
order of operations. A mathematical
expression cannot simply be evaluated left to
right.
A challenge when evaluating a program.
Lexical analysis is the process of
interpreting a program.
Involves Tokenization
What about 1 - 2 - 4 ^ 5 * 3 * 6 / 7 ^ 2 ^ 2
10
Infix and Postfix Expressions
The way we are used to writing expressions
is known as infix notation
Postfix expression does not require any
precedence rules
3 2 * 1 + is postfix of 3 * 2 + 1
evaluate the following postfix expressions
and write out a corresponding infix
expression:
2324*+*
12-32^3*6/+
1234^*+
25^111
Evaluation of Postfix Expressions
Easy to do with a stack
given a proper postfix expression:
– get the next token
– if it is an operand push it onto the stack
– else if it is an operator
•
•
•
•
pop the stack for the right hand operand
pop the stack for the left hand operand
apply the operator to the two operands
push the result onto the stack
– when the expression has been exhausted the
result is the top (and only element) of the stack
12
Infix to Postfix
Convert the following equations from infix to
postfix:
2^3^3+5*1
233^^51*+
11 + 2 - 1 * 3 / 3 + 2 ^ 2 / 3
11 2 + 1 3 * 3 / - 2 2 ^ 3 / +
Problems:
parentheses in expression
13
Infix to Postfix Conversion
Requires operator precedence parsing algorithm
– parse v. To determine the syntactic structure of a
sentence or other utterance
Operands: add to expression
Close parenthesis: pop stack symbols until an open
parenthesis appears
Operators:
Pop all stack symbols until a symbol of lower
precedence appears. Then push the operator
End of input: Pop all remaining stack symbols and
add to the expression
14
Simple Example
Infix Expression:
PostFix Expression:
Operator Stack:
3+2*4
15
Simple Example
Infix Expression:
PostFix Expression:
Operator Stack:
+2*4
3
16
Simple Example
Infix Expression:
PostFix Expression:
Operator Stack:
2*4
3
+
17
Simple Example
Infix Expression:
PostFix Expression:
Operator Stack:
*4
32
+
18
Simple Example
Infix Expression:
PostFix Expression:
Operator Stack:
4
32
+*
19
Simple Example
Infix Expression:
PostFix Expression:
Operator Stack:
324
+*
20
Simple Example
Infix Expression:
PostFix Expression:
Operator Stack:
324*
+
21
Simple Example
Infix Expression:
PostFix Expression:
Operator Stack:
324*+
22
Example
1-2^3^3-(4+5*6)*7
Show algorithm in action on above equation
23
Applications of Stacks
Direct applications
– Page-visited history in a Web browser
– Undo sequence in a text editor
– Chain of method calls in the Java Virtual
Machine
– Validate XML
Indirect applications
– Auxiliary data structure for algorithms
– Component of other data structures
24
Method Stack in the JVM
 The Java Virtual Machine
(JVM) keeps track of the chain
of active methods with a stack
 When a method is called, the
JVM pushes on the stack a
frame containing
main() {
int i = 5;
foo(i);
}
foo(int j) {
int k;
– Local variables and return value
– Program counter, keeping track of
k = j+1;
the statement being executed
bar(k);
 When a method ends, its frame
}
is popped from the stack and
control is passed to the method bar(int m) {
on top of the stack
…
}
 Allows for recursion
bar
PC = 1
m=6
foo
PC = 3
j=5
k=6
main
PC = 2
i=5
25
Implementing a stack
need an underlying collection to hold the elements
of the stack
2 basic choices
– array (native or ArrayList)
– linked list
array implementation
linked list implementation
Some of the uses for a stack are much more
interesting than the implementation of a stack
26
Array-based Stack
 A simple way of
implementing the
Stack ADT uses an
array
 We add elements
from left to right
 A variable keeps
track of the index of
the top element
Algorithm size()
return t + 1
Algorithm pop()
if isEmpty() then
throw EmptyStackException
else
tt1
return S[t + 1]
…
S
0 1 2
t
27
Queues
28
Queues
Closely related to Stacks
Like a line
– In Britain people don’t “get in line” they “queue
up”.
Queues are a first in first out data structure
– FIFO (or LILO, but that sounds a bit silly)
Add items to the end of the queue
Access and remove from the front
Used extensively in operating systems
– Queues of processes, I/O requests, and much
more
29
Queue operations
add(Object item)
– a.k.a. enqueue(Object item)
Object get()
– a.k.a. Object front()
Object remove()
– a.k.a. Object dequeue()
boolean isEmpty()
Specify in an interface, allow varied
implementations
30
Queue Example
Operation
enqueue(5)
enqueue(3)
dequeue()
enqueue(7)
dequeue()
front()
dequeue()
dequeue()
isEmpty()
enqueue(9)
enqueue(7)
size()
enqueue(3)
enqueue(5)
dequeue()
Output
Q
–
–
5
–
3
7
7
“error”
true
–
–
2
–
–
9
(5)
(5, 3)
(3)
(3, 7)
(7)
(7)
()
()
()
(9)
(9, 7)
(9, 7)
(9, 7, 3)
(9, 7, 3, 5)
(7, 3, 5)
31
Applications of Queues
Direct applications
– Waiting lists, bureaucracy
– Access to shared resources (e.g., printer)
– Multiprogramming
Indirect applications
– Auxiliary data structure for algorithms
– Component of other data structures
32
Implementation
Array-based Queue
 Use an array of size N in a circular fashion
 Two variables keep track of the front and rear
f index of the front element
r index immediately past the rear element
 Array location r is kept empty
normal configuration
Q
0 1 2
f
r
wrapped-around configuration
Q
0 1 2
r
f
33
Queue Operations
We use the
modulo operator
(remainder of
division)
Algorithm size()
return (N  f + r) mod N
Algorithm isEmpty()
return (f = r)
Q
0 1 2
f
0 1 2
r
r
Q
f
34
Queue Operations (cont.)
 Operation enqueue
throws an exception if
the array is full
 This exception is
implementationdependent
Algorithm enqueue(o)
if size() = N  1 then
throw FullQueueException
else
Q[r]  o
r  (r + 1) mod N
Q
0 1 2
f
0 1 2
r
r
Q
f
35
Queue Operations (cont.)
 Operation dequeue
throws an exception
if the queue is empty
 This exception is
specified in the
queue ADT
Algorithm dequeue()
if isEmpty() then
throw EmptyQueueException
else
o  Q[f]
f  (f + 1) mod N
return o
Q
0 1 2
f
0 1 2
r
r
Q
f
36
Queue Interface in Java
Java interface
corresponding to
our Queue ADT
Requires the
definition of class
EmptyQueueException
No corresponding
built-in Java class,
however there is
PriorityQueue
public interface Queue {
public int size();
public boolean isEmpty();
public Object front()
throws EmptyQueueException;
public void enqueue(Object o);
public Object dequeue()
throws EmptyQueueException;
}
37
Application: Round Robin
Schedulers
 We can implement a round robin scheduler using a
queue, Q, by repeatedly performing the following
steps:
1.
2.
3.
e = Q.dequeue()
Service element e
Q.enqueue(e)
The Queue
1. Deque the
next element
2 . Service the
next element
3. Enqueue the
serviced element
Shared
Service
38
Implementing a Queue
Given the internal storage container and
choice for front and back of queue what are
the Big O of the queue operations?
ArrayList
LinkedList
(Singly Linked)
LinkedList
(Doubly Linked)
enqueue
front
dequeue
isEmpty
39
Priority Queue Implementation
Sequence-based Priority Queue
 Implementation with an
unsorted list
4
5
2
 Performance:
3
1
– insert takes O(1) time
since we can insert the
item at the beginning or
end of the sequence
– removeMin and min take
O(n) time since we have
to traverse the entire
sequence to find the
smallest key
 Implementation with a
sorted list
1
2
3
4
5
 Performance:
– insert takes O(n) time
since we have to find the
place where to insert the
item
– removeMin and min take
O(1) time, since the
smallest key is at the
beginning
40
Priority Queue Applications
Priority-based OS process scheduler
41