Pilhas e Filas

Pilhas e Filas

Na disciplina de Estrutura de Dados, exploramos duas estruturas fundamentais com comportamentos específicos: Pilhas (Stacks) e Filas (Queues). Ambas são implementadas sobre listas encadeadas ou vetores, mas com regras distintas de inserção e remoção.

Pilhas (Stacks) - LIFO

Uma pilha segue o princípio LIFO (Last In, First Out) - o último elemento a entrar é o primeiro a sair. É como uma pilha de pratos: você adiciona e remove sempre do topo.

• Push: Insere um elemento no topo
• Pop: Remove o elemento do topo
• Peek/Top: Consulta o elemento do topo sem remover

// Estrutura de nó para pilha struct NoPilha { int valor; struct NoPilha *prox; };

Filas (Queues) - FIFO

Uma fila segue o princípio FIFO (First In, First Out) - o primeiro elemento a entrar é o primeiro a sair. Como uma fila de banco: quem chega primeiro é atendido primeiro.

• Enqueue: Insere no fim da fila
• Dequeue: Remove do início da fila
• Front: Consulta o primeiro elemento sem remover

// Estrutura de nó para fila struct NoFila { int valor; struct NoFila *prox; };

Comparação: Pilhas vs Filas

Implementação de Pilha com Lista Encadeada

void push(struct NoPilha **topo, int valor) { struct NoPilha *novo = malloc(sizeof(struct NoPilha)); novo->valor = valor; novo->prox = *topo; *topo = novo; }
int pop(struct NoPilha **topo) {
if (*topo == NULL) return -1; // Erro
struct NoPilha *temp = *topo;
int valor = temp->valor;
*topo = temp->prox;
free(temp);
return valor;
}

Implementação de Fila com Lista Encadeada

void enqueue(struct NoFila **inicio, struct NoFila **fim, int valor) { struct NoFila *novo = malloc(sizeof(struct NoFila)); novo->valor = valor; novo->prox = NULL;
if (*fim == NULL) {
    *inicio = *fim = novo;
} else {
    (*fim)->prox = novo;
    *fim = novo;
}
}

int dequeue(struct NoFila **inicio, struct NoFila **fim) {
if (*inicio == NULL) return -1; // Erro
struct NoFila *temp = *inicio;
int valor = temp->valor;
inicio = temp->prox;
if (inicio == NULL) *fim = NULL;
free(temp);
return valor;
}

Aplicações Práticas

Fila Circular

Uma variação eficiente de fila que reutiliza espaços liberados no início do vetor, evitando desperdício de memória:

#define TAM 5 struct FilaCircular { int dados[TAM]; int inicio, fim, quantidade; };
void enfileirarCircular(struct FilaCircular *f, int valor) {
if (f->quantidade == TAM) return; // Cheia
f->dados[f->fim] = valor;
f->fim = (f->fim + 1) % TAM;
f->quantidade++;
}

Fila com Prioridade

Uma variação onde elementos com maior prioridade "furavam" a fila. Implementada com duas filas separadas ou com comparação de prioridade na inserção:

void enfileirarComPrioridade(struct Paciente **inicio, struct Paciente **fim, int idade) { struct Paciente *novo = malloc(sizeof(struct Paciente)); // ... preenche dados if (idade >= 60) { // Prioritário novo->prox = *inicio; *inicio = novo; if (*fim == NULL) *fim = novo; } else { // Comum // Insere no fim normalmente } }

Lista Duplamente Encadeada Circular

Uma estrutura avançada onde cada nó aponta para o anterior e próximo, e o último nó aponta para o primeiro, formando um ciclo:

struct NoCircular { int valor; struct NoCircular *ant, *prox; };
void inserirFimCircular(struct NoCircular **inicio, struct NoCircular **fim, int valor) {
struct NoCircular novo = malloc(sizeof(struct NoCircular));
novo->valor = valor;
if (fim == NULL) { // Lista vazia
*inicio = *fim = novo;
novo->ant = novo->prox = novo;
} else {
novo->ant = fim;
novo->prox = inicio;
(fim)->prox = novo;
(inicio)->ant = novo;
*fim = novo;
}
}