Transcript Stacks and Queues

Stacks and Queues
Starring: IndexOutOfBOundsException
Co-Starring: NoSuchElementException
1
Purpose:
In this lecture series we will discuss
two more ADTs
The Stack and Queue data types are
used to process data in a linear fashion
2
Resources:
Barrons Chapter 9 p.300 (EXCEPT
Priority Queues p.305-309)
Java Essentials Chapter 19 p.757
Java Essentials Study Guide Chapter
16 p.281
Java Methods Chapter 3 p.61
3
Handouts:
1. Stack and Queue Interfaces &
Implementations
2.The Following Java Code:
Stack.java
Queue.java
ArrayStack.java
ListQueue.java
4
Intro:
A STACK is a linearly ordered list
A STACK is a data structure used for
storing and retrieving data elements in
such a way that the element stored
last will be retrieved first.
LIFO --- last in first out
5
Intro:
A QUEUE is a data structure used for
temporary storage from which the data
elements are retrieved in the same
order as they were stored.
FIFO – first in first out
Used for processing events that have
to be processed in the order of their
arrival (events are buffered in the
queue)
6
Stacks:
Think of the mountain of clothes piled
in a corner of your room
As you hurry to dress so as not to be
late for school, you begin your search
from the TOP of the clothes pile
The last stuff to be thrown on to the
pile is the first to be examined
This is a “messy” stack
7
TO implement a Stack ADT, you must
provide a way to store (push) and
remove (pop) elements from a Stack
Elements on the stack should be of the
same type (or in the same class
hierarchy)
A Stack has no limits as to its size
8
TO add an element on to the stack you
“Push” that item and it goes to the
front of the stack
TO remove an element from the stack,
you can only “Pop” off the element
currently at the top of the stack
PUSH --- adds elements to the top of
the stack
POP --- removes the element from the
top of the stack
9
These operations should be in
Constant time O(1)
Other behaviors of the Stack should
return the top element of the Stack
without removing it (peekTop) and to
see if the Stack has any elements left in
it (isEmpty)
10
For testing purposes, we will use the
following as the standard Stack
Interface (similar to ListNode when
dealing with Linked Lists)
11
public interface Stack
{
// postcondition: returns true if stack is empty, false otherwise
boolean isEmpty();
// precondition: stack is [e1, e2, ..., en] with n >= 0
// postcondition: stack is [e1, e2, ..., en, x]
void push(Object x);
// precondition: stack is [e1, e2, ..., en] with n >= 1
// postcondition: stack is [e1, e2, ..., e(n-1)]; returns en
//
throws an unchecked exception if the stack is empty
Object pop();
// precondition: stack is [e1, e2, ..., en] with n >= 1
// postcondition: returns en
//
throws an unchecked exception if the stack is empty
Object peekTop();
}
12
RUNTIME STACK
Remember the “runtime stack” ?
It uses stacks to handle function calls
The stack holds the function specific
data PLUS the memory address of the
NEXT instruction to execute
Elements are “on the stack”
13
The stack is controlled by the two
operations: PUSH & POP
Possible Implementation of a Stack is a
singly linked list enhanced by an
additional reference to the tail of the list
Elements are added at the tail of the list
and removed at the head of the list.
However, lets look at an ArrayList
Implementation
14
public class ArrayStack implements Stack
{
private ArrayList array;
public ArrayStack()
{
array = new ArrayList();
}
public void push(Object x)
{
array.add(x);
}
public Object pop()
{
return array.remove(array.size() - 1);
}
public Object peekTop()
{
return array.get(array.size() - 1);
}
public boolean isEmpty()
{
return array.size() == 0;
}
}
15
 To use the Stack:
// SPVM
MyStack mS = new ArrayStack();
mS.push(new String (“Billy”);
mS.push(new String (“Joe”);
mS.push(new String (“Bob”);
mS.push(new String (“Sally”);
mS.push(new String (“Lucy”);
 The Stack Should now look like this:
Lucy
Sally
Bob
Joe
Billy
16
Object o = mS.pop( );
String s = (String)mS.pop( );
String y = (String)mS.peekTop( );
Boolean empty = mS.isEmpty( );
The Stack Should now look like this:
Bob
Joe
Billy
The String y contains “Bob”
The Boolean empty is False
17
Errors:
The pop and peekTop methods can
throw an Unchecked Exception
IndexOutOfBOundsException or
NoSuchElementException
in cases where the stack is empty
18
If you use the ArrayList or the
LinkedList Java class to implement
your Stack, then these errors are
handled , for you, from within these
classes
19
Queues:
Its lunch time and you leave class early
to get into the food line
“Dr.Nick” dashes as fast as he can and
is first to grab a tray and get into line
After Dr.Nick, “Naum” trips over a floor
tile and skins his knee
20
As a result, “Alden” stops to help wipe
away Naum’s tears and to give him a
Scooby Doo bandaid
So, Alden winds up behind Dr.Nick and
Naum follows
Since the line is implemented as a
Queue, Dr.Nick gets the best lunch
choices and Naum gets the crumbs
21
TO implement a Queue ADT, you must
provide a way to store (enqueue) and
remove (dequeue) elements from a
Queue
Elements on the Queue should be of the
same type (or in the same class
hierarchy)
A Queue has no limits as to its size
22
TO add an element on to the Queue you
“enqueue” that item and it goes to the
end of the Queue
TO remove an element from the Queue,
you can only “dequeue” off the element
currently at the top of the Queue
23
ENQUEUE --- adds elements to the end
of the Queue
DEQUEUE --- removes the element from
the top of the Queue
These operations should be in Constant
time O(1)
24
Other behaviors of the Queue should
return the top element of the Queue
without removing it (peekFront) and to
see if the Queue has any elements left in
it (isEmpty)
For testing purposes, we will use the
following as the standard Queue
Interface:
25
public interface Queue
{
// postcondition: returns true if queue is empty, false otherwise
boolean isEmpty();
// precondition: queue is [e1, e2, ..., en] with n >= 0
// postcondition: queue is [e1, e2, ..., en, x]
void enqueue(Object x);
// precondition: queue is [e1, e2, ..., en] with n >= 1
// postcondition: queue is [e2, ..., en]; returns e1
//
throws an unchecked exception if the queue is empty
Object dequeue();
// precondition: queue is [e1, e2, ..., en] with n >= 1
// postcondition: returns e1
//
throws an unchecked exception if the queue is empty
Object peekFront();
}
26
Ring Buffer
An array used in a circular manner.
Adjust the pointer that defines the
“logical” first array element.
The state of the queue is maintained with
the help of 2 indices, FRONT and
REAR.
27
Front points to the first element in the
queue (returned by the next call to the
dequeue)
Rear points to the empty slot following
the last stored element.
Enqueue method stores the next
element in the slot pointed to by the rear
and increments the rear index.

28
PC’s have a keyboard queue
implemented as a ring buffer. When a
key is pressed its code does not go
directly to the active program but is
placed in the keyboard buffer until the
program requests it.
29
Lets look at a LinkedList
Implementation:
30
public class ListQueue implements Queue
{
private LinkedList list;
public ListQueue()
{
list = new LinkedList();
}
public void enqueue(Object x)
{
list.addLast(x);
}
public Object dequeue()
{
return list.removeFirst();
}
public Object peekFront()
{
return list.getFirst();
}
public boolean isEmpty()
{
return list.size() == 0;
}
}
31
 To use the Queue:
// SPVM
MyQueue mQ = new ListQueue();
mQ.enqueue(new String (“Billy”);
mQ.enqueue(new String (“Joe”);
mQ.enqueue(new String (“Bob”);
mQ.enqueue(new String (“Sally”);
mQ.enqueue(new String (“Lucy”);
 The Stack Should now look like this:
Billy
Joe
Bob
Sally
Lucy
32
Object o = mQ.dequeue( );
String s = (String)mQ.dequeue( );
String y = (String)mQ.peekFront( );
Boolean empty = mQ.isEmpty( );
The Stack Should now look like this:
Bob
Sally
Lucy
The String y contains “Bob”
The Boolean empty is False
33
Queues are best when simulating bank
lines, or any other system where there is
a “First Come First Served” basis
34
Lets look at Barrons Redial Telephone
Feature on Page 305
35
TPS: Implement a Queue using an
Array (or ArrayList)
Implement the Possible Unchecked
Exceptions
Draw array implementation on board
(RingBuffer)
36
AP AB Subset Requirements:
Although there is no standard Java
Interface we need to be able to work
with the AP interfaces for Stacks and
Queues (handouts)
Students are also responsible for
understanding that these ADT’s can be
implemented as an array or a linked
list, although you will NOT be tested on
any SPECIFIC implementation
37
AP AB Subset Requirements:
For our reference purposes we will look
at an Array implementation of a stack
called ArrayStack.java and we will look
at a LinkedList implementation of a
Queue called ListQueue.java
38
AP AB Subset Requirements:
You will see Multiple Choice questions
regarding analysis of Stack and Queue
implementations and processes
Multiple Choice questions may focus
on your ability to evaluate the
effectiveness of and to determine the
best use of Stacks and Queues
39
Projects:
Barrons M/C Questions Chapter 9 p.310
Do ALL Questions Except the following:
# 14, 15




Decimal to Binary
Expression
McDonalds
Palendrome
40
TEST FOLLOWS
COMPLETION OF
PROJECTS !!!
41