Transcript Elementary Data Structures

Analysis & Design of
Algorithms
(CSCE 321)
Prof. Amr Goneid
Department of Computer Science, AUC
Part R1. Elementary Data
Structures
Prof. Amr Goneid, AUC
1
Elementary Data Structures




Linked Lists
Stacks
Queues
Helpful Links:
Link to programs in the text book:
http://www.cise.ufl.edu/~raj/PList.html
Link to Data Structures and Algorithms:
http://cpp.datastructures.net/presentations/
Prof. Amr Goneid, AUC
2
1. The Linked List
Current
head
Last NULL
First
prev
data
cursor
next
Prof. Amr Goneid, AUC
3
Demo
http://www.cosc.canterbury.ac.nz/people/
mukundan/dsal/LinkListAppl.html
Prof. Amr Goneid, AUC
4
Variations on Linked Lists
The Circular List:
head
tail
cursor
Notice that tail->next == head
Prof. Amr Goneid, AUC
5
Variations on Linked Lists
The Doubly Linked List
back
next
cursor
To advance: cursor = cursor->next;
To back : cursor = cursor->back;
Prof. Amr Goneid, AUC
6
Variations on Linked Lists
 The Circular Doubly Linked List
 The 2-D List:
Prof. Amr Goneid, AUC
7
2. Stacks
 A simple data container consisting of a linear list
of elements
 Access is by position (order of insertion)
 All insertions and deletions are done at one end,
called top
 Last In First Out (LIFO) structure
 Two basic operations:
push: add to top
pop: remove from top
Prof. Amr Goneid, AUC
8
Example
push
top
top
++top
top
top
top-pop
Prof. Amr Goneid, AUC
9
Demo
http://www.cosc.canterbury.ac.nz/people/
mukundan/dsal/StackAppl.html
Prof. Amr Goneid, AUC
10
Some Stack Applications
 Run-time
stack used in function calls
 Page-visited history in a Web browser
 Undo sequence in a text editor
 Removal of recursion
 Conversion of Infix to Postfix notation
 Evaluation of Postfix expressions
 Reversal of sequences
 Checking for balanced symbols
Prof. Amr Goneid, AUC
11
Stack Class Operations
 construct: construct an empty stack
 stackIsEmpty




 bool : return True if stack
is empty
stackIsFull  bool : return True if stack is
full
push(el) : add element (el) at the top
pop(el): retrieve and remove the top element
stackTop(el): retrieve top element without
removing it
Prof. Amr Goneid, AUC
12
A Stack Class Definition
 The stack may be implemented as a
dynamic array.
 The capacity (MaxSize) will be input as
a parameter to the constructor
 The stack ADT may be implemented as
a template class to allow for different
element types.
Prof. Amr Goneid, AUC
13
A Stack Class Definition
// File: Stackt.h
// Stack template class definition.
// Dynamic array implementation
#ifndef STACKT_H
#define STACKT_H
template <class Type>
class Stackt
{
public:
Stackt (int nelements = 128);
Stackt (const Stackt <Type> &);
~Stackt ();
// Constructor
// Copy Constructor
// Destructor
Prof. Amr Goneid, AUC
14
A Stack Class Definition
// Member Functions
void push(Type );
void pop(Type &);
void stackTop(Type &) const;
bool stackIsEmpty() const;
bool stackIsFull() const;
private:
Type *stack;
int top, MaxSize;
// Push
// Pop
// retrieve top
// Test for Empty stack
// Test for Full stack
// pointer to dynamic array
};
#endif // STACKT_H
#include "Stackt.cpp"
Prof. Amr Goneid, AUC
15
Linked Stacks
A
stack can also be implemented as a
linked structure.
 Requires more space than array
implementations, but more flexible in size.
 Easy to implement because operations are
at the top (in this case the head node)
Prof. Amr Goneid, AUC
16
Node Specification
// The linked structure for a node can be
// specified as a Class in the private part of
// the main stack class.
class node
// Hidden from user
{
public:
Type e;
// stack element
node *next;
// pointer to next node
}; // end of class node declaration
typedef node * NodePointer;
NodePointer top;
// pointer to top
Prof. Amr Goneid, AUC
17
Push Operation
First
Last
top
3
pnew
2
New
1
push(v):
NodePointer pnew = new
node ;
pnew->e = v;
pnew->next = top;
top = pnew;
Prof. Amr Goneid, AUC
18
Pop Operation
1
top
cursor
3
2
pop(v):
v = top->e;
cursor = top;
top = top->next;
delete cursor;
Prof. Amr Goneid, AUC
19
Linked Stack Class
// File: StackL.h
// Linked List Stack class definition
#ifndef STACKL_H
#define STACKL_H
template <class Type>
class StackL
{
public:
StackL();
~StackL();
void push(Type );
void pop(Type &);
// Constructor
// Destructor
// Push
// Pop
Prof. Amr Goneid, AUC
20
Linked Stack Class
void stackTop(Type &) const; // retrieve top
bool stackIsEmpty() const;
// Test for Empty stack
private:
// Node Class
class node
{
public:
Type e;
// stack element
node *next;
// pointer to next node
}; // end of class node declaration
Prof. Amr Goneid, AUC
21
Linked Stack Class
typedef node * NodePointer;
NodePointer top;
// pointer to top
};
#endif // STACKL_H
#include "StackL.cpp"
Prof. Amr Goneid, AUC
22
Analysis of Stack Operations
 All operations are O(1)
Prof. Amr Goneid, AUC
23
Stack Template Classes
 The CSCI 321 course web site contains full
definitions and implementations of :

Stackt template class: stack class with
dynamic array implementation
 StackL template class: stack class with linked
implementation
Prof. Amr Goneid, AUC
24
3. Queues
 A simple data container consisting of a linear list
of elements
 Access is by position (order of insertion)
 Insertions at one end (rear) , deletions at another
end (front)
 First In First Out (FIFO) structure
 Two basic operations:
enqueue: add to rear
dequeue: remove from front
Prof. Amr Goneid, AUC
25
An Illustration
4
1 2 3
1 2 3
Enqueue
1
1 2 3 4
2 3 4
Dequeue
Prof. Amr Goneid, AUC
26
Enqueue and Dequeue
o
o
o
When last array element is reached, we move back to start
The queue is viewed as a circular array
o To enqueue:
rear = (rear + 1) % size
o To dequeue:
front = (front + 1) % size
Both rear and front advance clockwise
Prof. Amr Goneid, AUC
27
Demo
http://www.cosc.canterbury.ac.nz/people/
mukundan/dsal/QueueAppl.html
Prof. Amr Goneid, AUC
28
Some Queue Applications
 Simulation
of waiting lines
 Simulation of serviceable events
 Job scheduling
 Input/Output Buffering
 Multiprogramming
Prof. Amr Goneid, AUC
29
Queue Class Operations
 construct: construct an empty queue
 queueIsEmpty





 bool : return True if queue is
empty
queueIsFull  bool : return True if queue is full
enqueue(el) : add element (el) at the rear
dequeue(el): retrieve and remove the front element
queueFront(el): retrieve front without removing it
queueLength  int : return the current queue length
Prof. Amr Goneid, AUC
30
A Queue Class Definition
 The queue may be implemented as a
dynamic array.
 The capacity (MaxSize) will be input as
a parameter to the constructor.
 The queue ADT may be implemented
as a template class to allow for different
element types.
Prof. Amr Goneid, AUC
31
A Queue Class Definition
// File: Queuet.h
// Queue template class definition
// Dynamic array implementation
#ifndef QUEUET_H
#define QUEUET_H
template <class Type>
class Queuet
{
public:
Queuet (int nelements = 128);
Queuet (const Queuet <Type> &);
~Queuet ();
Prof. Amr Goneid, AUC
// Constructor
// Copy Constructor
// Destructor
32
A Queue Class Definition
// Member Functions
void enqueue(Type );
void dequeue(Type &);
void queueFront(Type &) const;
bool queueIsEmpty() const;
bool queueIsFull() const;
int queueLength() const;
private:
Type *queue;
int front, rear, count, MaxSize;
// Add to rear
// Remove from front
// Retrieve front
// Test for Empty queue
// Test for Full queue
// Queue Length
// pointer to dynamic array
};
#endif // QUEUET_H
#include "Queuet.cpp"
Prof. Amr Goneid, AUC
33
Linked Queues
A
Queue can be implemented as a linked
structure.
 Requires more space than array
implementations, but more flexible in size.
 Two pointers are needed: front for
dequeue and rear for enqueue
Prof. Amr Goneid, AUC
34
Node Specification
// The linked structure for a node can be
// specified as a Class in the private part of
// the main queue class.
class node
// Hidden from user
{
public:
Type e;
// stack element
node *next;
// pointer to next node
}; // end of class node declaration
typedef node * NodePointer;
NodePointer front , rear;
Prof. Amr Goneid, AUC
// pointers
35
Enqueue Operation
rear
front
3
New
2
pnew
1
enqueue(v):
NodePointer pnew = new node;
pnew->e = v;
pnew->next = NULL;
rear->next = pnew;
rear = pnew;
Prof. Amr Goneid, AUC
36
Dequeue Operation
1
front
cursor
rear
3
2
dequeue(v):
v = front->e;
cursor = front;
front = front->next;
delete cursor;
Prof. Amr Goneid, AUC
37
Linked Queue Class
// File: QueueL.h
// Linked List Queue class definition
#ifndef QUEUEL_H
#define QUEUEL_H
template <class Type>
class QueueL
{
public:
QueueL();
// Constructor
~QueueL();
// Destructor
void enqueue(Type );
// Add to rear
Prof. Amr Goneid, AUC
38
Linked Queue Class
void dequeue(Type &);
void queueFront(Type &) const;
bool queueIsEmpty() const;
int queueLength() const;
// Remove from front
// retrieve front
// Test for Empty queue
// Queue Length
private:
// Node Class
class node
{
public:
Type e;
// queue element
node *next;
// pointer to next node
}; // end of class node declaration
Prof. Amr Goneid, AUC
39
Linked Queue Class
typedef node * NodePointer;
NodePointer front , rear;
int count;
// Pointers
// length
};
#endif // QUEUEL_H
#include "QueueL.cpp"
Prof. Amr Goneid, AUC
40
Analysis of Queue Operations
 All operations are O(1)
Prof. Amr Goneid, AUC
41
Queue Template Classes
 The CSCI 321 course web site contains full
definitions and implementations of :

Queuet template class: queue class with
dynamic array implementation
 QueueL template class: queue class with
linked implementation
Prof. Amr Goneid, AUC
42