C Pilhas e Filas

Muitos programas guardam coisas para usar depois, e a ordem em que elas saem é o que importa. O Ctrl+Z de um editor desfaz primeiro a última coisa que você fez. O caixa do banco chama primeiro quem chegou primeiro. Esses dois jeitos têm nome: pilha e fila. Nesta aula você vai construir os dois em C, primeiro com um array e depois com uma lista ligada, e vai ver o truque do array circular.

Esta aula usa structs, passar por ponteiro e listas ligadas. Todos os programas foram compilados com o gcc 15.2 na máquina fictícia da Ana (usuária ana, computador notebook), na pasta ~/c, com o comando padrão do guia: gcc -std=c23 -Wall -Wextra arquivo.c -o programa.

A ideia: pratos e o banco

Na cozinha da Ana, os pratos limpos ficam empilhados. Ela sempre põe o prato novo em cima e sempre tira o prato de cima. O prato que está embaixo de todos foi o primeiro a ser guardado e vai ser o último a ser usado. Isso é uma pilha (em inglês, stack).

No banco, as pessoas pegam uma senha e entram na fila. Quem chega vai para o fim; o caixa chama quem está no começo. Quem chegou primeiro é atendido primeiro. Isso é uma fila (em inglês, queue).

Nenhuma das duas deixa você mexer no meio. Essa é a graça: com só duas operações, não tem como errar a ordem.

1. Pilha com array

A forma mais simples de pilha é um array e um número, topo, que diz quantos itens estão guardados. Os itens moram em itens[0], itens[1]… e o de cima está em itens[topo - 1]:

#include <stdio.h>

#define MAX 5

typedef struct {
    int itens[MAX];
    int topo;
} Pilha;

bool push(Pilha *p, int valor) {
    if (p->topo == MAX) {
        return false;
    }
    p->itens[p->topo] = valor;
    p->topo++;
    return true;
}

bool pop(Pilha *p, int *saida) {
    if (p->topo == 0) {
        return false;
    }
    p->topo--;
    *saida = p->itens[p->topo];
    return true;
}

bool ver_topo(const Pilha *p, int *saida) {
    if (p->topo == 0) {
        return false;
    }
    *saida = p->itens[p->topo - 1];
    return true;
}

int main(void) {
    Pilha pratos = {.topo = 0};
    for (int i = 1; i <= 6; i++) {
        if (push(&pratos, i * 10)) {
            printf("push %d\n", i * 10);
        } else {
            printf("push %d: pilha cheia!\n", i * 10);
        }
    }
    int x;
    if (ver_topo(&pratos, &x)) {
        printf("Topo: %d (com %d itens)\n", x, pratos.topo);
    }
    while (pop(&pratos, &x)) {
        printf("pop %d\n", x);
    }
    printf("Vazia: %s\n", pratos.topo == 0 ? "sim" : "não");
    return 0;
}

$ gcc -std=c23 -Wall -Wextra pilha_array.c -o pilha_array
$ ./pilha_array
push 10
push 20
push 30
push 40
push 50
push 60: pilha cheia!
Topo: 50 (com 5 itens)
pop 50
pop 40
pop 30
pop 20
pop 10
Vazia: sim

#define MAX 5

A capacidade da pilha. Com um array, ela é fixa: o sexto push é recusado.

int topo;

Quantos itens estão na pilha. Também é a posição livre onde o próximo item vai entrar.

Pilha pratos = {.topo = 0};

Começa vazia. O .topo = 0 é um inicializador designado C99: dá valor ao campo pelo nome, e os campos não citados (o array) ficam zerados.

bool push(Pilha *p, int valor)

Recebe a pilha por ponteiro, para poder mudá-la, e devolve false se ela estiver cheia. Quem chama confere.

p->itens[p->topo] = valor; p->topo++;

Guarda na posição livre e sobe o topo.

bool pop(Pilha *p, int *saida)

O valor tirado sai pelo ponteiro saida; o retorno diz se deu certo. Assim, "pilha vazia" nunca se confunde com um valor de verdade.

p->topo--; *saida = p->itens[p->topo];

Desce o topo e lê o item que estava lá em cima. O valor continua no array, mas agora está na parte "livre" e vai ser sobrescrito no próximo push.

ver_topo

Olha o item de cima sem tirar. Em inglês é o peek ("espiar") ou top.

while (pop(&pratos, &x))

Desempilha até o pop devolver false. Repare que os números saíram na ordem contrária à que entraram.

ahlip

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

#define MAX 20

typedef struct {
    char letras[MAX];
    int topo;
} Pilha;

bool push(Pilha *p, char c) {
    if (p->topo == MAX) {
        return false;
    }
    p->letras[p->topo++] = c;
    return true;
}

bool pop(Pilha *p, char *saida) {
    if (p->topo == 0) {
        return false;
    }
    *saida = p->letras[--p->topo];
    return true;
}

int main(void) {
    const char *palavra = "pilha";
    Pilha p = {.topo = 0};
    for (size_t i = 0; i < strlen(palavra); i++) {
        push(&p, palavra[i]);
    }

    // tire as letras da pilha, uma por uma, e mostre cada uma com putchar

    putchar('\n');
    return 0;
}

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

#define MAX 20

typedef struct {
    char letras[MAX];
    int topo;
} Pilha;

bool push(Pilha *p, char c) {
    if (p->topo == MAX) {
        return false;
    }
    p->letras[p->topo++] = c;
    return true;
}

bool pop(Pilha *p, char *saida) {
    if (p->topo == 0) {
        return false;
    }
    *saida = p->letras[--p->topo];
    return true;
}

int main(void) {
    const char *palavra = "pilha";
    Pilha p = {.topo = 0};
    for (size_t i = 0; i < strlen(palavra); i++) {
        push(&p, palavra[i]);
    }

    char c;
    while (pop(&p, &c)) {
        putchar(c);
    }

    putchar('\n');
    return 0;
}

Repare em p->letras[p->topo++] = c; e p->letras[--p->topo]: são as mesmas duas linhas do pilha_array.c juntadas numa só, com o ++ depois (usa e depois soma) e o -- antes (subtrai e depois usa). Veja ++ e --.

2. Pilha com lista ligada: o desfazer

A pilha com array tem tamanho fixo. Com uma lista ligada, ela cresce enquanto houver memória, e as operações já existem: push é inserir no início e pop é remover o primeiro. O topo é a cabeça da lista.

Vamos fazer o "desfazer" de um editor de texto. Cada ação vai para a pilha; o Ctrl+Z tira a de cima:

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

typedef struct Acao {
    char texto[40];
    struct Acao *abaixo;
} Acao;

bool empilhar(Acao **topo, const char *texto) {
    Acao *a = malloc(sizeof *a);
    if (a == NULL) {
        return false;
    }
    snprintf(a->texto, sizeof a->texto, "%s", texto);
    a->abaixo = *topo;
    *topo = a;
    return true;
}

bool desempilhar(Acao **topo, char *saida, size_t tam) {
    if (*topo == NULL) {
        return false;
    }
    Acao *a = *topo;
    snprintf(saida, tam, "%s", a->texto);
    *topo = a->abaixo;
    free(a);
    return true;
}

int main(void) {
    Acao *historico = NULL;
    const char *feitas[] = {"digitou \"Olá\"", "pôs negrito", "trocou a cor"};
    for (int i = 0; i < 3; i++) {
        if (!empilhar(&historico, feitas[i])) {
            fprintf(stderr, "Sem memória\n");
            return 1;
        }
        printf("Fez: %s\n", feitas[i]);
    }
    char ultima[40];
    for (int i = 0; i < 2; i++) {
        if (desempilhar(&historico, ultima, sizeof ultima)) {
            printf("Ctrl+Z desfez: %s\n", ultima);
        }
    }
    printf("Ainda pode desfazer: %s\n", historico != NULL ? historico->texto : "nada");
    while (desempilhar(&historico, ultima, sizeof ultima)) {
    }
    return 0;
}

$ gcc -std=c23 -Wall -Wextra -g desfazer.c -o desfazer
$ ./desfazer
Fez: digitou "Olá"
Fez: pôs negrito
Fez: trocou a cor
Ctrl+Z desfez: trocou a cor
Ctrl+Z desfez: pôs negrito
Ainda pode desfazer: digitou "Olá"

O valgrind confirma que o laço final devolveu tudo (3 ações + o bloco do printf):

$ valgrind --leak-check=full ./desfazer 2>&1 | tail -8
==64513== HEAP SUMMARY:
==64513==     in use at exit: 0 bytes in 0 blocks
==64513==   total heap usage: 4 allocs, 4 frees, 4,240 bytes allocated
==64513==
==64513== All heap blocks were freed -- no leaks are possible
==64513==
==64513== For lists of detected and suppressed errors, rerun with: -s
==64513== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

O 2>&1 | tail -8 junta o relatório do valgrind (que sai no stderr) com a saída normal e mostra só as 8 últimas linhas (veja stdin, stdout e stderr).

3. Fila com lista ligada: o banco

Numa fila, entra-se pelo fim e sai-se pelo começo. Com uma lista ligada, as duas pontas precisam ser rápidas, então a fila guarda dois ponteiros: ini (o próximo a ser atendido) e fim (o último que chegou):

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

typedef struct No {
    int senha;
    struct No *prox;
} No;

typedef struct {
    No *ini;
    No *fim;
} Fila;

bool enfileirar(Fila *f, int senha) {
    No *n = malloc(sizeof *n);
    if (n == NULL) {
        return false;
    }
    n->senha = senha;
    n->prox = NULL;
    if (f->fim == NULL) {
        f->ini = n;
    } else {
        f->fim->prox = n;
    }
    f->fim = n;
    return true;
}

bool desenfileirar(Fila *f, int *senha) {
    if (f->ini == NULL) {
        return false;
    }
    No *n = f->ini;
    *senha = n->senha;
    f->ini = n->prox;
    if (f->ini == NULL) {
        f->fim = NULL;
    }
    free(n);
    return true;
}

int main(void) {
    Fila banco = {NULL, NULL};
    for (int s = 1; s <= 3; s++) {
        if (!enfileirar(&banco, s)) {
            return 1;
        }
        printf("Chegou a senha %d\n", s);
    }
    int s;
    if (desenfileirar(&banco, &s)) {
        printf("Caixa chama: %d\n", s);
    }
    if (enfileirar(&banco, 4)) {
        printf("Chegou a senha 4\n");
    }
    while (desenfileirar(&banco, &s)) {
        printf("Caixa chama: %d\n", s);
    }
    return 0;
}

$ gcc -std=c23 -Wall -Wextra -g fila_lista.c -o fila_lista
$ ./fila_lista
Chegou a senha 1
Chegou a senha 2
Chegou a senha 3
Caixa chama: 1
Chegou a senha 4
Caixa chama: 2
Caixa chama: 3
Caixa chama: 4
$ valgrind -q --leak-check=full ./fila_lista
Chegou a senha 1
Chegou a senha 2
Chegou a senha 3
Caixa chama: 1
Chegou a senha 4
Caixa chama: 2
Caixa chama: 3
Caixa chama: 4

As senhas foram chamadas na ordem em que chegaram, mesmo com a senha 4 chegando no meio do atendimento. O valgrind -q não reclamou de nada: nenhum vazamento.

Fila banco = {NULL, NULL};

Fila vazia: os dois ponteiros em NULL.

if (f->fim == NULL) f->ini = n;

enfileirar numa fila vazia: o nó novo é o começo e o fim ao mesmo tempo.

else f->fim->prox = n;

Senão, o último de agora aponta para o novo. Sem andar pela lista: o fim já está guardado.

f->fim = n;

Nos dois casos, o novo vira o fim.

f->ini = n->prox;

desenfileirar: o segundo da fila passa a ser o primeiro.

if (f->ini == NULL) f->fim = NULL;

Se a fila esvaziou, o fim também precisa voltar a NULL. Sem esta linha, ele fica apontando para o nó que o free vai devolver (veja Quando dá errado).

4. Fila com array circular

Dá para fazer fila com array, mas tem uma pegadinha. Se o começo da fila andar para a direita a cada atendimento, logo ele chega ao fim do array, mesmo com o array quase vazio. Empurrar todo mundo para a esquerda a cada atendimento resolveria, mas é lento.

O truque é tratar o array como um círculo, como as cadeiras numa mesa redonda: depois da última posição vem a primeira de novo. Quem faz a volta é o resto da divisão, o % (veja Operadores Aritméticos): com 4 posições, (3 + 1) % 4 dá 0.

#include <stdio.h>

#define CAP 4

typedef struct {
    int itens[CAP];
    int ini;
    int qtd;
} Fila;

bool enfileirar(Fila *f, int valor) {
    if (f->qtd == CAP) {
        return false;
    }
    int fim = (f->ini + f->qtd) % CAP;
    f->itens[fim] = valor;
    f->qtd++;
    printf("  entra %d na posição %d\n", valor, fim);
    return true;
}

bool desenfileirar(Fila *f, int *saida) {
    if (f->qtd == 0) {
        return false;
    }
    *saida = f->itens[f->ini];
    printf("  sai %d da posição %d\n", *saida, f->ini);
    f->ini = (f->ini + 1) % CAP;
    f->qtd--;
    return true;
}

int main(void) {
    Fila f = {.ini = 0, .qtd = 0};
    int x;
    for (int s = 1; s <= 4; s++) {
        enfileirar(&f, s);
    }
    if (!enfileirar(&f, 99)) {
        printf("  fila cheia: 99 não entrou\n");
    }
    desenfileirar(&f, &x);
    desenfileirar(&f, &x);
    enfileirar(&f, 5);
    enfileirar(&f, 6);
    while (desenfileirar(&f, &x)) {
    }
    return 0;
}

$ gcc -std=c23 -Wall -Wextra circular.c -o circular
$ ./circular
  entra 1 na posição 0
  entra 2 na posição 1
  entra 3 na posição 2
  entra 4 na posição 3
  fila cheia: 99 não entrou
  sai 1 da posição 0
  sai 2 da posição 1
  entra 5 na posição 0
  entra 6 na posição 1
  sai 3 da posição 2
  sai 4 da posição 3
  sai 5 da posição 0
  sai 6 da posição 1

int ini; int qtd;

A posição do primeiro da fila e quantos itens existem. Com os dois, dá para calcular tudo.

int fim = (f->ini + f->qtd) % CAP;

A posição livre depois do último. Com ini = 2 e qtd = 2: (2 + 2) % 4 = 0. A fila "dá a volta" e usa a posição 0, que o 1 tinha deixado livre.

f->ini = (f->ini + 1) % CAP;

Depois de tirar o primeiro, o começo anda uma casa, também dando a volta: de 3 vai para 0.

if (f->qtd == CAP)

Cheia. Com qtd guardado à parte, "cheia" e "vazia" nunca se confundem (as duas teriam ini igual ao fim).

#include <stdio.h>

#define CAP 4

typedef struct {
    int itens[CAP];
    int ini;
    int qtd;
} Fila;

bool enfileirar(Fila *f, int valor) {
    if (f->qtd == CAP) {
        return false;
    }
    int fim = (f->ini + f->qtd) % CAP;
    f->itens[fim] = valor;
    f->qtd++;
    printf("  entra %d na posição %d\n", valor, fim);
    return true;
}

bool desenfileirar(Fila *f, int *saida) {
    if (f->qtd == 0) {
        return false;
    }
    *saida = f->itens[f->ini];
    printf("  sai %d da posição %d\n", *saida, f->ini);
    f->ini = (f->ini + 1) % CAP;
    f->qtd--;
    return true;
}

int main(void) {
    Fila f = {.ini = 0, .qtd = 0};
    int x;
    for (int s = 1; s <= 4; s++) {
        enfileirar(&f, s);
    }
    if (!enfileirar(&f, 99)) {
        printf("  fila cheia: 99 não entrou\n");
    }
    desenfileirar(&f, &x);
    desenfileirar(&f, &x);
    enfileirar(&f, 5);
    enfileirar(&f, 6);
    while (desenfileirar(&f, &x)) {
    }
    return 0;
}

Formas diferentes

Qual usar

• Sabe o máximo de itens (uma pilha de até 100 parênteses, uma fila de até 50 pedidos)? Use o array: menos código, nenhum malloc, nada para liberar.
• Não sabe quantos vão ser (o histórico do desfazer, mensagens chegando)? Use a lista ligada, ou um array que cresce com realloc.
• Qualquer que seja a escolha, esconda-a atrás das funções (push, pop, enfileirar…). Quem usa a pilha não precisa saber se ela é array ou lista, e você pode trocar depois sem mexer no resto do programa.

Quando dá errado

#include <stdio.h>

#define MAX 5

typedef struct {
    int itens[MAX];
    int topo;
} Pilha;

int pop(Pilha *p) {
    p->topo--;
    return p->itens[p->topo];
}

int main(void) {
    Pilha pratos = {.topo = 0};
    int x = pop(&pratos);
    printf("Tirei %d; agora topo = %d\n", x, pratos.topo);
    return 0;
}

$ gcc -std=c23 -Wall -Wextra pop_vazia.c -o pop_vazia
$ ./pop_vazia
Tirei 0; agora topo = -1

$ gcc -std=c23 -Wall -Wextra -g -fsanitize=address pop_vazia.c -o pop_vazia
$ ./pop_vazia
=================================================================
==62258==ERROR: AddressSanitizer: stack-buffer-underflow on address 0x76ef711f001c at pc 0x5e09084ec2f2 bp 0x7ffda4d8a480 sp 0x7ffda4d8a470
READ of size 4 at 0x76ef711f001c thread T0
    #0 0x5e09084ec2f1 in pop /home/ana/c/pop_vazia.c:12
    #1 0x5e09084ec418 in main /home/ana/c/pop_vazia.c:17
«  (… mais linhas: o mapa da memória em volta do erro …)
SUMMARY: AddressSanitizer: stack-buffer-underflow /home/ana/c/pop_vazia.c:12 in pop

$ gcc -std=c23 -Wall -Wextra sem_resto.c -o sem_resto
$ ./sem_resto
  entra 1 na posição 0
  entra 2 na posição 1
  entra 3 na posição 2
  entra 4 na posição 3
  fila cheia: 99 não entrou
  sai 1 da posição 0
  sai 2 da posição 1
  entra 5 na posição 4
  entra 6 na posição 8
  sai 4 da posição 5
  sai 44602368 da posição 6
  sai -914074094 da posição 7
  sai 6 da posição 8

$ gcc -std=c23 -Wall -Wextra -g fim_solto.c -o fim_solto
$ ./fim_solto
Primeiro da fila: ninguém
$ valgrind -q ./fim_solto
==62531== Invalid write of size 8
==62531==    at 0x4001213: enfileirar (fim_solto.c:24)
==62531==    by 0x40012E9: main (fim_solto.c:46)
==62531==  Address 0x4aa6048 is 8 bytes inside a block of size 16 free'd
==62531==    at 0x48538BF: free (vg_replace_malloc.c:990)
==62531==    by 0x4001282: desenfileirar (fim_solto.c:37)
==62531==    by 0x40012D8: main (fim_solto.c:45)
==62531==  Block was alloc'd at
==62531==    at 0x4850858: malloc (vg_replace_malloc.c:447)
==62531==    by 0x40011C5: enfileirar (fim_solto.c:15)
==62531==    by 0x40012C5: main (fim_solto.c:44)
==62531==
Primeiro da fila: ninguém

Referência rápida

Exercícios

Missão final: conferir os parênteses

(a[b]{c}) -> ok
(] -> erro
((x) -> erro
{[()]} -> ok
) -> erro

#include <stdio.h>

#define MAX 100

typedef struct {
    char itens[MAX];
    int topo;
} Pilha;

bool push(Pilha *p, char c) {
    if (p->topo == MAX) {
        return false;
    }
    p->itens[p->topo++] = c;
    return true;
}

bool pop(Pilha *p, char *saida) {
    if (p->topo == 0) {
        return false;
    }
    *saida = p->itens[--p->topo];
    return true;
}

// Devolve o par de abertura de um fechamento: ')' -> '(', ']' -> '[', '}' -> '{'
char par(char fecha) {
    switch (fecha) {
        case ')': return '(';
        case ']': return '[';
        default:  return '{';
    }
}

bool balanceado(const char *s) {
    Pilha p = {.topo = 0};
    for (int i = 0; s[i] != '\0'; i++) {
        char c = s[i];
        // COMPLETE: abertura ( [ { -> push
        //           fechamento ) ] } -> pop e confira se combina com par(c)
        (void)c;
    }
    return p.topo == 0;
}

int main(void) {
    const char *testes[] = {"(a[b]{c})", "(]", "((x)", "{[()]}", ")"};
    for (int i = 0; i < 5; i++) {
        printf("%s -> %s\n", testes[i], balanceado(testes[i]) ? "ok" : "erro");
    }
    return 0;
}

#include <stdio.h>

#define MAX 100

typedef struct {
    char itens[MAX];
    int topo;
} Pilha;

bool push(Pilha *p, char c) {
    if (p->topo == MAX) {
        return false;
    }
    p->itens[p->topo++] = c;
    return true;
}

bool pop(Pilha *p, char *saida) {
    if (p->topo == 0) {
        return false;
    }
    *saida = p->itens[--p->topo];
    return true;
}

// Devolve o par de abertura de um fechamento: ')' -> '(', ']' -> '[', '}' -> '{'
char par(char fecha) {
    switch (fecha) {
        case ')': return '(';
        case ']': return '[';
        default:  return '{';
    }
}

bool balanceado(const char *s) {
    Pilha p = {.topo = 0};
    for (int i = 0; s[i] != '\0'; i++) {
        char c = s[i];
        if (c == '(' || c == '[' || c == '{') {
            if (!push(&p, c)) {
                return false;
            }
        } else if (c == ')' || c == ']' || c == '}') {
            char aberto;
            if (!pop(&p, &aberto) || aberto != par(c)) {
                return false;
            }
        }
    }
    return p.topo == 0;
}

int main(void) {
    const char *testes[] = {"(a[b]{c})", "(]", "((x)", "{[()]}", ")"};
    for (int i = 0; i < 5; i++) {
        printf("%s -> %s\n", testes[i], balanceado(testes[i]) ? "ok" : "erro");
    }
    return 0;
}

Repare nos três jeitos de errar: (] fecha com o par errado; ((x) sobra um ( na pilha no fim; ) tenta tirar de uma pilha vazia. O seu gcc faz algo parecido quando diz expected ‘}’ at end of input (veja Lendo Erros do Compilador).

Resumo

• Pilha: o último que entra é o primeiro que sai (LIFO). Operações: push, pop e ver o topo. Usos: desfazer, voltar, conferir parênteses.
• Fila: o primeiro que entra é o primeiro que sai (FIFO). Operações: enfileirar (no fim) e desenfileirar (do começo). Usos: atendimento por ordem de chegada, filas de tarefas.
• Pilha com array: itens[] + topo (quantos itens = a próxima posição livre). Pilha com lista: push = inserir no início, pop = remover o primeiro.
• Fila com lista: ponteiros ini e fim; quando esvaziar, zere os dois. Fila com array: circular, com ini, qtd e toda conta de posição terminando em % CAP.
• Sempre confira vazia antes de tirar e cheia antes de pôr; devolva bool e entregue o valor por ponteiro. Na lista, cada item tirado ganha o seu free.