Abstraction
To understand a system, it should be enough to understand what its components do without knowing how. For example when watching a television
• We operate the TV through its interface – remote control and buttons.
• WedonotneedtoopentheTVupandseeinsidetouseit,or understand the electronics inside the remote control.
Abstract Data Types
A data type is
• a set of values
• a collection of operations on those values
An abstract data type (ADT)
• is an approach to implementing data types
• separates the interface from the implementation
users of the type see only an interface
builders of the type provide an implementation
• Example: Do you know what a (FILE *) looks like? Do you need to?
Interface vs Implementation
An ADT interface provides
• a user view of the data structure (eg FILE *)
• function signatures (prototypes) for all operations • semantics of operations (via documentation)
• a contract between the ADT and its clients
• inCwewillputthisinthe.hfile
An ADT implementation gives
• a concrete definition of the data structures
• definitions of functions for all operations
• inCwewillputthisina.cfile
• we may also create static functions which are not part of the interface but are just local helper functions.
Advantages of ADTs
A client does not see the implementation through the interface ie they don’t know if you used an array, a linked list etc. This is good because
• Hides complex details from the user
• Allows the implementation to change without breaking the
client code
• Facilitates decomposing problems into smaller parts
Stacks and Queues
.
• Stacks and Queues are good examples of ADTs
• They are used in many computing applications,
• They form auxiliary data structures for common algorithms,
• They appear as components of larger structures.
• They are also good examples to practice programming with arrays and linked lists.
Stack – ADT
• a stack is a collection of items such that the last item to enter is the first one to exit
• “last in, first out” (LIFO)
• based on the idea of a stack of books, or plates
• essential Stack operations:
push() // add new item to stack
pop() // remove top item from stack
• additional Stack operations:
top() // fetch top item (but don’t remove it)
size() // number of items isEmpty()
Stack Applications
• page-visited history in a Web browser • undo sequence in a text editor
• checking for balanced brackets
• HTML tag matching
• postfix (RPN) calculator
• chain of function calls in a program
Stack – ADT – C Interface
typedef struct stack * Stack;
Stack stackCreate(void);
void stackPush(Stack s, int item); int stackTop(Stack s);
int stackPop(Stack s);
int stackSize(Stack s);
void stackDestroy(Stack s);
Stack – ADT – using the C Interface
#include “stack.h”
…
Stack s;
s = stackCreate();
stackPush(s, 10);
stackPush(s, 11);
stackPush(s, 12);
printf(“%d\n”, stackSize(s)); // prints 3 printf(“%d\n”, stackTop(s)); // prints 12 printf(“%d\n”, stackPop(s)); // prints 12 printf(“%d\n”, stackPop(s)); // prints 11 printf(“%d\n”, stackPop(s)); // prints 10
Stack – ADT – using the C Interface
• Implementation of stack is opaque (hidden from user).
• User programs can not depend on how stack is implementated.
• Stack implementation can change without risk of breaking user programs.
• This type of information hiding is crucial to managing complexity in large software systems.
Stack Application: Postfix Notation
Some early calculators and programming languages used a convention known as Postfix Notation where the operator comes after the two operands rather than between them:
12+
result = 3 32*
result = 6 43+6* result = 42 1234+*+ result = 15
Postfix Calculator
A calculator using RPN is called a Postfix Calculator; it can be implemented using a stack:
• when a number is entered: push it onto the stack
• when an operator is entered: pop the top two items from the stack, apply the operator to them, and push the result back onto the stack.
Queue Abstract Data Type
• a queue is a collection of items such that the first item to enter
is the first one to exit, i.e. “first in, first out” (FIFO)
• based on the idea of queueing at a bank, shop, etc.
• Essential Queue operations:
enqueue() // add new item to queue
dequeue() // remove front item from queue
• Additional Queue operations:
front() // fetch front item (but don’t remove it)
size() // number of items is_empty()
Queue Applications
• waiting lists, bureaucracy
• access to shared resources (printers, etc.) • phone call centres
• multiple processes in a computer
Queue – Abstract Data Type – C Interface
typedef struct queue * Queue; Queue queueCreate(void);
void enqueue(Queue q, int item); int queueFront(Queue q);
int dequeue(Queue q);
int queueSize(Queue q); void queueDestroy(Queue q);
Queue – Abstract Data Type – C Interface
#include “queue.h”
…
Queue q;
q = queueCreate();
enqueue(q, 10);
enqueue(q, 11);
enqueue(q, 12);
printf(“%d\n”, queueSize(q)); // prints 3 printf(“%d\n”, queueFront(q)); // prints 10 printf(“%d\n”, dequeue(q)); // prints 10 printf(“%d\n”, dequeue(q)); // prints 11 printf(“%d\n”, dequeue(q)); // prints 12
Implementing a Stack using an Array
To implement a stack, we need to decide what we need in our struct stack.
We need
• an array and some kind of variable
• a variable to keep track of the current size
• maybe a variable to keep track the maximum size if we aren’t using a define constant
For example:
struct stack{
int items[MAX_SIZE]; int size;
};
Implementing a Stack using an Array
We can make sure we always push and pop to and from the end of the array, which is very efficient.
We also need to be careful about what we do if our stack becomes full.
void stackPush(Stack s, int item){ if(s->size < MAX_SIZE){
s->items[s->size] = item;
s->size++; } else {
//do nothing or give an error message
} }
How would we implement pop?
Implementing A Stack with a Linked List
• a stack can be implemented using a linked list, by adding and removing at the head [push() and pop()]
• adding and removing at the head of a list is very efficient.
• Note: we will implement this in the tutorial.
top of stack
push
pop
data
next
data
next
data
next
NULL
Implementing a Queue using an Array
To implement a queue, we can create a struct similar to what we did for the stack
For example:
struct queue{
int items[MAX_SIZE]; int size;
};
Implementing a Queue using an Array
When we implement enqueue and dequeue we need to either add or remove from the front of the array.
What issues do we face when we add or remove an item from the start of an array?
Is there anyway around this? (Yes see the lab!)
Implementing Queues with Linked Lists
• recall that a queue is a collection of items such that the first item to enter
is the first one to exit, i.e. “first in, first out” (FIFO)
• based on the idea of queueing at a bank, shop, etc. First element of queue
NULL
enqueue
next
next
next
data
data
data
next
data
dequeue
Implementing A Queue with a Linked List
• for a queue, we need to either add and remove from opposite ends
• so we either have to add or remove from the tail. can either of these be done efficiently?
Adding to the Tail of a List
First element of list
next
next
next
NULL
data
data
data
next
data
next
data
NULL
• adding an item at the tail is achieved by making the last node of the list point to the new node
• we first need to scan along the list to find the last item
Adding to the Tail of a List
struct node *addToTail(struct node *n, struct node *head) { if (head == NULL) { // list is empty
head = n;
} else { // list not empty
struct node *node = head; while (node->next != NULL) {
node = node->next; // scan to end }
node->next = n;
}
return head; }
Efficiency Issues
Unfortunately, this implementation is very slow. Every time a new item is inserted, we need to traverse the entire list (which could be
very large).
We can do the job much more efficiently if we retain a direct link to the last item or “tail” of the list:
if (tail == NULL) { // list is empty head = node;
} else { // list not empty tail->next = node;
}
tail = node;
Note: there is no way to efficiently remove items from the tail. (Why?)
Efficient Queue Structure
We can use this structure to implement a queue efficiently:
typedef struct queue Queue;
struct queue {
struct node *head; struct node *tail; int size;
};
Making a new Queue
Queue queueCreate() {
Queue q = malloc(sizeof (struct queue)); if (q == NULL) {
fprintf(stderr, “Out of memory\n”);
exit(EXIT_FAILURE);
}
q->head = NULL; q->tail = NULL; q->size = 0; return q;
}
Adding a new Item to a Queue
//Assume we have a helper function //to create a node
void enqueue(Queue q, int data) {
struct node * newNode = createNode(data,NULL); if (q->tail == NULL) { // queue is empty
q->head = newNode;
} else { // queue not empty
q->tail->next = newNode;
}
q->tail = newNode;
q->size++; }
See lab for dequeue
Testing
Regression testing:
• Keep a test suite (don’t throw away your tests). • Re-run all tests after any changes to the system
Blackbox ADT Testing
Testing code from the outside
• checks behaviour
• does the tested input result in the correct output
• tests do not use knowledges of the underlying implementation. They use the interface only.
• if the implementation changes the tests should still pass
Whitebox ADT Testing
Testing code from the inside • Checks code structure
For example, we could check that our head and tail pointers are correct in a white box test for our linked list based queue
• Checks internal functions (such as static functions)
• Tests rely on and access the internal implementation • If implementation changes, tests need to be rewritten
Assert Based Testing
Use while testing developing and debugging a program.
If the expression inside the assert is false, then the assert fails. For example the following assert fails if x != 0.
assert(x == 0);
When an assert fails it aborts the program and gives an error message which is useful to the programmer.
Black Box Assert Based Testing Example
#include
printf(“Testing an empty stack\n”); Stack s = stackCreate(); assert(stackSize(s) == 0); printf(“passed\n”);
printf(“Pushing 1 item \n”); stackPush(s,9); assert(stackSize(s) == 1); int result = stackPop(s); assert(result == 9); printf(“passed\n”);
//And many more tests…
}