Transcript Chapter 4

Chapter 4
The easy stuff
Lists, Stacks, and Queues
• If you only need to store a few things, the
simplest and easiest approach might be to
put them in a list
• Only if you need to search or some other
more intensive operation on the data
would a more complex structure be
needed
Goals for this Chapter
• Present some basic data structures
• Give examples of separating a logical
representation in the form of an ADT from
a physical implementation in a Data
Structure
• Illustrate the use of algorithm analysis in
the context of simple operations
Lists
• A list is a finite, ordered sequence of data items
know as elements
• Each element has a position
• This is a sequence as defined in Chapter 2
• It’s empty when it contains no elements
• The number of current elements is its length
• The first element is the head
• The last element is the tail
Basic Operations
• Must be able to insert and delete
anywhere along the list
• Should be able to gain access to an
elements value
• Must be able to create and clear the list
• Convenient to gain access to the next
element from the current one
List ADT
• In C++ we will use the notion of an
abstract class for the List
• We will increase the flexibility by making it
a template
• The abstract class does not specify how
the operations are implemented
• Given that we want to support the concept
of a sequence, the key decision embodied
in the ADT is the notion of position
The Fence
• The list will be partitioned into two sets
with a fence between them
• We will use a vertical bar to indicate where
the fence is when we need notation to
show the fence
• <4, 5, 6 | 8, 10, 11>
• After an insert
– <4, 5, 6 | 13, 8, 10, 11>
The List Abstract Class
template <class Elem> class List{
public:
virtual void clear() = 0;
virtual bool insert(const Elem&) = 0;
virtual bool append(const Elem&) = 0;
virtual bool remove(Elem&) = 0;
virtual void setStart() = 0;
virtual void setEnd() = 0;
virtual void prev() = 0;
virtual void next() = 0;
virtual int leftLength() = 0;
virtual int rightLength() = 0;
virtual bool setPos(int pos) = 0;
virtual bool getValue(Elem&) const = 0;
virtual void print() const = 0;
};
Array Based Implementation
• Contains 4 private variables
• One for maxSize, listSize, fence, and the
listArray
• Stores the elements in contiguous memory
locations
• Shifting can occur with insert and deletes
• Inserting and deleting in the average case
is Θ(n)
Linked Implementation
• Key design choice is how to implement the
fence
• Two choices:
– The first node on the right side
– The last node on the left side
• A header node can eliminate some the
special cases that arise from choosing the
second option.
• It does introduce some overhead
Comparision
• Array list size is
predetermined
• When list is small,
large amount of
space can be wasted
• Linked list waste
space with overhead
• No limit to the number
of elements in list
Breakeven Comparison
•
•
•
•
•
•
•
•
n number of elements in list
P size of pointer storage
E size of data element
D maximum number of elements stored in array
Space required for Array DE
Space required for Linked n(P+E)
n> DE/(P+E)
When P = E we get D/2 as break even point
Dictionary ADT
• The most common objective of a computer
program is to store and retrieve data
• The dictionary is defined to provide the
fundamental operations of storing records,
finding records and removing records from
a database.
• We must define concepts of a key and
comparable objects
The Dictionary ADT
template <class Key, class Elem, class
KEComp, class EEComp>
class Dictionary
{
public:
virtual void clear() = 0;
virtual bool insert(const Elem&) = 0;
virtual bool remove(const Key&, Elem&) =
0;
virtual bool removeAny(Elem&) = 0;
virtual bool find(const Key&, Elem& ) = 0;
virtual int size() = 0;
};
What are all those classes for?
• We know we need to be able to find records in the
dictionary.
• We could simply use the basic relational operators.
– This doesn’t work for complex types
• We could simply overload the basic relational operators
– This is hidden in the code
• We could require that the Elem class is inheiret off of a
class that implements a comparable method
– What about multiple keys?
Best Solution
• Allowing the user to supply their own
definitions for comparing keys to records
and records to records
• By making the class a template parameter,
we now have the requirement in the
interface
• The design is known as a “Strategy”
design pattern, since the strategy is
provided explicitly by the client
Stacks
• The stack is a list-like structure in which
elements may be inserted or removed
from only one end.
• A stack follows a LIFO access pattern
• Elements are stored and removed in
reverse order of their arrival
• Elements are pushed on the stack
• Elements are popped off the stack
Queues
• The queue is a list-like structure that
provides restricted access to its elements
• Elements are enqueued at the back
• Elements are dequed from the front
• Queues follow a FIFO access pattern