* 4.1 (a,c), 4.4 (a-b), 4.5 (a-b), 4.6.
Reading Assignment
* Ch 6.3 (pp.244-252).
* Very light reading! Enjoy the holidays!
Assignment #2
* due Wed July 5.
Midterm #1
* Fri July 7.
Data Type
* Every data type has two defining characteristics:
1. the "domain" of the type (the set of all possible values).
2. a collection of allowable operations on those values.
* Types such as "int" and "float" are called "simple data types" or "atomic data types".
* A value in an atomic data type is a single data item.
* In contrast, a "structured data type" or "data structure" has
1. component data items, each of which may be atomic or another data structure.
2. rules that define how components relate to each other and to the structure as a whole.
* For example, the C++ built-in array type.
* DOMAIN
1. A collection of a fixed number of component values - each of the same type (either atomic or structure).
2. A set of index (subscript) values that are non negative integers.
* STRUCTURE
1. There is one-to-one relationship between each index and an array component (array element).
2. In particular, index 0 selects the first array element, index 1 selects the second array element, and so forth.
* OPERATIONS
1. retrieve the value of the array element associated with index i.
x = a[i];
2. store a value into the array element associated with index i.
a[i] = x;
Data Structures
* In general, programming languages provide very few data structures as built-in types.
* Arrays
* Records (like a "struct")
* Lists
* Stacks
* Queues
* Sets
Lists
* Common operations on lists
1. create() - create the list
2. is_empty() - is the list empty
3. is_full() - is the list full
4. insert(x) - insert to the front of the list
5. append(x) - append to the end of the list
6. delete(x) - delete x from the list
* Real world examples?
Example
* Assume a list of integers (max 4)
1. create()
2. is_empty() ? is_full() ?
3. insert(1)
4. insert(2)
5. append(3)
6. append(4)
7. is_empty() ? is_full() ?
8. delete(1)
9. what does the list have now?
Stacks
* Last-In First-Out (LIFO) structure.
* Common operations on stacks:
1. create()
2. is_empty()
3. is_full()
4. push(x) - push x onto the top of the stack
5. pop() - pop an element from the top of the stack
* Real world examples?
Example
* Assume a stack of (max 10)
enum Color { WHITE, BLUE, RED }
1. create()
2. is_empty() ? is_full() ?
3. push(WHITE);
4. push(BLUE);
5. push(RED);
6. pop()
7. pop()
8. pop()
Queues
* First-In First-out (FIFO) order.
* Common operations:
1. create()
2. is_empty()
3. is_full()
4. enqueue(x) - insert x to the end
5. dequeue() - remove an element from the front
6. front() - get the element from the front
* Real world examples?
Example
* Assume a queue of characters (max 5)
1. create()
2. enqueue( `a' )
3. enqueue( `b' )
4. enqueue( `c' )
5. front() - assume no removal
6. dequeue()
7. enqueue( `a' )
8. What does the queue look like now?
Sets
* ordering is not an issue.
* Common operations:
1. create()
2. is_empty()
3. is_full()
4. insert(x) - insert x to the set
5. delete(x) - delete x from the set
6. is_member(x) - test if x is a member of the set
* Real world examples?
Example
* Assume a set of Booleans (max 2)
1. create()
2. insert(TRUE)
3. insert(FALSE)
4. insert(TRUE)
5. is_member(TRUE)
6. is_member(FALSE)
7. delete(TRUE)
8. delete(TRUE)
9. is_member(TRUE)
Summary
* The four data structures can be implemented in most programming languages.
* In other words, the concept of data structures are not restricted to the C++ language.
* However, in C++ classes, we probably do not need the create() function because the constructor will do that for us.
* The other functions can be implemented in C++ using public member functions.
Array implementation of a stack of integers
const int MAX_STACK_SIZE = 100;
// max for all instances
class Stack {
public:
Stack(int in_max_size = MAX_STACK_SIZE);
Boolean is_empty() const;
Boolean is_full() const;
void push(int x); // non const
int pop(); // non const
private:
int elem[MAX_STACK_SIZE];
int top; // current top of stack
int max_size; // max_size for this instance
};
// Note the top element is at top - 1
Stack::Stack(int in_max_size)
{
max_size = in_max_size;
top = 0;
}
Boolean
Stack::is_empty() const
{
return (top == 0);
}
Boolean
Stack::is_full() const
{
return (top == max_size);
}
void
Stack::push(int x)
{
if (!is_full()) { elem[top] = x;
top++;
}
}
int
Stack::pop()
{
if (!is_empty()) {
--top;
return (elem[top]);
} else {
// some error code }
}
Array implementation of a queue of characters
const int MAX_QUEUE_SIZE = 100;
class Queue {
public:
Queue(int in_max_size = MAX_QUEUE_SIZE);
Boolean is_empty() const;
Boolean is_full() const;
char front() const;
void enqueue(char x); // non const
void dequeue(); // non const
private:
char elem[MAX_QUEUE_SIZE];
int last;
int max_size;
};
Queue::Queue(int in_max_size)
{
}
Boolean
Queue::is_empty() const
{
}
Boolean
Queue::is_full() const
{
}
char
Queue::front() const
{
}
void
Queue::enqueue(char x)
{
}
void
Queue::dequeue()
{
}