Pilhas e filas

Pilhas e filas são estruturas de dados fundamentais que organizam elementos de forma linear, mas com regras específicas de inserção e remoção. Enquanto a pilha segue o princípio LIFO (Last In, First Out), onde o último elemento inserido é o primeiro a sair, a fila segue o princípio FIFO (First In, First Out), onde o primeiro elemento inserido é o primeiro a sair. Nesta aula, você aprenderá a implementar essas estruturas em C, tanto com arrays quanto com listas encadeadas, e entenderá onde aplicá-las em problemas reais.

Dominar pilhas e filas é essencial para qualquer programador, pois elas aparecem em inúmeros algoritmos e sistemas: desde a pilha de chamadas de funções até o gerenciamento de processos em sistemas operacionais. Vamos explorar desde os conceitos básicos até implementações robustas, com análise de complexidade e boas práticas.

Implementação com array e lista

As pilhas e filas podem ser implementadas de duas maneiras principais: usando um array de tamanho fixo ou usando uma lista encadeada dinâmica. A escolha entre elas depende dos requisitos de memória, desempenho e flexibilidade.

Com arrays, o acesso é direto e rápido, mas o tamanho é fixo, o que pode causar desperdício de memória ou estouro se a capacidade for insuficiente. Já com listas encadeadas, a memória é alocada sob demanda, mas há overhead de ponteiros e o acesso é sequencial. Para pilhas, a implementação com array é simples e eficiente, pois as operações ocorrem apenas em uma extremidade. Para filas, o array exige cuidado com o deslocamento de elementos, mas podemos usar um buffer circular para otimizar.

Pilha com array

Uma pilha com array precisa de um vetor para armazenar os elementos, um inteiro para indicar o topo (índice do último elemento) e, opcionalmente, a capacidade máxima. Inicialmente, o topo é -1 (pilha vazia). As operações principais são push (inserir) e pop (remover), que ajustam o topo conforme necessário.

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

#define MAX 100

typedef struct {
    int items[MAX];
    int top;
} Stack;

void init(Stack *s) {
    s->top = -1;
}

bool isEmpty(Stack *s) {
    return s->top == -1;
}

bool isFull(Stack *s) {
    return s->top == MAX - 1;
}

void push(Stack *s, int value) {
    if (isFull(s)) {
        printf("Erro: pilha cheia\n");
        return;
    }
    s->items[++(s->top)] = value;
}

int pop(Stack *s) {
    if (isEmpty(s)) {
        printf("Erro: pilha vazia\n");
        exit(EXIT_FAILURE);
    }
    return s->items[(s->top)--];
}

int peek(Stack *s) {
    if (isEmpty(s)) {
        printf("Erro: pilha vazia\n");
        exit(EXIT_FAILURE);
    }
    return s->items[s->top];
}

Fila com array (buffer circular)

Uma fila com array linear simples teria complexidade O(n) para remoção, pois precisaríamos deslocar todos os elementos. Para evitar isso, usamos um buffer circular, onde os índices de frente (front) e trás (rear) se movem e quando atingem o fim, voltam ao início (usando módulo).

#define MAX 100

typedef struct {
    int items[MAX];
    int front;
    int rear;
} Queue;

void initQueue(Queue *q) {
    q->front = 0;
    q->rear = 0;
}

bool isQueueEmpty(Queue *q) {
    return q->front == q->rear;
}

bool isQueueFull(Queue *q) {
    return (q->rear + 1) % MAX == q->front;
}

void enqueue(Queue *q, int value) {
    if (isQueueFull(q)) {
        printf("Erro: fila cheia\n");
        return;
    }
    q->items[q->rear] = value;
    q->rear = (q->rear + 1) % MAX;
}

int dequeue(Queue *q) {
    if (isQueueEmpty(q)) {
        printf("Erro: fila vazia\n");
        exit(EXIT_FAILURE);
    }
    int value = q->items[q->front];
    q->front = (q->front + 1) % MAX;
    return value;
}

Implementação com lista encadeada

Listas encadeadas são ideais quando não se sabe o tamanho máximo ou quando a memória é limitada. Cada nó contém um dado e um ponteiro para o próximo. Para pilhas, inserimos e removemos no início (cabeça). Para filas, mantemos dois ponteiros: um para o início e outro para o fim, permitindo inserção no fim e remoção no início em O(1).

// Nó para lista encadeada
typedef struct Node {
    int data;
    struct Node* next;
} Node;

// Pilha com lista
typedef struct {
    Node* top;
} StackList;

void initStackList(StackList *s) {
    s->top = NULL;
}

bool isStackListEmpty(StackList *s) {
    return s->top == NULL;
}

void pushList(StackList *s, int value) {
    Node *newNode = (Node*)malloc(sizeof(Node));
    if (!newNode) { printf("Erro de alocação\n"); return; }
    newNode->data = value;
    newNode->next = s->top;
    s->top = newNode;
}

int popList(StackList *s) {
    if (isStackListEmpty(s)) { printf("Pilha vazia\n"); exit(EXIT_FAILURE); }
    Node *temp = s->top;
    int value = temp->data;
    s->top = temp->next;
    free(temp);
    return value;
}

// Fila com lista
typedef struct {
    Node *front;
    Node *rear;
} QueueList;

void initQueueList(QueueList *q) {
    q->front = q->rear = NULL;
}

bool isQueueListEmpty(QueueList *q) {
    return q->front == NULL;
}

void enqueueList(QueueList *q, int value) {
    Node *newNode = (Node*)malloc(sizeof(Node));
    if (!newNode) { printf("Erro de alocação\n"); return; }
    newNode->data = value;
    newNode->next = NULL;
    if (q->rear == NULL) {
        q->front = q->rear = newNode;
    } else {
        q->rear->next = newNode;
        q->rear = newNode;
    }
}

int dequeueList(QueueList *q) {
    if (isQueueListEmpty(q)) { printf("Fila vazia\n"); exit(EXIT_FAILURE); }
    Node *temp = q->front;
    int value = temp->data;
    q->front = temp->next;
    if (q->front == NULL) q->rear = NULL;
    free(temp);
    return value;
}

push/pop, enqueue/dequeue

As operações de uma pilha são tradicionalmente chamadas de push (empurrar) e pop (remover). O push adiciona um elemento ao topo, e o pop remove o elemento do topo, retornando-o. Também é comum ter a operação peek (ou top) para consultar o topo sem remover.

Para filas, as operações são enqueue (inserir na extremidade final) e dequeue (remover da extremidade frontal). Em muitas linguagens, essas operações também são chamadas de offer/poll ou add/remove. A operação front permite consultar o primeiro elemento sem removê-lo.

É crucial verificar se a estrutura está vazia ou cheia (no caso de array) antes de realizar as operações, para evitar erros de acesso à memória. Nas implementações acima, usamos funções de verificação como isEmpty e isFull.

Casos de uso

Pilhas são amplamente usadas em algoritmos que exigem retrocesso (backtracking), como o problema das Torres de Hanói, avaliação de expressões matemáticas (notação polonesa reversa), e no controle de chamadas de funções (pilha de execução). Também são a base para algoritmos de busca em profundidade (DFS) em grafos.

Filas são usadas em sistemas que precisam de processamento em ordem de chegada: escalonamento de processos em sistemas operacionais, gerenciamento de impressão, buffers de dados (como em comunicação serial), e busca em largura (BFS) em grafos. Além disso, são utilizadas para implementar caches e em aplicações de simulação.

Exemplos

A seguir, apresentamos um exemplo prático que usa uma pilha para inverter uma string e uma fila para simular uma fila de atendimento.

#include <stdio.h>
#include <string.h>

// Implementação da pilha (reutilizando a estrutura Stack anterior)
// ... (código da pilha)

// Implementação da fila (reutilizando a estrutura Queue anterior)
// ... (código da fila)

int main() {
    // Exemplo com pilha: inverter string
    char str[] = "hello";
    int len = strlen(str);
    Stack s;
    init(&s);
    for (int i = 0; i < len; i++) {
        push(&s, str[i]);
    }
    printf("String invertida: ");
    while (!isEmpty(&s)) {
        printf("%c", pop(&s));
    }
    printf("\n");

    // Exemplo com fila: simular atendimento
    Queue q;
    initQueue(&q);
    enqueue(&q, 1);
    enqueue(&q, 2);
    enqueue(&q, 3);
    printf("Atendendo: ");
    while (!isQueueEmpty(&q)) {
        printf("%d ", dequeue(&q));
    }
    printf("\n");
    return 0;
}

Boas práticas e observações finais

Ao implementar pilhas e filas, sempre considere a possibilidade de estouro (overflow) e underflow. Em aplicações críticas, é preferível usar listas encadeadas para evitar o desperdício de memória e a limitação de tamanho. Além disso, encapsule as operações em funções e use tipos opacos (como estruturas) para facilitar a manutenção.

Lembre-se de liberar a memória alocada dinamicamente quando usar listas encadeadas. Em C, o gerenciamento de memória é manual, então é fundamental evitar vazamentos. Finalmente, entenda bem a complexidade das operações: com arrays, push/pop e enqueue/dequeue são O(1), mas a fila circular exige cuidado com o cálculo de cheio; com listas, todas as operações são O(1) se mantivermos ponteiros adequados.

Referências

• cppreference: Arrays em C
• cppreference: Struct em C
• GeeksforGeeks: Stack Data Structure
• GeeksforGeeks: Queue Data Structure
• POSIX: stdlib.h (malloc, free)
• IBM Documentation: malloc
• Wikipedia: Stack (abstract data type)
• Wikipedia: Queue (abstract data type)

Exercícios

1. Implemente uma pilha usando um array dinâmico (com realloc) que cresce conforme necessário. Teste com 1000 inserções.

Ver resposta

✓ Resposta: Use um ponteiro para int, capacidade e topo. Na função push, se topo == capacidade, use realloc para dobrar a capacidade. Exemplo:

typedef struct { int *items; int top; int capacity; } DynStack;
void pushDyn(DynStack *s, int val) {
    if (s->top == s->capacity) {
        s->capacity = (s->capacity == 0) ? 1 : s->capacity * 2;
        s->items = realloc(s->items, s->capacity * sizeof(int));
    }
    s->items[s->top++] = val;
}

2. Crie uma função que use uma pilha para verificar se os parênteses, colchetes e chaves em uma string estão balanceados.

Ver resposta

✓ Resposta: Percorra a string: se for abertura, push; se for fechamento, verifique se o topo corresponde; se não, retorne false. No final, a pilha deve estar vazia.
3. Implemente uma fila usando duas pilhas (ou seja, simule FIFO com LIFO). As operações devem ser O(1) amortizado.

Ver resposta

✓ Resposta: Use uma pilha para enqueue (empilhe) e outra para dequeue. No dequeue, se a pilha de saída estiver vazia, transfira todos os elementos da pilha de entrada para a de saída (invertendo a ordem) e então pop.
4. Escreva um programa que use uma fila para simular a senha de um banco: os clientes recebem senhas sequenciais e são atendidos na ordem de chegada.

Ver resposta

✓ Resposta: Use um contador para gerar senhas e a fila para armazenar as senhas. Ao chamar um cliente, faça dequeue e imprima a senha.
5. Dada uma fila de inteiros, inverta a ordem dos elementos usando apenas uma pilha e operações de fila (sem outras estruturas).

Ver resposta

✓ Resposta: Desenfileire todos os elementos e empilhe-os na pilha. Depois, desempilhe e enfileire novamente. A fila resultante estará invertida.