2018-06-18_2 esercizio "integer sort"

Tema

Descrivere un algoritmo che, dati n numeri interi compresi nell’intervallo da 0 a k, svolga un’analisi preliminare del suo input e poi risponda nel tempo O(1) a qualsiasi domanda su quanti degli n interi ricadono nell’intervallo [a..b] con a e b interi. Il vostro algoritmo dovrebbe impiegare un tempo È(n+k) per l’analisi preliminare.

Svolgimento

Nota: descrivere = scrivere.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define N_ELEMENTS 20
#define MAX_ABS_VALUES 50

int *prepare(int values[], int size, int *min, int *max) {
	int i;
	int * aux;
	if(size == 0) {
		return NULL;
	}
	*min = values[0];
	*max = values[0];
	for(i = 0; i < size; i++) {
		if(values[i] < *min) *min = values[i]; if(values[i] > *max) *max = values[i];
	}
	aux = malloc(sizeof(int) * (*max - *min + 1));
	for(i = 0; i < *max - *min + 1; i++) aux[i] = 0;
	for(i = 0; i < size; i++) {
		aux[values[i] - (*min)]++;
	}
	for(i = 1; i < *max - *min; i++) aux[i] = aux[i] + aux[i-1];
	return aux;
}


int main(int argc, char *argv[])
{
	int *values; // contiene i valori non ordinati
	int min; // il valore più piccolo
	int max; // il valore più grande
			 // la dimensione del vettore di appoggio è data da min - max
	int *aux; // l'array ausiliario dell'integer sort
	int i;
	int da, a; // il minimo e massimo tra i valori chiesti all'utente
	int ind_da, ind_a; // gli indici più vicini a da e a
	
	values = malloc(sizeof(int) * N_ELEMENTS);
	srand(time(0));

	for(i = 0; i < N_ELEMENTS; i++)
		values[i] = rand() % (MAX_ABS_VALUES * 2) - MAX_ABS_VALUES;

	aux = prepare(values, N_ELEMENTS, &min, &max);

	for(i = 0; i < max - min; i++) printf("%d: %d\t", i+min, aux[i]);

	printf("\nInserire il primo elemento: ");
	scanf("%d", &da);
	printf("Inserire il secondo elemento: ");
	scanf("%d", &a);

	if(a - da < 0) { a = da+a; da = a-da; a = da-a;} // scambio gli elementi se a < da

	printf("La quantità di numeri compresi tra %d e %d e' %d\n", da, a, (a>=max?aux[max-min-1]:aux[a-min]) - (da<=min?0:aux[da-min-1]));

	system("PAUSE");
	return 0;
}

Commento all'algoritmo

L'algoritmo è una variante dell'integer sort.

Dati n numeri compresi tra n1 e n2 si inizializza un array di k+1 elementi indicizzati da 0 a n2 - n1 e inizializzati a zero.

Esempio (vettore n):

6 -7 5 -1 8 0 4 -2 -8 3

Per ogni elemento in n si incrementano gli indici corrispondenti come nell'integer sort:

Esempio (vettore k):

Ind: -8 -7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7 8
Val: 1 1 0 0 0 0 1 1 1 0 0 1 1 1 1 0 1

poi si cumula la somma da n1 a n2

Ind: -8 -7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7 8
Val: 1 2 2 2 2 2 3 4 5 5 5 6 7 8 9 9 10

Questo richiede ancora un costo Θ(n+k).

In tempo O(1) si estrae l'elemento precedente di A (o zero se A è il primo) e si sottrae all'elemento B.

Esempio:

A = -2

B = 3

k[A-1] = 3

k[B] = 5

k[B] - k[A-1] = 2

Se A o B sono rispettivamente minore del più piccolo e maggiore del più grande è sufficiente considerare il primo e l'ultimo elemento.

Come richiesto, il tempo di preparazione è Θ(n+k) e quello di consultazione è O(1).

Commento al codice

Si è deciso di separare la procedura principale (il tema d'esame) da quella di appoggio, contenente l'inizializzazione e le richieste all'utente.

La chiamata prevede il ritorno di tre valori: l'array k e il minimo e il massimo. Questi due valori sono due int nella procedura di appoggio, che sono passati come puntatori alla procedura principale.

Due costanti indicano la dimensione dell'array e l'intervallo di numeri che è possibile inserire in senso assoluto (es. 5 => da -5 a +5) ottenendo un intervallo di n*2+1 valori.

Nella procedura principale, i valori di minimo e massimo vanno inizializzati con uno dei valori dell'array, poi con un ciclo si valuta se abbassare il minimo o alzare il massimo.

È necessario anche inizializzare i valori dell'array k a zero, perché c'è una probabilità non nulla che alcuni valori non compaiano mai (soprattutto se |n| è piccolo e |k| è grande).

Rispetto all'integer sort è necessario un ulteriore ciclo per calcolare il valore cumulato, che però non ha impatti sul costo asintotico.

Nella procedura principale, a parte il popolamento dell'array con valori casuali, è degno di nota il sistema per gestire la richiesta di valori minori del minimo o maggiori del massimo, che per sintesi è reso con l'utilizzo di operatori ternari.

Algoritmi di ordinamento (con implementazione in C)

Premessa

Tutti gli algoritmi usano il seguente codice:

#include <stdio.h>
#define NUM_OF_ELEMENTS 10000
main() {
	int i;
	int numeri[NUM_OF_ELEMENTS];
	srand(time(NULL));
	for(i = 0; i < NUM_OF_ELEMENTS; i++) {
		numeri[i] = rand();
	}
	for(i = 0; i < NUM_OF_ELEMENTS; i++) {
		printf("%d ", numeri[i]);
		if(i % 5 == 4) printf("\n");
		}
	printf("\n\n");
	sort(&numeri, NUM_OF_ELEMENTS);
	for(i = 0; i < NUM_OF_ELEMENTS; i++) {
		printf("%d ", numeri[i]);
		if(i % 5 == 4) printf("\n");
	}
	getchar();
}

In alcuni casi la chiamata alla funzione sort può avere una firma leggermente diversa (es. possono avere come parametro l'indice di partenza, tipicamente zero).

Algoritmi con costo di esecuzione O(n2)

Tipicamente gli algoritmi di ordinamento con costo di esecuzione O(n2) sono caratterizzati da una reiterazione di tutti gli elementi per ogni "sistemazione".

Selection sort

L'algoritmo inizia con un elemento, che per definizione è orditato.

Dal secondo elemento in poi, abbiamo un insieme già ordinato - convenzionalmente a sinistra - e un insieme da ordinare - a destra.

Per ciascun elemento non ancora ordinato, si sceglie il minore tra gli elementi non ancora ordinati e si scambia con quello più a sinistra.

1 3 4 7 8 10 29 44 14 73 19 36
1 3 4 7 8 10 29 44 14 73 19 36
1 3 4 7 8 10 14 44 29 73 19 36
1 3 4 7 8 10 14 44 29 73 19 36

Il tempo di esecuzione si può calcolare dividendo l'array in due.

Per ciascun elemento già ordinato si sottrae uno al totale di elementi da ordinare, quindi con n elementi la prima iterazione sarà tutti gli elementi (n), la seconda su tutti tranne il primo (n-1) e così via, fino a fare n iterazioni su

j=1nn-j

Il totale delle iterazioni è il ben noto

nn-12

Apparentemente è un tempo migliore di n2, ma a ben guardare il limite per n sufficientemente grande di

limnnn-12n2=limnn22-n2n2

Dividendo il numeratore e il denominatore per n2,

limn12-12n

Si ottiene che per n sufficientemente grande, l'algoritmo tende a un costo di Θ(n2) con costante = 1/2.

Il tempo di esecuzione non varia per il caso medio, ottimo e pessimo.

L'implementazione può essere fatta in loco.

void sort(int *numeri, int conteggio) {
	int i;
	int j;
	int m;
	int temp;
	for(i = 0; i < conteggio-1; i++) {
		m = i;
		for(j = i+2; j < conteggio; j++) {
			if(numeri[j] < numeri[m]) m = j;
		}
		temp = numeri[m];
		numeri[m] = numeri[i+1];
		numeri[i] = temp;
	}
}

Insertion Sort

L'algoritmo inizia con un elemento, che per definizione è orditato.

Dal secondo elemento in poi, abbiamo un insieme già ordinato - convenzionalmente a sinistra - e un insieme da ordinare - a destra.

Per ciascun elemento non ancora ordinato, si sceglie quello più a sinistra e si scorre da sinistra a destra l'insieme ordinato fino a trovare il primo elemento maggiore dell'elemento considerato.

A questo punto si scorrono a destra di una posizione tutti gli elementi maggiori e si inserisce l'elemento considerato nella posizione lasciata libera.

1 18 27 44 89 101 29 45 14 73 19 36
1 18 27
44

89

101
29 45 14 73 19 36

il 29 è memorizzato in una variabile

1 18 27 * 44 89 101 45 14 73 19 36

* questa posizione è ancora occupata dal 44, ma ai fini dell'algoritmo è libera

1 18 27 29 44 89 101 45 14 73 19 36

Il tempo di esecuzione si può discutere in maniera estremamente simile a Selection Sort.

L'implementazione può essere fatta in loco.

void sort(int *numeri, int conteggio) {
	int i;
	int j;
	int k;
	int num;
	for(i = 0; i < conteggio-1; i++) {
		num = numeri[i+1];
		for(j = 0; j <= i; j++) { if(numeri[j] > num) {
				for(k = i+1; k > j; k--) {
					numeri[k] = numeri[k-1];
				}
				numeri[j] = num;
				break;
			}
		}
	}
}

Bubble Sort

L'algoritmo inizia con un elemento, che per definizione è orditato.

Dal secondo elemento in poi, abbiamo un insieme già ordinato - convenzionalmente a sinistra - e un insieme da ordinare - a destra.

Per ciascun elemento non ancora ordinato, si sceglie quello più a sinistra e si scambia con tutti quelli già ordinati che sono maggiori dell'elemento considerato.
È maggiore il 32 o il 18? Si fa lo scambio!

32 18 45 14 73 19 36
18 32 14 45 19 73 36

È maggiore il 32 o il 45? Siccome è il 45, non c'è scambio e l'indice si incrementa.

18 14 32 45 19 73 36
18 14 32 19 45 73 36
18 14 32 19 45 36 73

Anche in questo caso il tempo di esecuzione è Θ(n2), poiché per n volte posizioniamo l'n-k-esimo elemento a destra.

L'implementazione può essere fatta in loco.

void sort(int *numeri, int conteggio) {
	short scambio;
	int i;
	int j;
	int temp;
	scambio = 0;
	for(i = 0; i < conteggio - 1; i++) {
		for(j = 1; j < conteggio - i + 1; j++) { if(numeri[j-1] > numeri[j]) {
				temp = numeri[j-1];
				numeri[j-1] = numeri[j];
				numeri[j] = temp;
				scambio = 1;
			}
		}
		if(scambio == 0) break;
	}
}

Algoritmi con costo di esecuzione O(n logn)

Gli algoritmi con questo tempo di esecuzione sono i divide-et-impera, algoritmi in cui il vettore viene diviso (tipicamente in due) tante volte fino ad arrivare a blocchi con uno o due soli elementi.

Merge Sort

Il vettore viene spezzato a metà ricorsivamente, fino ad arrivare a piccoli blocchi di uno o due elementi. Successivamente tutti gli elementi, ordinati al loro interno, sono fusi (merge) in un unico blocco grande (circa) il doppio.

V1 1 4 14 19 29 36 44 73
V2 3 7 11 21 29 39 52
Vettore risultante

La freccia indica la posizione del puntatore, il grigio indica che il numero è il più basso tra i due

V1 ⇒1 4 14 19 29 36 44 73
V2 ⇒3 7 11 21 29 39 52
Vettore risultante 1

 

V1 1 ⇒4 14 19 29 36 44 73
V2 ⇒3 7 11 21 29 39 52
Vettore risultante 1 3

 

V1 1 ⇒4 14 19 29 36 44 73
V2 3 ⇒7 11 21 29 39 52
Vettore risultante 1 3 4

...eccetera...

V1 1 4 14 19 29 36 44 ⇒73
V2 3 7 11 21 29 39 52 ⇒ *

* il puntatore ha superato i limiti, quindi è sufficiente copiare il contenuto dell'altro array

Vettore risultante 1 3 4 7 11 14 19 21 29 29 36 39 44 52

Il tempo di esecuzione del merge è C(n) = n-1 + 2C(n/2). Per il teorema master, O(nlog22) = O(n-1) ⇒ C(n) = Θ(n logn)

L'implementazione può essere fatta con un vettore di appoggio.

void merge(int * numeri, int inizio, int pivot, int conteggio) {
	int * merged;
	int i;
	int ja, jb;
	ja = inizio;
	jb = pivot;
	merged = malloc(sizeof(int) * (conteggio - inizio));

	for(i = inizio; i < conteggio; i++) {
		if((numeri[ja] < numeri[jb] || jb >= conteggio) && ja < pivot)
			merged[i-inizio] = numeri[ja++];
		else
			merged[i-inizio] = numeri[jb++];
	}
	for(i = inizio; i < conteggio; i++) numeri[i] = merged[i-inizio];
	free(merged);
}
void sort(int *numeri, int inizio, int conteggio, int rec) {
	int pivot;
	int i;
	if(conteggio - inizio > 1) {
		pivot = (conteggio - inizio) / 2 + inizio;
		sort(numeri, inizio, pivot, rec+1);
		sort(numeri, pivot, conteggio, rec+1);
		merge(numeri, inizio, pivot, conteggio);
	}
}

Quick Sort

Quick Sort è un algoritmo in cui il grosso del costo consiste nella fase del divide, perché richiede di scegliere un elemento pivot e di spostare tutti gli elementi minori o uguali del pivot a sinistra e tutti quelli maggiori a destra, e di applicare ricorsivamente alle due metà l'algoritmo fino a ottenere blocchi di uno o due elementi.

Limiti e caratteristiche del Quick Sort

Quick Sort richiede la scelta di un elemento, contenuto nella parte di vettore che stiamo ordinando, che sia "circa" mediano, in modo da ottenere due parti "circa" uguali. Scegliendo un elemento completamente a caso, la probabilità seguirà la classica curva gaussiana, e la probabilità di scegliere il minimo o il massimo è estremamente bassa.

Però il Quick Sort processa per la maggior parte dei casi vettori di pochi elementi, in cui la probabilità di scegliere il minimo o il massimo è non trascurabile.

Scegliendo tre elementi a caso - e non uno - e utilizzando come pivot la mediana, si riduce in modo esponenziale la probabilità di scegliere un estremo (p.e. se c'è 1/100 probabilità di ottenere un minimo o un massimo, scegliendo tra tre numeri la probabilità diventa 1/100 * 1/100 * 1/100 = 1/1.000.000).

Quick Sort richiede un "aggiustamento" nel caso in cui ci possano essere molti valori duplicati. In questo caso ci si potrebbe trovare con semi-array contenenti sempre lo stesso numero, e in questo caso il divide porterebbe a un semi-array uguale a quello originale e un altro semi-array vuoto, all'infinito.

Per questo è necessario prevedere un controllo che tutti gli elementi dell'array siano non tutti uguali (basta un elemento diverso).

Esempio d'uso

Nota: gli elementi inseriti nella funzione med (=mediana) sono scelti casualmente.

52 4 19 36 73 29 21 44 1 39 3 7 11 29 14

Pivot: med(39, 29, 36) = 36

Ricorsione: sinistra

4 19 36 29 21 1 3 7 11 29 14

Pivot: med(19, 7, 11) = 11

Ricorsione: sinistra-sinistra

4 1 3 7 11

Pivot: med(1, 3, 7) = 3

Ricorsione: sinistra-sinistra-sinistra

1 3

A questo punto, se gli elementi non sono ordinati si scambiano.
In questo caso, 1, 3

Ricorsione: sinistra-sinistra-destra

4 7 11

A questo punto, la mediana è 7, che divide l'array in 4, 7 e 11.

4 e 7 non vengono scambiati perché sono già in ordine e 11 resta da solo. Fondendo i due array si ottiene 4, 7, 11

Ricorsione: sinistra-destra

19 36 29 21 29 14

Pivot: med(19, 21, 14) = 21

Ricorsione: sinistra-destra-sinistra

19 21 14

A questo punto, la mediana è 19, si ottengono 19, 14 e 21.
19 e 14 vengono scambiati e si ottiene 14, 19, 21

Ricorsione: sinistra-destra-destra

36 29 29

A questo punto, la mediana è 29. Si ottengono 29, 29 e 36.
29 e 29 sono uguali, quindi non avviene alcuno scambio e si restituisce la coppia di numeri.
Il risultato è 29, 29, 36

Ricorsione: destra

52 73 44 39

Pivot: med(52, 73, 44) = 52

Ricorsione: destra-sinistra

52 44 39

La mediana è 44, si ottengono 44, 39 e 52.
44 e 29 si scambiano, e unendo l'elemento singolo 52 si ottiene 39, 44, 52

Ricorsione: destra-destra
Si ottiene l'elemento unico 73.

Unendo nell'ordine di chiamata, dal ramo più a sinistra a quello più a destra, si ottiene

1 3 4 7 11 14 19 21 29 29 36 39 44 52 73

Il tempo di esecuzione del Quick Sort è O(n logn).

// NOTA: Questa implementazione funziona solo con valori distinti
// NOTA: Questa implementazione non utilizza il sistema della mediata descritto nel testo

void sort(int * a, int start, int end) {
	int s, e; // inizializzati a start e end, scorrono l'array dall'inizio o dalla fine
	int pivot; // l'elemento pivot. Nella prima implementazione, è un elemento scelto completamente a caso
	int i, tmp, r;
	
	// gestisco il caso di un array di 1 e 2 elementi
	if(start >= end) return;
	if(start + 1 == end) {
		if(a[start] > a[end]) {
			tmp = a[start];
			a[start] = a[end];
			a[end] = tmp;
		}
		return;
	}
	
	srand(time(NULL));
	
	s = start;
	e = end;
	srand(time(NULL));
	r = (rand() % (end-start+1)) + start;
	pivot = a[r]; // non è un'implementazione equiprobabile, ma per i nostri scopi è più che sufficiente
	while(s < e) {
		if(a[s] <= pivot) s++; else { if(a[e] > pivot) e--;
			if(a[s] > pivot && a[e] <= pivot) { tmp = a[s]; a[s] = a[e]; a[e] = tmp; } } } if(a[s] > a[e]) {
		tmp = a[s];
		a[s] = a[e];
		a[e] = tmp;
	}
	if(a[s] <= pivot) e++; sort(a, start, e-1); if(e >= s) sort(a, e, end);
}

Algoritmi con costo di esecuzione O(n) e simili

Integer Sort

Integer Sort ha tempi migliori degli algoritmi precedenti perché suppone che gli elementi da ordinare siano tutti numeri interi positivi (in realtà è facile includere nell'algoritmo anche quelli negativi).

L'idea è di creare un array che utilizzi gli interi da ordinare come degli indici e l'elemento del secondo array incrementa semplicemente l'indice ogni volta che si incontra quel numero.

Per esempio:

5, 9, 13, 13, 6, 9, 5, 14, 2 è l'array da ordinare.

max(array) = 14, quindi si crea un array di 14 elementi (per semplicità sarà indicizzato da 1 a n, contro la prassi degli array) e si inizializzano i contatori a zero.

[0] [0] [0] [0] [0] [0] [0] [0] [0] [0] [0] [0] [0] [0]

Per ogni numero esaminato si incrementa il rispettivo contatore:

5

[0] [0] [0] [0] [1] [0] [0] [0] [0] [0] [0] [0] [0] [0]

9

[0] [0] [0] [0] [1] [0] [0] [0] [1] [0] [0] [0] [0] [0]

13

[0] [0] [0] [0] [1] [0] [0] [0] [1] [0] [0] [0] [1] [0]

13

[0] [0] [0] [0] [1] [0] [0] [0] [1] [0] [0] [0] [2] [0]

...eccetera. L'ordine finale è il seguente:

[0] [1] [0] [0] [2] [1] [0] [0] [2] [0] [0] [0] [2] [1]

Scorrendo l'array si ottiene

2, 5, 5, 6, 9, 9, 13, 13, 14

Il tempo di esecuzione dipende dagli n elementi e dal k massimo, ed è O(n+k).

L'implementazione è la seguente:

sort(int * a, int count) {
	int i, k, max;
	int * appo;
	
	max = 0;
	k = 0;
	
	for(i = 0; i < count; i++) if(max < a[i]) max = a[i];
	
	appo = malloc(sizeof(int) * max + 1);
	for(i = 0; i <= max; i++) appo[i] = 0;
	for(i = 0; i < count; i++) appo[a[i]]++;
	for(i = 0; i <= max; i++) while(appo[i] > 0) {a[k++] = i; appo[i]--;}
}

Implementazione in C di una pila

La struttura dati pila

La pila è una struttura dati di tipo LIFO per cui l'ultimo elemento inserito è il primo a uscire.

Le operazioni sulla pila sono solo tre:

  • verifica che la pila [non] sia vuota (empty)
  • inserimento di un nuovo elemento (push)
  • restituzione di un elemento e cancellazione dalla pila (pop)

Esempio:

push('c')

c

push('i')

c i

push('a')

c i a

push('o')

c i a o

pop() // ottengo la o

c i a

pop() // ottengo la a

c i

Tempo di esecuzione

Inserimento: ο(1)

Cancellazione: ο(1)

Ricerca: ο(n)

Implementazione

In questa implementazione, la pila è un insieme di nodi, ciascuno dei quali contiene un valore di tipo char e un puntatore al nodo successivo.

// in stack.h
typedef struct stack * Stack;

// in stack.c
struct stack {
char c;
Stack next;
};

Nel file di header è definito un tipo Stack che rappresenta una struct stack *, quindi Stack è un puntatore.

Nel file .c è definita la struttura stack (s minuscola) che contiene il valore del nodo e il puntatore al nodo successivo. Una scrittura alternativa, che non fa uso della definizione del tipo Stack è la seguente:
// in stack.c
struct stack {
char c;
stack * next;
};

init

è stata aggiunta una funzione init() che alloca della memoria e restituisce il puntatore a un nodo vuoto.


Stack init() {
Stack s;
s = (Stack)malloc(sizeof(Stack));
s->next = NULL;
return s;
}

Il cast a Stack presente nella malloc non è strettamente necessario.

empty


int empty(Stack s) {
return s->next == NULL;
}

Dal momento che l'ultimo nodo è vuoto, faccio una verifica sul campo next.

push


void push(Stack *s, char c) {
Stack newStack;
newStack = init();
newStack->c = c;
newStack->next = *s;
*s = newStack;
}

push prende in ingresso il puntatore a uno Stack (quindi un puntatore al puntatore di stack con la s minuscola).

In questo modo quando si usa s si sta utilizzando un indirizzo di memoria, e non un valore. Nella pratica, si agisce sul dato contenuto nell'indirizzo puntato da s; viceversa sarebbe fatta una copia del contenuto di s.

Con puntatore Senza puntatore
push(Stack *s, char c)
è passato un puntatore a s
push(Stack s, char c)
è passato s: in realtà è una "copia" che ha la funzione come scope
Stack newStack;
newStack = init();
newStack->c = c;

Si inizializza un nuovo elemento Stack
Stack newStack;
newStack = init();
newStack->c = c;

Si inizializza un nuovo elemento Stack
newStack->next = *s;
il next contiene un puntatore a s
newStack->next = s;
il next contiene s (una copia del contenuto "originale")
*s = newStack;
l'indirizzo a cui punta s è sostituito dall'indirizzo a cui punta newStack
s = newStack;
s è sostituito dall'indirizzo a cui punta newStack

Al termine di queste operazioni, il contenuto di s nella funzione che utilizza push è cambiato solo nella versione con puntatore; viceversa l'esecuzione di push non ha effetto sulla funzione chiamante nella versione in cui è passato s come valore.

pop

La funzione pop restituisce un char e rimuove l'elemento dalla pila.
char pop(Stack *s) {
char c;
Stack oldS;
oldS = *s;
c = (*s)->c;
*s = (*s)->next;
free(oldS);
return c;
}

Vanno mantenute sia una copia del carattere sia del puntatore, perché dopo aver "spostato" il puntatore a next (*s = (*s)->next;) è necessario prima deallocare lo spazio ormai inutilizzato sia restituire il carattere, che "sopravvive" solo nella copia fatta precedentemente.

Se non si facesse il free dello spazio, questo resterebbe allocato senza che sia puntato da alcun puntatore. Quindi ci sarebbe uno spreco di memoria, crescente a ogni operazione, che si libererebbe solo al termine dell'esecuzione del programma tramite il garbage collector del sistema operativo.

main

main(int argc, char *argv[]) {
Stack s;
char c;
s = init();
push(&s, 'o');
push(&s, 'a');
push(&s, 'i');
push(&s, 'c');
while(!empty(s)) printf("%c", pop(&s));
pop(&s);
getchar();
}

Nel main è necessario passare come parametri non tanto il valore di s, quanto il suo indirizzo di memoria.
L'output di questo esempio sarà "oaic".
Al termine di questo esempio è stato aggiunto un getchar() per comodità.