Transcript CS525W: Webware

CS2303: Systems
Programming Concepts
Class 14
Data Structures:
Defining
Using
Implementing
Copyright 2005-2008, Michael J. Ciaraldi
1
Data Structures
You may have used some:
Stack
Queue
Linked list
Tree
We will learn how to make them.
2
Data Structures
We will learn how to make them. Why?
Not always available.
Might have to implement.
Better understanding.
Pick most appropriate.
Built-in not appropriate.
E.g. kernel, time-critical.
3
Defining and Using
Data Structures
4
Stack
Gets it name from where?
And is it appropriate?
Policy: LIFO
Where else is that used?
Top
Operations:
push()
pop()
peek()
isEmpty()
5
Conceptual Stack: push-down
One entry
in stack
Push
Push
3 entries
in stack
6
Conceptual Stack: pop up
3 entries
in stack
Pop
Pop
Pop causes
empty stack
7
Practical Stack
Stack pointer
One entry
in stack
Push
Push
Push
8
Stack Options
Growth
Up?
Down?
Stack pointer points to:
“Top” of stack?
Next free cell?
Types of elements restricted/preserved?
9
Stack Warnings
How to handle stack overflow?
How to handle stack underflow?
What is “handle”?
Detect
Stack effect
Return value
Signal error condition
10
Queue
Gets it name from where?
And is it appropriate?
Policy: FIFO
Where else is that used?
Add at tail, remove at head.
Operations:
enqueue()
dequeue()
peek()
isEmpty()
11
Conceptual Queue
One entry
in queue
Enqueue
Enqueue
Enqueue
12
Conceptual Queue
3 entries
in queue
Dequeue
Dequeue
Dequeue causes
empty queue
13
Practical Queue
Head pointer
Tail pointer
14
Queue Options
Fixed maximum size?
Priority?
Add/delete at both ends?
Deque = double-ended queue.
Types of elements restricted/preserved?
15
Queue Warnings
How to handle wraparound?
How to handle queue overflow?
How to handle queue underflow?
What is “handle”?
Detect
Queue effect
Return value
Signal error condition
16
Data Structure
Implementation
17
Implementation
Alternatives:
Object-oriented
Not
18
Implementation
Object-oriented
Each stack or queue is a separate object.
Fields: Stack data area, size, pointer.
Methods: push(), pop(), etc.
19
Implementation
Not Object-oriented
Series of functions: create(), push(), pop(),
etc.
Need identifier if more than one.
Where to store specs?
Risky, but done: just a stack pointer.
20
Next Time
More data structures: Implementation,
list, tree…
21