Transcript Algorithms and Data Structures

Algorithms and Data
Structures
Lecture VI
Simonas Šaltenis
Aalborg University
[email protected]
October 2, 2003
1
This Lecture

Abstract Data Types


Vector
List (Sequence)


Doubly linked list implementation
Dynamic set ADTs




Stack
Queue
Deque
Priority Queue
October 2, 2003
2
Abstract Data Types (ADTs)

ADT is a mathematically specified entity
that defines a set of its instances, with:


a specific interface – a collection of signatures
of operations that can be invoked on an
instance,
a set of axioms (preconditions and
postconditions) that define the semantics of the
operations (i.e., what the operations do to
instances of the ADT, but not how)
October 2, 2003
3
ADTs
Why do we talk about ADTs in this course?


Allows to break work into peaces that can be worked
on independently – without compromising
correctness



They serve as specifications of requirements for the building
blocks of solutions to algorithmic problems
ADTs encapsulate data structures and algorithms
that implement them
Provides a language to talk on a higher level of
abstraction
October 2, 2003
4
ADTs
Why do we talk about ADTs in this
course?


Allows to separate the concerns of
correctness and the performance analysis
1.
2.
3.
Design the algorithm using an ADT
Count how often different ADT operations are
used
Choose implementations of ADT operations
October 2, 2003
5
ADT operations

Types of ADT operations:

Constructors



Access functions


No preconditions
Postconditions describe the “value” of the ADT
instance, by telling what the access functions return
No postconditions
Manipulation procedures

Postconditions describe the “value” of the ADT
instance, by telling what the access functions return
October 2, 2003
6
ADTs for basic data structures

ADTs encapsulating basic data structures:


Vectors encapsulate arrays
Lists (or sequences) encapsulate linear linked
structures
October 2, 2003
7
Vector ADT

Vector of integers ADT:

Constructor


Access functions:



make():Vector
size():int
elemAtRank(r:int):int
Manipulation procedures:



replaceAtRank(r:int, e:int)
insertAtRank(r:int, e:int)
removeAtRank(r:int)
October 2, 2003
8
Vector ADT

make():Vector


elemAtRank(r:int):int


Post-conditions: size() = 0
Preconditions: 0 < r size()
replaceAtRank(r:int, e:int)


Preconditions: 0 < r size()
Postconditions: (let A be an instance of the vector
before the operation, and B after the operation)



A.size() = B.size()
B.elemAtRank(r) = e
For each i (0 < i size(), i r)

October 2, 2003
B.elemAtRank(r) = A.elemAtRank(r)
9
Implementation of Vector ADT

Array implementation of Vector ADT:
Vector operation
Time complexity
make()
O(1)
size()
O(1)
elemAtRank(r)
O(1)
replaceAtRank(r,e)
O(1)
insertAtRank(r,e)
O(n)
removeAtRank(r)
O(n)
October 2, 2003
10
List (Sequence) ADT

Vectors implemented as arrays are



Lists (implemented using linked data structures)




good for random access J,
but bad for insertions and deletions L
good for insertion and deletion J
but bad for accessing elements by their rank L
Instead of the rank, we have a concept of
position (abstraction of a pointer)
Position ADT:


One operation: element():int
Special instance: NIL
October 2, 2003
11
List (Sequence) ADT

List ADT:

Constructor


make():List
Access functions:





isEmpty():boolean
first():Position
last():Position
before(p:Position):Position
after(p:Position):Position
October 2, 2003
12
List (Sequence) ADT

List ADT:

Manipulation procedures:






replace(p:Position, e:int)
insertFirst(e:int)
insertLast(e:int)
insertBefore(p:Position, e:int)
insertAfter(p:Position, e:int)
remove(p:Position)
October 2, 2003
13
Implementation of List ADT

Singly linked list – nodes (data, pointer)
connected in a chain by links
October 2, 2003
14
Implementation of List ADT

Singly linked list implementation of the List
ADT
List ADT operation
Time
complexity
isEmpty()
O(1)
first(), last(), insertFirst(), insertLast(p)
O(1)
after(p), insertAfter()
O(1)
before(p), insertBefore(p)
O(n)
replace(p,e)
O(1)
remove(p)
O(n)
October 2, 2003
15
Doubly Linked Lists


To implement all of the List ADT operations in
constant time we use doubly linked lists.
A node of a doubly linked list has a next and a
prev link
October 2, 2003
16
Dynamic Set ADTs

We will deal with ADTs, instances of which
are sets of some type of elements.


Operations are provided that change the set
We call such class of ADTs dynamic sets
October 2, 2003
18
Example: Set ADT (1)

An example: Set ADT

Constructor:


Access functions




make():Set
isEmpty(s:Set):boolean
size(s:Set):int
isIn(s:Set, v:element):boolean
Manipulation procedures


insert(s:Set, v:element)
delete(s:Set, v:element)
October 2, 2003
19
Example: Set ADT (2)

Postconditions for make, insert and
delete:





isIn(make(), v) = false
isIn(insert(S, v), v) = true
isIn(insert(S, u), v) = isIn(S, v), if v u
isIn(delete(S, v), v) = false
isIn(delete(S, u), v) = isIn(S, v), if v u
October 2, 2003
20
Dynamic Set ADTs
Dynamic set ADTs
Stacks,
Queues,
Deques
October 2, 2003
Sets,
Bags
Priority
Queues
Dictionaries
(Maps)
21
Basic ADTs

Basic dynamic set ADTs, where access to
elements of the set is restricted, based on
the order of operations:



Queue
Deque
Stack
October 2, 2003
22
Stack ADT



A stack is a container of objects that are
inserted and removed according to the
last-in-first-out (LIFO) principle.
Objects can be inserted at any time, but
only the last (the most-recently inserted)
object can be removed.
Inserting an item is known as “pushing”
onto the stack. “Popping” off the stack is
synonymous with removing an item.
October 2, 2003
23
Stacks (2)

A PEZ ® dispenser as an analogy:
October 2, 2003
24
Stacks(3)

The stack ADT:

Constructor:


Access functions:




make():Stack – Creates a new stack
top(S:Stack):element
size(S:Stack):integer
isEmpty(S:Stack): boolean
Manipulation procedures:


push(S:Stack, o:element):Stack - Inserts o onto top of S
pop(S:Stack):Stack - Removes the top object of stack S
October 2, 2003
25
Stacks(4)

push(S:Stack, o:element):Stack

Postconditions:




isEmpty(S) = false
pop(push(S, v)) = S
top(push(S, v)) = v
pop(S:Stack):Stack

Preconditions:


isEmpty(S) = false
Postconditions:

push(pop(S), top(S)) = S
October 2, 2003
26
An Array Implementation



Create a stack using an array by specifying a
maximum size N for our stack.
The stack consists of an N-element array S and
an integer variable t, the index of the top
element in array S.
Array indices start at 0, so we initialize t to -1
October 2, 2003
27
An Array Implementation (2)

Pseudo code
Algorithm size()
return t+1
Algorithm isEmpty()
return (t<0)
Algorithm top()
if isEmpty() then
return Error
return S[t]
October 2, 2003
Algorithm push(o)
if size()==N then
return Error
t=t+1
S[t]=o
Algorithm pop()
if isEmpty() then
return Error
S[t]=null
t=t-1
28
An Array Implementation (3)


The array implementation is simple and
efficient (methods performed in O(1)).
There is an upper bound, N, on the size of
the stack. The arbitrary value N may be too
small for a given application, or a waste of
memory.
October 2, 2003
29
Using List ADT

We can use List ADT implemented as singly
linked list to implement Stack,

all operations O(1)
Stack ADT
Operation
List ADT operation
size()
-
isEmpty()
isEmpty()
top()
first()
push(o)
insertFirst(o)
pop()
remove(first())
October 2, 2003
30
Queue ADT



A queue differs from a stack in that its insertion and
removal routines follows the first-in-first-out (FIFO)
principle.
Elements may be inserted at any time, but only the
element which has been in the queue the longest may be
removed.
Elements are inserted at the rear (enqueued) and
removed from the front (dequeued)
Front
Rear
Queue
October 2, 2003
31
Queues (2)

The queue ADT:

Constructor:


Access functions:




make():Queue – Creates an empty queue
size(S:Queue):integer
isEmpty(S:Queue):boolean
front(S:Queue):element
Manipulation procedures:


Enqueue(S:Queue, o:element):Queue - Inserts object o at
the rear of the queue
Dequeue(S:Queue):Queue - Removes the object from the
front of the queue
October 2, 2003
32
An Array Implementation



Create a queue using an array in a circular
fashion
A maximum size N is specified.
The queue consists of an N-element array Q and
two integer variables:


f, index of the front element (head – for dequeue)
r, index of the element after the rear one (tail – for
enqueue)
October 2, 2003
33
An Array Implementation (2)

“wrapped around” configuration

what does f=r mean?
October 2, 2003
34
An Array Implementation (3)

Pseudo code
Algorithm size()
return (N-f+r) mod N
Algorithm isEmpty()
return size()=0
Algorithm front()
if isEmpty() then
return Error
return Q[f]
October 2, 2003
Algorithm dequeue()
if isEmpty() then
return Error
Q[f]=null
f=(f+1)modN
Algorithm enqueue(o)
if size = N - 1 then
return Error
Q[r]=o
r=(r +1)modN
35
Using List ADT


List ADT implemented as a singly linked list
can be used
dequeue(S): S.remove(S.first())
October 2, 2003
36
Using List ADT

Enqueue(S, e): S.insertLast(e)
October 2, 2003
37
Double-Ended Queue ADT



A double-ended queue, or deque, supports
insertion and deletion from the front and rear
Can be implemented with List ADT implemented
as doubly linked list
The deque supports six fundamental methods






insertFirst(S:Deque, o:element):Deque
insertLast(S:Deque, o:element):Deque
removeFirst(S:Deque):Deque
removeLast(S:Deque):Deque
first(S:Deque):element
last(S:Deque):element
October 2, 2003
38
Priority Queues


A priority queue is an ADT(abstract data type) for
maintaining a set S of elements, each with an
associated value called key
A PQ supports the following operations



insert(S,x) insert element x in set S (SS{x})
maximum(S) returns the element of S with the
largest key
extract-Max(S) returns and removes the element of
S with the largest key
October 2, 2003
39
Priority Queues (2)

Removal of max takes constant time on top
of Heapify (lg n)
October 2, 2003
40
Priority Queues (3)

Insertion of a new element


enlarge the PQ and propagate the new
element from last place ”up” the PQ
tree is of height lg n, running time: (lg n)
October 2, 2003
41
Priority Queues (4)
October 2, 2003
42
Priority Queues (5)

Applications:




job scheduling shared computing resources
(Unix)
Event simulation
As a building block for other algorithms
We used a heap in an array to implement
PQ. Other implementations are possible
October 2, 2003
43
Next Week

Hashing
October 2, 2003
44