Vectors, Lists, Stacks, Queues

K08 Δομές Δεδομένων και Τεχνικές Προγραμματισμού

Κώστας Χατζηκοκολάκης

ADTVector

A Vector can be seen as an abstract resizable “array”
- It is not an array (remember, it's abstract)
- but it behaves like one
We can access existing elements based on their position (random access)
We can insert/remove elements at the end of the vector (dynamic size)
We can search for elements (but this is usually inefficient)
We can iterate over elements (also possible using random access)

a.k.a. Dynamic/Growable/Resizable/Mutable Array, Array List, List, …

Create, destroy

// Ένα vector αναπαριστάται από τον τύπο Vector. Ο χρήστης δε χρειάζεται να
// γνωρίζει το περιεχόμενο του τύπου αυτού, απλά χρησιμοποιεί τις συναρτήσεις
// vector_<foo> που δέχονται και επιστρέφουν Vector.
//
// Ο τύπος Vector ορίζεται ως pointer στο "struct vector" του οποίου το
// περιεχόμενο είναι άγνωστο (incomplete struct), και εξαρτάται από την
// υλοποίηση του ADT Vector.

typedef struct vector* Vector;

// Δημιουργεί και επιστρέφει ένα νεό vector μεγέθους size, με στοιχεία
// αρχικοποιημένα σε NULL. Αν δεν υπάρχει διαθέσιμη μνήμη επιστρέφει
// VECTOR_FAIL.

Vector vector_create(int size, DestroyFunc destroy_value);

// Ελευθερώνει όλη τη μνήμη που δεσμεύει το vector vec.

void vector_destroy(Vector vec);

An initial size is given at creation (ignore destroy_value for now).

Random access

// Επιστρέφει την τιμή στη θέση pos του vector vec (μη ορισμένο αποτέλεσμα αν
// pos < 0 ή pos >= size)

Pointer vector_get_at(Vector vec, int pos);

// Αλλάζει την τιμή στη θέση pos του Vector vec σε value. ΔΕΝ μεταβάλλει το
// μέγεθος του vector, αν pos >= size το αποτέλεσμα δεν είναι ορισμένο.

void vector_set_at(Vector vec, int pos, Pointer value);

Example [4, 6, 2, 1]
- Get at 1: 6
- Set 8 at 0: [8, 6, 2, 1]

Insert and delete at the end

// Προσθέτει την τιμή value στο _τέλος_ του vector vec. Το μέγεθος του vector
// μεγαλώνει κατά 1. Αν δεν υπάρχει διαθέσιμη μνήμη το vector παραμένει όπως
// ήταν (αυτό μπορεί να ελεγχθεί με τη vector_size)

void vector_insert_last(Vector vec, Pointer value);

// Επιστρέφει  την τιμή της τελευταίας θέσης του vector.
// Το μέγεθος του vector μικραίνει κατά 1.

void vector_remove_last(Vector vec);

The size of the vector is modified (in contrast to C arrays)!
Example [4, 6, 2, 1]
- Insert 3: [4, 6, 2, 1, 3]
- Remove: [4, 6, 2, 1]

Search

// Βρίσκει και επιστρέφει το πρώτο στοιχείο στο vector που να είναι ίσο με value
// (με βάση τη συνάρτηση compare), ή NULL αν δεν βρεθεί κανένα στοιχείο.

Pointer vector_find(Vector vec, Pointer value, CompareFunc compare);

Usually sequential search (remember, the implementation is not fixed!)
Reduntant, could be implemented by iterating

Iteration

// Μέσω random access

int size = vector_size(vec);
for (int i = 0; i < size; i++) {
    int* value = vector_get_at(vec, i);
    printf("%d\n", *value);
}

// Μέσω κόμβων

for(VectorNode node = vector_first(vec);        // ξενικάμε από τον πρώτο κόμβο
    node != VECTOR_EOF;                         // μέχρι να φτάσουμε στο EOF
    node = vector_next(vec, node)) {            // μετάβαση στον επόμενο κόμβο

    int* value = vector_node_value(vec, node);  // η τιμή του συγκεκριμένου κόμβου
    printf("value: %d\n", *value);
}

Memory management

The memory reserved for the vector itself is managed by the module
We are responsible for the contents (Pointers)
Simple memory management:
- destroy_value function to be called when a value is removed

Vector vec = vector_create(0, free);

vector_insert_last(vec, strdup("foo"));
vector_insert_last(vec, strdup("bar"));

vector_remove_last(vec);    // free bar

vector_destroy(vec);        // free foo (και destroy το ίδιο το vector)

When to use Vectors

General purpose containers
When we need random access
When we don't need to insert at random positions
When we don't need efficient search

ADTList

We sacrifice random access for insert/delete flexibility
Only sequential access
We can insert and remove elements anywhere
We can search for elements (but this is usually inefficient)
We can iterate over elements in the order of insertion

a.k.a. Forward list (also, “List” sometimes means something else)

Insert and delete anywhere

// Προσθέτει έναν νέο κόμβο __μετά__ τον node, ή στην αρχή αν node == LIST_BOF,
// με περιεχόμενο value.

void list_insert_next(List list, ListNode node, Pointer value);

// Αφαιρεί τον __επόμενο__ κόμβο από τον node, ή τον πρώτο κόμβο αν node == LIST_BOF.

void list_remove_next(List list, ListNode node);

Positions represented by nodes
Insert/remove happens after the given node
Example (4, 6, 2, 1)
- Insert 3 after 6: (4, 6, 3, 2, 1)
- Remove after 4: (4, 3, 2, 1)

Iteration

// Μόνο μέσω κόμβων

for(ListNode node = list_first(list);          // ξενικάμε από τον πρώτο κόμβο
    node != LIST_EOF;                          // μέχρι να φτάσουμε στο EOF
    node = list_next(list, node)) {            // μετάβαση στον επόμενο κόμβο

    int* value = list_node_value(list, node);  // η τιμή του συγκεκριμένου κόμβου
    printf("value: %d\n", *value);
}

Other functions

Same as for Vectors.

List list_create(DestroyFunc destroy_value);

// Επιστρέφει τον αριθμό στοιχείων που περιέχει η λίστα.

int list_size(List list);

// Επιστρέφει την πρώτη τιμή που είναι ισοδύναμη με value
// (με βάση τη συνάρτηση compare), ή NULL αν δεν υπάρχει

Pointer list_find(List list, Pointer value, CompareFunc compare);

// Ελευθερώνει όλη τη μνήμη που δεσμεύει η λίστα list.
// Οποιαδήποτε λειτουργία πάνω στη λίστα μετά το destroy είναι μη ορισμένη.

void list_destroy(List list);

When to use Lists

General purpose containers
When sequential access is enough
When we need to insert/delete at random positions
When we don't need efficient search

Stacks

Very limited functionality
- but useful in practice
- allows for efficient implementations
Insert and delete at the top
- Last-in, first-out (LIFO)
Acceess only the top element
- No random access
- No iteration

Examples of Stacks in Real Life

LIFO access

// Επιστρέφει το στοιχείο στην κορυφή της στοίβας (μη ορισμένο αποτέλεσμα αν η
// στοίβα είναι κενή)

Pointer stack_top(Stack stack);

// Προσθέτει την τιμή value στην κορυφή της στοίβας stack.

void stack_insert_top(Stack stack, Pointer value);

// Αφαιρεί την τιμή στην κορυφή της στοίβας (μη ορισμένο
// αποτέλεσμα αν η στοίβα είναι κενή)

void stack_remove_top(Stack stack);

Example [4, 6, 2, 1]
- Insert 3: [4, 6, 2, 1, 3]
- Remove: [4, 6, 2, 1]
Commonly called push and pop

When to use Stacks

When LIFO access is enough
Many applications
- Storing information of active function calls
- Parsing algorithms
- Expression evaluation algorithms
- Backtracking algorithms
- …

Using a Stack to check for balanced parentheses

Determine whether parentheses/brackets balance properly in algebraic expressions.
Example:

$ \{ a^2 -[(b+c)^2 - (d+e)^2] * [\sin(x-y)] \} - \cos(x+y)$
This expression contains parentheses, square brackets, and braces in balanced pairs according to the pattern

$\{ [ ( ) ( ) ] [ ( ) ] \} ( )$

The Algorithm

Start with an empty stack
Scan the algebraic expression from left to right
- On (, [, { we insert it to the stack.
- On ), ], } we remove the top item and check that its type matches
The expression is balanced iff
- all pairs match, and
- at the end the stack is empty

Postfix Expressions

Expressions are usually written in infix notation $L~op~R$
- The operator appears between the operands
- eg. $(a+b)*2-c$
- Parentheses are used to denote the order
Postfix: write the operator after the operands $L~R~op$
- eg. $ a b + 2 * c -$
- Advantage: no need for parentheses!

Examples

Infix	Postfix
(a + b)	a b +
(x - y - z)	x y - z -
(x - y - z) / (u + v)	x y - z - u v + /
(a^2 + b^2) * (m - n)	a 2 ^ b 2 ^ + m n - *

Using a Stack to evaluate postfix expressions

Scan from left to right
When we find an operand $X$, insert it int the stack
When we find an operator $op$
- remove the top operand into a variable $R$ (right operand)
- remove another topmost operand into a variable $L$ (left operand)
- Perform the operation $L~op~R$
- Insert the value back into the stack
End of expression: its value is the (only) item remaining in the stack

Translating Infix expressions to Postfix

We can also use a Stack to translate fully parenthesized infix arithmetic expressions to postfix.
Algorithm to convert $(L~op~R)$ to the postfix form $L~R~op$
- ignore the left parenthesis
- convert $L$ to postfix
- save $op$ on the stack
- convert $R$ to postfix
- then, on $)$, pop the stack and output the $op$

Example

We want to translate the infix expression ((5*(9+8))+7) into postfix.
The result will be 5 9 8 + * 7 +

Input	Output	Stack
(
(
5	5
*		*
(		*
9	9	*
+		* +
8	8	* +
)	+	*
)	*
+		+
7	7	+
)	+

Queues

Very limited functionality (similarly to stacks)
- but useful in practice
- allows for efficient implementations
Insert in the back, remove from the front
- First-in, first-out (FIFO)
Acceess only the front and back elements
- No random access
- No iteration

FIFO access

// Επιστρέφει το στοιχείο στο μπροστινό μέρος της ουράς

Pointer queue_front(Queue queue);

// Επιστρέφει το στοιχείο στο πίσω μέρος της ουράς

Pointer queue_back(Queue queue);

// Προσθέτει την τιμή value στo πίσω μέρος της ουράς queue.

void queue_insert_back(Queue queue, Pointer value);

// Αφαιρεί την τιμή στο μπροστά μέρος της ουράς

void queue_remove_front(Queue queue);

Example [4, 6, 2, 1]
- Insert 3: [4, 6, 2, 1, 3]
- Remove: [6, 2, 1, 3]
Commonly called push/pop (or enqueue/dequeue)

When to use Queues

When FIFO access is enough
Many applications
- Sheduling of processes
- Access to resources (CPU, printers, etc)
- Breadth First Search in trees and graphs
- …

Example, experimental simulation

A new job arrives to the CPU each second with pb $p$
Each job takes between 1 and 4 seconds to execute (random)
What is the average waiting time?
We can write a program the simulates the system using a queue
- time represented by an integer t
- at each second, insert a job randomly (using rand)
- select duration also randomly
- remove job after duration seconds, compute its waiting time

Readings

T. A. Standish. Data Structures, Algorithms and Software Principles in C. Chapter 7.
R. Sedgewick. Αλγόριθμοι σε C., Κεφ. 4.