Transcript ppt

Stuff
• Solution to midterm is posted. Marking has just
started…
• Lab for this week is not posted (yet?).
• Final exam (full of good news today!) is scheduled
on April 27 (Thursday) at 2pm in Jock Hardy
(Clergy). 3 hours long.
Winter 2006
CISC121 - Prof. McLeod
1
Last Time
• Replacing sparse tables with linked lists.
• Started Stacks and Queues
Winter 2006
CISC121 - Prof. McLeod
2
Today
• Finish looking at stacks
• Queues
Winter 2006
CISC121 - Prof. McLeod
3
Stacks – Cont.
• Another example are those plate dispensers in
cafeterias.
• A stack follows the “Last In, First Out” or “LIFO”
principle.
• A stack would have the following operations:
–
–
–
–
–
–
clear() – clear the stack.
isEmpty() – check to see if the stack is empty.
isFull() – check to see if the stack is full.
push(element) - put the element on top of the stack.
pop() – take the topmost element from the stack.
peek() – return the topmost element in the stack
without removing it.
Winter 2006
CISC121 - Prof. McLeod
4
Stacks – Cont.
• See IntStack.java for a linked list implementation.
• See IntStackSmaller.java for an even smaller
linked list implementation!
• Some features of IntStackSmaller:
– An inner class for the node.
– Only public methods are:
• clear ()
• boolean isEmpty ()
• push (int)
• int pop ()
• int peek ()
Winter 2006
CISC121 - Prof. McLeod
5
Stacks – Cont.
• A stack can also be implemented with an ArrayList
or even an array (But not as well, IMHO).
• Note that none of the stack operations require
iteration through the linked list.
Winter 2006
CISC121 - Prof. McLeod
6
ArrayList Stack Implementation
• See ALStack.java
• (Note that we are assuming the user will check to
see if the stack is empty before calling a “pop()”
operation. What else could we do?)
• “Features”:
– We need to keep track of position in the ArrayList.
– We could use (but did not) the automatic “un-boxing”
and boxing feature in Java 5.0 (huh?).
Winter 2006
CISC121 - Prof. McLeod
7
Array Stack Implementation
• See ArrayStack.java
• A bit clumsy?
• Of the three implementations, which is the best?
Winter 2006
CISC121 - Prof. McLeod
8
A Stack in Use
• How to add numbers that are too large to be
stored in a long type variable?
• See LongAddition.java
Winter 2006
CISC121 - Prof. McLeod
9
The Stack<E> Class in java.util
• java.util has a “Stack” class that implements the
above methods using a Vector as the storage
object.
• (A Vector is like an ArrayList…)
• Stack is a sub-class of Vector, and as such,
inherits all the Vector methods.
Winter 2006
CISC121 - Prof. McLeod
10
The Stack<E> Class – Cont.
• Unique Stack methods:
boolean empty() // same as isEmpty
Object peek()
Object pop()
Object push(element)
int search(target) // returns position of
target in stack, if not found –1 is
returned.
Stack() // constructor
Winter 2006
CISC121 - Prof. McLeod
11
The Stack<E> Class – Cont.
• In Stack, “push” also returns a reference to the
Object added to the stack, so both peek and
push can change that topmost object on the
stack.
• Since Stack “is a” Vector, methods like
“setElementAt” and “removeElementAt” can
be used on stack elements – but these methods
would be illegal by our definition of what a stack
is!
• Also, when Vector’s are used to implement the
stack, re-sizing of the Vector can greatly slow
down the push method.
Winter 2006
CISC121 - Prof. McLeod
12
The Stack<E> Class – Cont.
• For these reasons it is better to implement a stack
as we have done above, using a private linked list
(best) or a private array(next best) as a data
object within the definition of the class.
• Implementing a stack using a linked list defined
using an inner class for the node provides better
information hiding than the Stack class.
Winter 2006
CISC121 - Prof. McLeod
13
Queues
• A queue is just a lineup, like at your favorite movie
theatre.
• It would use the “FIFO” principle – “First In, First
Out”.
• It would have the following operations:
–
–
–
–
–
–
clear() – clear the queue.
isEmpty() – check to see if the queue is empty.
isFull() – check to see if the queue is full.
enqueue(element) - put the element at the end of the queue.
dequeue() – take the first element from the queue.
firstEl() – return the first element in the queue without removing it.
Winter 2006
CISC121 - Prof. McLeod
14
Aside: “isFull()”
• Our implementations of stacks and queues do not
have an “isFull()” method, because they do
not need one.
• If you did need such a method to model a stack or
queue that is limited in size, how would you do it?
• Suppose the maximum size is provided when the
stack or queue is created (in the constructor).
Winter 2006
CISC121 - Prof. McLeod
15
Queues - Cont.
• Does a linked list implementation of a queue
require both head and tail links?
YUP!
• If a singly linked list is used would you enqueue to
the head or the tail? Why?
- enqueue to tail!
- easier to remove head node than to remove tail
node in singly linked list for dequeue operation
Winter 2006
CISC121 - Prof. McLeod
16
Queues – Cont.
• A queue can easily be implemented using a singly
linked list with a head and tail.
• (See IntQueue.java, for example)
• A queue, in code, is often used as part of a model
of a real-world process.
• In the “real-world” queues are everywhere –
Airport runways, McDonalds, banks, assembly
lines, etc.
Winter 2006
CISC121 - Prof. McLeod
17
Queues – Cont.
• How would you implement a queue with an
ArrayList or an array?
• Not so easy, right?
• A “circular array” can be used, with variables that
point to the first and last occupied positions in the
array.
• If “last” moves to the end of the array, it can be
wrapped back to the beginning.
• Linked lists really are the best way to implement
a queue.
Winter 2006
CISC121 - Prof. McLeod
18
Queues – Priority Queue
• A Priority Queue is just a queue where the
elements are also given a priority. In this case, an
element with a higher priority can be removed
before the element that is “first” in the the queue,
when the first element is of a lower priority.
• (Like how an ambulance gets through traffic…)
Winter 2006
CISC121 - Prof. McLeod
19
Back to Stacks - Activation Frames
• Stacks are an integral part of computer architecture.
• For example, Java byte code is run by the “Java Virtual
Machine”, or “JVM”.
• The JVM is stack – based.
• Each thread (or process…) in the JVM has its own private
run-time stack in memory (our programs are “single
threaded”).
• Each run-time stack contains “activation frames” – one
for each method that has been activated.
• Only one activation frame (or method) can be active at a
time for each thread.
• An activation frame is created, or “pushed”, every time a
method is invoked. When the method is completed, the
frame is popped off the stack.
Winter 2006
CISC121 - Prof. McLeod
20
Activation Frames
• An activation frame (or “stack frame” or “activation
record”) contains (among other things):
– All local variables.
– A link to the frame of the calling method, so that control
can be returned to line of code in the caller immediately
after the method call.
– Information for catching exceptions.
– An “operand stack”, which is another stack that is used
by the JVM as a source of arguments and a repository
of results.
• An understanding of how this particular stack
works will help to explain how recursive
methods work…
Winter 2006
CISC121 - Prof. McLeod
21
Demonstration
• Run “RunTimeStackDemo.java” in debug mode,
stepping though method calls and observe thread
stack display.
Winter 2006
CISC121 - Prof. McLeod
22
Summary - Stacks & Queues
• We will use the thread stack to help explain how
recursion works - later...
• Stacks & Queues are often used to model realworld processes.
• Providing an easy-to-use stack or queue object
makes the modeling effort easier.
• Now we have to move on to something
completely different!
Winter 2006
CISC121 - Prof. McLeod
23