C++ stack e queue

Algumas listas têm uma regra de quem sai primeiro. Na pilha de pratos da cozinha da Ana, você sempre pega o prato de cima, o último que foi colocado. Na fila do banco, quem é atendido é quem chegou primeiro. O C++ tem uma "caixa" pronta para cada uma dessas regras: std::stack (pilha) e std::queue (fila). Elas fazem menos coisas que um std::vector, e é exatamente por isso que são úteis: não deixam você quebrar a regra sem querer.

Os programas desta aula foram compilados com o g++ 15.2 na máquina fictícia da Ana (usuária ana, computador notebook), na pasta ~/cpp, com o comando padrão do guia: g++ -std=c++23 -Wall -Wextra arquivo.cpp -o programa (veja Compilar com g++). Antes desta aula, vale ter visto std::vector e list e deque.

A ideia: a pilha de pratos e a fila do banco

Pense em duas cenas do dia a dia:

• A pilha de pratos. A Ana lava um prato e coloca em cima da pilha. Quando precisa de um, pega o de cima. O prato que está lá embaixo, o primeiro que ela guardou, vai ser o último a sair.
• A fila do banco. Quem chega vai para o fim da fila. O caixa chama quem está na frente. Quem chegou primeiro é atendido primeiro.

Stack quer dizer "pilha" e queue (pronuncia-se "kiú") quer dizer "fila". As duas estão na biblioteca padrão (a STL, aula O que é a STL) e são chamadas de adaptadores de container: por baixo, elas guardam os elementos num std::deque, mas só mostram para você as operações que respeitam a regra.

1. std::stack: a pilha

Para usar a pilha, inclua o cabeçalho <stack>. Entre os sinais < > você diz o tipo do que vai guardar, como no std::vector:

#include <iostream>
#include <stack>
#include <string>

int main() {
    std::stack<std::string> pratos;

    pratos.push("prato azul");
    pratos.push("prato verde");
    pratos.push("prato vermelho");

    std::cout << "Pratos na pilha: " << pratos.size() << '\n';
    std::cout << "No topo: " << pratos.top() << '\n';

    pratos.pop();
    std::cout << "Depois do pop, no topo: " << pratos.top() << '\n';
    std::cout << "Pratos na pilha: " << pratos.size() << '\n';
}

#include <stack>

Traz a std::stack para o programa.

std::stack<std::string> pratos;

Cria uma pilha vazia chamada pratos, que guarda textos.

pratos.push("prato azul");

Push = "empurrar". Coloca um elemento no topo. Depois dos três push, o vermelho está em cima e o azul está embaixo.

pratos.size()

Quantos elementos a pilha tem agora.

pratos.top()

Top = "topo". Olha o elemento de cima, sem tirá-lo.

pratos.pop();

Pop = "estourar", "tirar". Remove o elemento de cima e não devolve nada.

$ g++ -std=c++23 -Wall -Wextra pilha.cpp -o pilha
$ ./pilha
Pratos na pilha: 3
No topo: prato vermelho              « o último que entrou
Depois do pop, no topo: prato verde
Pratos na pilha: 2

Desenhando a pilha a cada passo (o topo está à direita):

1. push("prato azul") → azul
2. push("prato verde") → azul, verde
3. push("prato vermelho") → azul, verde, vermelho
4. top() → olha o vermelho; a pilha não muda.
5. pop() → tira o vermelho: azul, verde

Tirar tudo, do topo até o fundo

O jeito clássico de "percorrer" uma pilha é olhar o topo e tirá-lo, repetindo enquanto ela não estiver vazia. O empty() ("vazia?") responde true ou false:

#include <iostream>
#include <stack>

int main() {
    std::stack<int> pilha;
    for (int i = 1; i <= 4; ++i) {
        pilha.push(i * 10);
    }

    while (!pilha.empty()) {
        std::cout << pilha.top() << ' ';
        pilha.pop();
    }
    std::cout << '\n';
    std::cout << "Vazia? " << std::boolalpha << pilha.empty() << '\n';
}

$ g++ -std=c++23 -Wall -Wextra esvaziar.cpp -o esvaziar
$ ./esvaziar
40 30 20 10                          « entrou 10, 20, 30, 40; saiu ao contrário
Vazia? true

Repare: os números saíram na ordem inversa da que entraram. Essa é a "assinatura" da pilha. O std::boolalpha só faz o cout escrever true em vez de 1 (aula Booleanos). E perceba que, para ler a pilha inteira, você precisou destruí-la: a pilha não deixa olhar o meio. Se precisar ver todos os elementos sem tirá-los, a estrutura certa é um std::vector.

#include <iostream>
#include <stack>
#include <string>

int main() {
    std::stack<std::string> pratos;
    pratos.push("prato azul");
    pratos.push("prato verde");
    pratos.push("prato vermelho");

    std::cout << "No topo: " << pratos.top() << '\n';
    pratos.pop();
    std::cout << "Agora no topo: " << pratos.top() << '\n';
    std::cout << "Restam " << pratos.size() << " pratos\n";
}

pop() não devolve o valor

Quem vem de outras linguagens (Python, Java, JavaScript) costuma escrever x = pilha.pop(), porque lá o pop tira o elemento e devolve. Em C++, não. Veja o que o g++ diz:

#include <iostream>
#include <stack>

int main() {
    std::stack<int> pilha;
    pilha.push(7);
    int x = pilha.pop();
    std::cout << x << '\n';
}

$ g++ -std=c++23 -Wall -Wextra pop_valor.cpp -o pop_valor
pop_valor.cpp: In function ‘int main()’:
pop_valor.cpp:7:22: error: void value not ignored as it ought to be
    7 |     int x = pilha.pop();
      |             ~~~~~~~~~^~

Void value not ignored as it ought to be = "um valor void não foi ignorado, como deveria ser". void quer dizer "nada" (aula Retorno): o pop() devolve nada, e você tentou guardar esse nada num int. O jeito certo são duas linhas: primeiro olhe, depois tire.

int x = pilha.top();   // 1. copia o valor do topo
pilha.pop();           // 2. tira o elemento da pilha

top() numa pilha vazia

Se a pilha está vazia, não existe topo. O que acontece se você pedir mesmo assim?

#include <iostream>
#include <stack>

int main() {
    std::stack<int> pilha;
    std::cout << "Topo: " << pilha.top() << '\n';
}

$ g++ -std=c++23 -Wall -Wextra topo_vazio.cpp -o topo_vazio
$ ./topo_vazio
/usr/include/c++/15/bits/stl_stack.h:260: std::stack<_Tp, _Sequence>::reference std::stack<_Tp, _Sequence>::top() [with _Tp = int; _Sequence = std::deque<int, std::allocator<int> >; reference = int&]: Assertion '!this->empty()' failed.
Abortado                   (imagem do núcleo gravada) ./topo_vazio
$ echo $?
134                                  « 128 + 6: o programa foi abortado (sinal 6, SIGABRT)

Compilou sem nenhum aviso, mas o programa morreu ao rodar. Lendo a mensagem por partes:

/usr/include/c++/15/bits/stl_stack.h:260

O arquivo da biblioteca padrão onde a std::stack está escrita, linha 260: é o código do top().

[with _Tp = int; …]

Detalhes técnicos: era uma pilha de int guardada num std::deque.

Assertion '!this->empty()' failed.

"A conferência a pilha não está vazia falhou." Uma asserção é um teste que a biblioteca faz e que, se falhar, encerra o programa na hora.

Abortado (imagem do núcleo gravada)

Quem escreve isso é o terminal (o bash): o programa foi abortado.

$ g++ -std=c++23 -Wall -Wextra -O2 topo_vazio.cpp -o topo_vazio2
$ ./topo_vazio2
Falha de segmentação       (imagem do núcleo gravada) ./topo_vazio2

2. Uso real: desfazer (Ctrl+Z)

Todo editor de texto tem o "desfazer". Por trás, quase sempre há uma pilha: antes de cada mudança, o programa guarda o estado antigo no topo. Quando você aperta Ctrl+Z, ele pega o estado do topo, que é o mais recente, e volta para ele.

#include <iostream>
#include <stack>
#include <string>

int main() {
    std::string texto;
    std::stack<std::string> historico;

    // Cada vez que a Ana digita, guardamos o texto ANTES da mudança
    historico.push(texto);
    texto += "Lista: ";
    historico.push(texto);
    texto += "arroz, ";
    historico.push(texto);
    texto += "feijão, ";
    historico.push(texto);
    texto += "chocolate";
    std::cout << "Texto: " << texto << '\n';

    // Ctrl+Z duas vezes
    for (int i = 1; i <= 2; ++i) {
        if (!historico.empty()) {
            texto = historico.top();
            historico.pop();
        }
        std::cout << "Desfazer " << i << ": " << texto << '\n';
    }
}

$ g++ -std=c++23 -Wall -Wextra desfazer.cpp -o desfazer
$ ./desfazer
Texto: Lista: arroz, feijão, chocolate
Desfazer 1: Lista: arroz, feijão,    « o chocolate, a última mudança, saiu primeiro
Desfazer 2: Lista: arroz, 

O botão "voltar" do navegador funciona igual: cada página visitada vai para o topo de uma pilha, e "voltar" tira a do topo.

3. std::queue: a fila

A fila fica no cabeçalho <queue>. Ela também tem push, pop, size e empty, mas no lugar do top tem duas "janelas": front (a frente, quem sai) e back (o fim, quem acabou de chegar).

#include <iostream>
#include <queue>
#include <string>

int main() {
    std::queue<std::string> atendimento;

    atendimento.push("Ana");
    atendimento.push("Bruno");
    atendimento.push("Carla");

    std::cout << "Pessoas na fila: " << atendimento.size() << '\n';
    std::cout << "Primeira: " << atendimento.front() << '\n';
    std::cout << "Última: " << atendimento.back() << '\n';

    while (!atendimento.empty()) {
        std::cout << "Atendendo " << atendimento.front() << '\n';
        atendimento.pop();
    }
    std::cout << "Fila vazia.\n";
}

#include <queue>

Traz a std::queue (e também a std::priority_queue, da seção 4).

atendimento.push("Ana");

Coloca a Ana no fim da fila.

atendimento.front()

Olha quem está na frente (o próximo a ser atendido), sem tirar.

atendimento.back()

Olha quem está no fim (o último que chegou).

atendimento.pop();

Tira quem está na frente. Como na pilha, não devolve nada.

$ g++ -std=c++23 -Wall -Wextra fila.cpp -o fila
$ ./fila
Pessoas na fila: 3
Primeira: Ana
Última: Carla
Atendendo Ana                        « na ordem em que chegaram
Atendendo Bruno
Atendendo Carla
Fila vazia.

Compare com a pilha: aqui, quem entrou primeiro (Ana) saiu primeiro. As regras de segurança são as mesmas: front(), back() e pop() numa fila vazia são comportamento indefinido, então confira empty() antes.

A fila não tem top

Um tropeço comum é misturar os nomes da pilha com os da fila:

$ cat fila_top.cpp
#include <queue>

int main() {
    std::queue<int> fila;
    fila.push(1);
    return fila.top();
}
$ g++ -std=c++23 -Wall -Wextra fila_top.cpp -o fila_top
fila_top.cpp: In function ‘int main()’:
fila_top.cpp:6:17: error: ‘class std::queue<int>’ has no member named ‘top’; did you mean ‘pop’?
    6 |     return fila.top();
      |                 ^~~
      |                 pop

Has no member named ‘top’ = "não tem um membro chamado top". O g++ ainda tenta ajudar com did you mean ‘pop’? ("você quis dizer pop?"), mas aqui a sugestão está errada: o que você quer é front(). Para lembrar: pilha tem topo; fila tem frente.

#include <iostream>
#include <queue>
#include <string>

int main() {
    std::queue<std::string> fila;
    std::string nome;

    while (std::cin >> nome) {
        fila.push(nome);
    }

    int senha = 1;
    while (!fila.empty()) {
        std::cout << "Senha " << senha << ": " << fila.front() << '\n';
        fila.pop();
        ++senha;
    }
}

No laboratório, com três nomes na entrada:

$ g++ -std=c++23 -Wall -Wextra atendimento.cpp -o atendimento
$ printf "Ana Bruno Carla\n" | ./atendimento
Senha 1: Ana
Senha 2: Bruno
Senha 3: Carla

4. std::priority_queue: a fila com prioridade (só o básico)

No pronto-socorro, ninguém é atendido por ordem de chegada: quem está em estado mais grave passa na frente. A std::priority_queue ("fila de prioridade") faz isso: o top() é sempre o maior elemento, não importa a ordem em que entraram.

#include <iostream>
#include <queue>

int main() {
    std::priority_queue<int> urgencia;

    urgencia.push(3);
    urgencia.push(9);
    urgencia.push(1);
    urgencia.push(5);

    while (!urgencia.empty()) {
        std::cout << urgencia.top() << ' ';
        urgencia.pop();
    }
    std::cout << '\n';
}

$ g++ -std=c++23 -Wall -Wextra prioridade.cpp -o prioridade
$ ./prioridade
9 5 3 1                              « do maior para o menor, não na ordem de entrada

Repare que ela usa top(), como a pilha, e não front(). Ela não guarda os elementos em ordem por dentro; só garante que o de cima é sempre o maior. Por isso é rápida para "pegar o mais importante", mas não serve para listar tudo em ordem sem esvaziá-la (para isso existe o std::sort, da aula Algoritmos).

Menor primeiro

Para que o menor saia primeiro (por exemplo, a senha de número mais baixo), a declaração fica mais comprida. Você precisa dizer três coisas: o tipo, onde guardar por baixo (std::vector<int>) e como comparar (std::greater<int>, "maior que", de <functional>):

#include <functional>
#include <iostream>
#include <queue>
#include <vector>

int main() {
    std::priority_queue<int, std::vector<int>, std::greater<int>> senhas;

    senhas.push(42);
    senhas.push(17);
    senhas.push(30);

    while (!senhas.empty()) {
        std::cout << senhas.top() << ' ';
        senhas.pop();
    }
    std::cout << '\n';
}

$ g++ -std=c++23 -Wall -Wextra prioridade_menor.cpp -o prioridade_menor
$ ./prioridade_menor
17 30 42

Não se preocupe em decorar essa linha agora. O que importa é a ideia: fila de prioridade = sempre sai o "melhor", e você escolhe o que é "melhor". Prioridades com tipos próprios (structs com uma nota de gravidade, por exemplo) usam o mesmo mecanismo de comparação que você verá em Sobrecarga de Operadores e Lambdas.

Qual usar?

"Mas um std::vector com push_back, back e pop_back também faz uma pilha." Faz, e muita gente usa assim. A vantagem da std::stack é a intenção: quem lê std::stack sabe na hora que ali vale a regra do topo, e ninguém consegue mexer no meio por engano.

Quando dá errado

pop_valor.cpp:7:22: error: void value not ignored as it ought to be
    7 |     int x = pilha.pop();
      |             ~~~~~~~~~^~

$ cat percorrer.cpp
#include <iostream>
#include <stack>

int main() {
    std::stack<int> pilha;
    pilha.push(1);
    pilha.push(2);
    for (int x : pilha) {
        std::cout << x << '\n';
    }
}
$ g++ -std=c++23 -Wall -Wextra percorrer.cpp -o percorrer
percorrer.cpp: In function ‘int main()’:
percorrer.cpp:8:18: error: no matching function for call to ‘begin(std::stack<int>&)’
    8 |     for (int x : pilha) {
      |                  ^~~~~
percorrer.cpp:8:18: note: there are 6 candidates
                                     « … e mais de 100 linhas de notes sobre os 6 candidatos,
                                     « com erros como ‘class std::stack<int>’ has no member named ‘begin’

Referência rápida

A tabela de todos os containers está em Referência: Containers.

Exercícios

Missão: o caixa do banco

Atendida: Ana
Atendida: Bruno
Próxima: Carla
Ainda esperando: 2

#include <iostream>
#include <queue>
#include <string>

int main() {
    std::queue<std::string> fila;
    fila.push("Ana");
    fila.push("Bruno");
    fila.push("Carla");
    fila.push("Davi");

    // atenda duas pessoas aqui

    // mostre a próxima e quantas faltam aqui
}

#include <iostream>
#include <queue>
#include <string>

int main() {
    std::queue<std::string> fila;
    fila.push("Ana");
    fila.push("Bruno");
    fila.push("Carla");
    fila.push("Davi");

    // atenda duas pessoas
    for (int i = 0; i < 2; ++i) {
        std::cout << "Atendida: " << fila.front() << '\n';
        fila.pop();
    }

    std::cout << "Próxima: " << fila.front() << '\n';
    std::cout << "Ainda esperando: " << fila.size() << '\n';
}

Missão final: ROMA ao contrário

#include <iostream>
#include <stack>
#include <string>

int main() {
    std::string palavra = "ROMA";
    std::stack<char> pilha;

    // 1. empilhe cada letra de palavra

    std::string invertida;
    // 2. desempilhe tudo, juntando em invertida

    std::cout << invertida << '\n';
}

#include <iostream>
#include <stack>
#include <string>

int main() {
    std::string palavra = "ROMA";
    std::stack<char> pilha;

    for (char letra : palavra) {
        pilha.push(letra);
    }

    std::string invertida;
    while (!pilha.empty()) {
        invertida += pilha.top();
        pilha.pop();
    }
    std::cout << invertida << '\n';
}

Resultado da solução no laboratório:

$ g++ -std=c++23 -Wall -Wextra roma.cpp -o roma
$ ./roma
AMOR

Resumo

• Pilha (std::stack, <stack>): o último a entrar sai primeiro. push põe no topo, top olha, pop tira.
• Fila (std::queue, <queue>): o primeiro a entrar sai primeiro. push põe no fim, front olha a frente, back olha o fim, pop tira da frente.
• Fila de prioridade (std::priority_queue, <queue>): top é sempre o maior; com std::greater, o menor.
• pop() não devolve nada: leia antes com top()/front().
• Olhar ou tirar de uma pilha/fila vazia é comportamento indefinido: confira empty() antes.
• Pilhas e filas não têm begin/end: não dá para usar for. Se precisar ver o meio, use vector ou deque.
• Próxima aula: Algoritmos, para ordenar, buscar e contar dentro de um vetor sem escrever o laço na mão.