Page
1
of
11
Chapter
3
notes:
some
of
most
famous
and
incredibly
useful
ADTs
abstract
data
type
(ADT)
–
set
of
data
objects
together
with
a
set
of
operations
• No
mention
of
how
the
data
are
stored
or
how
the
operations
are
implemented
physical
data
structure
–
the
underlying
storage
mechanism
used
for
the
data
objects
Java
supports
the
implementation
of
ADTs
with
appropriate
hiding
of
implementation
details
(private
access
for
data)
stack
1–
last-‐in,
first-‐out
(or
first-‐in,
last-‐out)
web
browsing
–
history
of
pages
visited
kept
in
a
stack,
using
the
back
arrow
pops
the
stack
returning
you
to
the
most
recently
visited
page
word
processors
–
history
of
changes
kept
in
a
stack,
want
to
undo
something?
Stack
popped
to
see
what
you
did
last
method
calling
during
program
execution
–
stack
maintain
history
of
calls,
so
when
a
method
terminates,
it
knows
which
method
to
return
to
(who
its
caller
is)
parser
(part
of
compiler)
needs
a
stack
to
verify
the
syntax
of
your
program
–
stack
needed
to
match
parentheses,
for
example
stack
ADT:
(definitions
of
method
functionality
on
page
203)
Basic
operations:
pop
and
push
Other
common:
(peek
or
top)
and
isEmpty
1
Image
found
at
http://people.revoledu.com/kardi/tutorial/VB/lesson06/Stack.htm
Page
1
of
11
Page
2
of
11
May
be
relevant:
isFull,
size
Stack
interface
–
• spells
out
the
methods
that
must
be
implemented
for
any
stack;
• interface
is
implementation
independent
Assuming
a
generic
stack,
that
stores
data
of
type
E,
what
would
the
signatures
of
pop,
push,
top,
isEmpty
and
size
look
like?
Run-time
complexity
of
basic
operations?:
Operation Array Linked list
implementation implementation
int size( )
boolean isEmpty( )
void push (E elem)
E top( )
E pop( )
Page
2
of
11
Page
3
of
11
Logical
Physical
view
view
Picture
from
cs.millersville.edu
Logical
Physical
view
view
Picture
from
http://courses.cs.vt.edu/csonline/DataStructures/Lessons/StacksImplementationView/index.html
Empty stack:
top null
Page
3
of
11
Page
4
of
11
Instance
variables:
-‐-‐
an
array
of
some
CAPACITY
capacity
-‐-‐
an
int
variable
top
–
stores
index
of
last
element
pushed
-‐-‐
an
int
variable
for
size?
7
….
19
20
150
88
30
15
Picture
adapted
from
http://www.cs.grinnell.edu/~walker/courses/161.sp09/readings/reading-‐stacks-‐arrays.shtml
Empty
stack:
top
=
-‐1
Page
4
of
11
Page
5
of
11
Linked implementation of stack:
top
Physical
view
Logical
view
Picture
from
http://courses.cs.vt.edu/csonline/DataStructures/Lessons/StacksImplementationView/index.html
What instance data & types would we need for
this implementation?
_________________________
_________________________
_________________________
Page
5
of
11
Page
6
of
11
queue2
–
first-‐in
first
out
(like
a
line
of
polite
students
waiting
for
lunch);
add
data
on
one
end,
remove
from
the
other
end
jobs
waiting
on
the
CPU
–
(assuming
no
priority
system)
first
job
in
line
is
done
next
print
jobs
waiting
on
the
printer
to
be
available
orders
waiting
to
be
shipped
queue
ADT:
Basic
operations:
enqueue,
dequeue
Other
operations:
isEmpty,
front,
back
May
be
relevant:
size
Queue
interface
–
• spells
out
the
methods
that
must
be
implemented
for
any
queue;
• as
always….interface
is
implementation
independent
2
Image
from
http://brendan.enrick.com/post/understanding-‐the-‐queue-‐data-‐structure-‐using-‐a-‐simple-‐c-‐
implementation.aspx
Page
6
of
11
Page
7
of
11
Queue
logical
view:
Standard
array
implementation
–
a
challenge
since
front
and
rear
move.
Typical
to
view
array
as
if
it
is
circular.
Picture
from
http://www.grasshoppernetwork.c
om/Technical/Share/?q=node/168
Page
7
of
11
Page
8
of
11
Linked
list
implementation
of
a
queue:
Picture
from
http://people.cis.ksu.edu/~schm
idt/300s05/Lectures/Week5aa.h
tml
enqueue-‐ing
new
Node
v:
v
rear.setNext(v);
rear = v;
“q”
dequeue-‐ing
a
node:
Node retrieved = front;
front = front.getNext( );
retrieved.setNext(null);
Page
8
of
11
Page
9
of
11
Run-‐time
complexity
of
basic
queue
operations:
Operation
“circular”
array
Linked
list
implementation
implementation
int
size(
)
boolean
isEmpty(
)
E
front(
)
void
enqueue(
)
E
dequeue(
)
Page
9
of
11
Page
10
of
11
deque
–
(pronounced
“deck”)
double-‐ended
queue;
supports
insertion
and
deletion
at
both
ends
The
deque
ADT:
Basic:
addFirst,
addLast,
removeFirst,
removeLast
Other:
getFirst,
getLast,
size,
isEmpty
Possible
implementations:
Array,
linked
list
(singly
or
doubly)
Operation
array
Linked
list
implementation
implementation
int
size(
)
boolean
isEmpty(
)
E
getFirst(
)
E
getLast(
)
void
addFirst(
)
void
addLast(
)
E
removeFirst(
)
E
removeLast(
)
Page
10
of
11
Page
11
of
11
Thinking
back
on
the
OrderedList
ADT
from
assignments
1
&
2
Operation
Array
implementation
Linked
list
implementation
insert
remove
retrieve
find
Page
11
of
11
