Stack e Queue in C

Stack e Queue sono due delle strutture dati fondamentali in C, utilizzate per gestire collezioni di elementi in modo ordinato. Lo stack segue il principio LIFO (Last In, First Out), mentre la queue segue il principio FIFO (First In, First Out). In questa guida, esploreremo come implementare e utilizzare queste strutture dati, con esempi pratici che illustrano il loro funzionamento.

Cos’è uno Stack?

Uno stack è una struttura dati che gestisce gli elementi secondo il principio LIFO, il che significa che l’ultimo elemento inserito è il primo a essere rimosso. Le operazioni principali su uno stack sono:

• Push: Aggiunge un elemento in cima allo stack.
• Pop: Rimuove l’elemento in cima allo stack.
• Peek: Visualizza l’elemento in cima senza rimuoverlo.

Implementazione di uno Stack

Uno stack può essere implementato in C usando un array o una lista collegata. Qui vedremo l’implementazione tramite un array.

Definizione della Struttura Stack

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

#define MAX 100

struct Stack {
    int top;
    int elementi[MAX];
};

Funzioni per Gestire lo Stack

Inizializzazione dello Stack

void init_stack(struct Stack* stack) {
    stack->top = -1;
}

Operazione Push

void push(struct Stack* stack, int valore) {
    if (stack->top >= MAX - 1) {
        printf("Stack Overflow\n");
        return;
    }
    stack->elementi[++(stack->top)] = valore;
}

Operazione Pop

int pop(struct Stack* stack) {
    if (stack->top < 0) {
        printf("Stack Underflow\n");
        return -1;
    }
    return stack->elementi[(stack->top)--];
}

Operazione Peek

int peek(struct Stack* stack) {
    if (stack->top < 0) {
        printf("Stack is empty\n");
        return -1;
    }
    return stack->elementi[stack->top];
}

Esempio Completo di Utilizzo dello Stack

int main() {
    struct Stack stack;
    init_stack(&stack);

    push(&stack, 10);
    push(&stack, 20);
    push(&stack, 30);

    printf("Elemento in cima: %d\n", peek(&stack));

    printf("Elemento rimosso: %d\n", pop(&stack));
    printf("Elemento rimosso: %d\n", pop(&stack));

    return 0;
}

Uscita:

Elemento in cima: 30
Elemento rimosso: 30
Elemento rimosso: 20

Cos’è una Queue?

Una queue è una struttura dati che gestisce gli elementi secondo il principio FIFO, il che significa che il primo elemento inserito è il primo a essere rimosso. Le operazioni principali su una queue sono:

• Enqueue: Aggiunge un elemento alla fine della queue.
• Dequeue: Rimuove l’elemento all’inizio della queue.
• Peek: Visualizza l’elemento all’inizio senza rimuoverlo.

Implementazione di una Queue

Come per lo stack, anche la queue può essere implementata usando un array o una lista collegata. Vediamo l’implementazione con un array.

Definizione della Struttura Queue

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

#define MAX 100

struct Queue {
    int front, rear;
    int elementi[MAX];
};

Funzioni per Gestire la Queue

Inizializzazione della Queue

void init_queue(struct Queue* queue) {
    queue->front = 0;
    queue->rear = 0;
}

Operazione Enqueue

void enqueue(struct Queue* queue, int valore) {
    if (queue->rear == MAX) {
        printf("Queue Overflow\n");
        return;
    }
    queue->elementi[queue->rear++] = valore;
}

Operazione Dequeue

int dequeue(struct Queue* queue) {
    if (queue->front == queue->rear) {
        printf("Queue Underflow\n");
        return -1;
    }
    return queue->elementi[queue->front++];
}

Operazione Peek

int peek_queue(struct Queue* queue) {
    if (queue->front == queue->rear) {
        printf("Queue is empty\n");
        return -1;
    }
    return queue->elementi[queue->front];
}

Esempio Completo di Utilizzo della Queue

int main() {
    struct Queue queue;
    init_queue(&queue);

    enqueue(&queue, 10);
    enqueue(&queue, 20);
    enqueue(&queue, 30);

    printf("Elemento in testa: %d\n", peek_queue(&queue));

    printf("Elemento rimosso: %d\n", dequeue(&queue));
    printf("Elemento rimosso: %d\n", dequeue(&queue));

    return 0;
}

Uscita:

Elemento in testa: 10
Elemento rimosso: 10
Elemento rimosso: 20

Vantaggi e Svantaggi di Stack e Queue

Vantaggi:

• Semplicità: Sia lo stack che la queue sono semplici da implementare e utilizzare.
• Efficienza: Le operazioni di push, pop, enqueue e dequeue sono tutte O(1) (tempo costante).

Svantaggi:

• Dimensione Fissa: Quando implementati con array, la dimensione è fissa e potrebbe causare overflow o sprechi di memoria.
• Accesso Limitato: L’accesso agli elementi è limitato a una sola estremità (stack) o a entrambe le estremità (queue), ma non in mezzo.

Conclusioni

Stack e queue sono fondamentali nella gestione ordinata dei dati e trovano applicazione in molte situazioni pratiche, come la gestione delle chiamate di funzione (stack) o la gestione di task in coda (queue). Capire come implementare queste strutture dati e utilizzare le loro operazioni principali è essenziale per affrontare una vasta gamma di problemi in programmazione. Con la pratica, l’uso di stack e queue diventerà una parte naturale del tuo toolkit di sviluppo in C.