Subsecções de Estrutura de Dados

Subsecções de ED Linear

Capítulo 7

Pilha

A pilha é uma estrutura que, como o nome sugere, permite inserção e remoção apenas do “topo”. Isto significa que, ao remover um elemento da pilha, o elemento a ser removido é o último que foi inserido. Também é conhecido como LIFO (last-in first-out).

Pilha

Métodos:

  • push - Insere um elemento na pilha.
  • pop - Remove o elemento do topo da pilha.
  • top - Retorna o elemento do topo da pilha.
  • size - Retorna o tamanho da pilha.
  • empty - Retorna true se estiver vazia, se não, retorna falso.

Exemplo

  • Programa simples que vai inserir elementos na pilha e depois conforme for removendo, printa cada elemento
#include <bits/stdc++.h>
using namespace std;

int main() {
    stack<int> pilha; // construtor, entre <> deve ser inserido o tipo de dado que será armazenado
    pilha.push(2); // o metodo push insere o elemento no topo da pilha
    pilha.push(7);
    pilha.push(8);
    pilha.push(4);

    cout << pilha.size() << endl; // tamanho da pilha

    // enquanto não estiver vazia, remove o elemento do topo e printa ele
    while(!pilha.empty()){
        int elemento = pilha.top();
        cout<<elemento<<" ";

        pilha.pop();
    }

    return 0;
}

Saída

4 8 7 2

Pilha de Mínimo

E se quisermos o seguinte problema:

  • Dado N números em uma pilha, para os últimos Q números na pilha, printe o menor número em toda pilha até então.

Podemos fazer um código que para cada Q últimos números na pilha, podemos ir percorrendo toda a pilha restante, salvando os menores, sem alterar a pilha atual.

#include <bits/stdc++.h>
using namespace std;

int main(){
    stack<int> st;
    st.push(5);
    st.push(3);
    st.push(8);
    st.push(1);
    st.push(7);
    stack<int> st_aux;
    // para os 4 últimos números, printe o menor número de toda a pilha até ele
    for(int q=0; q<4; q++){
        // menor = infinito
        int menor = LLINF;
        // empilha na stack auxiliar
        while(!st.empty()){
            int x = st.top();
            menor = min(x, menor);
            st.pop();
            st_aux.push(x);
        }
        cout<<menor<<endl;
        // desempilha na stack original
        while(!st_aux.empty()){
            int x = st_aux.top();
            st_aux.pop();
            st.push(x);
        }
        if(!st.empty()){
          st.pop();
        }
    }
    return 0;
}

Porém, é claro, a complexidade do código não é boa. ficaria aproximadamente O(Q*N), se o Q e o N forem grandes, certamente levaríamos TLE (Time Limit Exceeded).

A solução para esse problema então, seríamos usar a pilha de mínimo.

Como funciona?

A pilha de mínimo usa um valor auxiliar para armazenar o menor elemento até a inserção atual, podemos usar um stack<pair<int,int>> ou duas stack<int>.

O algoritmo então inicia a inserção de N elementos, e para cada inserção de elemento, vamos verificar se o elemento da stack auxiliar é menor ou maior que o da original, e guardaremos o de menor valor na stack auxiliar.

Pilha-Min

Implementação

#include <bits/stdc++.h>
using namespace std;

int main(){
    stack<pair<int,int>> st;
    int n; cin>>n;
    // recebemos n números
    for(int i=0; i<n; i++){
      int num;
      cin>>num;
      if(st.empty()){
        // num sera o menor valor da pilha.second
        st.push({num,num});
      }else{
        // armazenamos o menor valor entre 
        // o que esta na pilha.second e o num atual
        int menor = st.top().second;
        menor = min(menor, num);
        st.push({num, menor});
      }
    }
    // Para Q consultas
    int q; cin>>q;
    for(int i=0; i<q; i++){
      if(!st.empty()){
        // pega o menor valor
        int val = st.top().second;
        st.pop();
        cout<<val<<endl;
      }
    }
    return 0;
}

E a complexidade fica somente O(N+Q), pois agora conseguimos responder em O(1) cada query.

Referências:

Capítulo 8

Fila

A fila segue o padrão de FIFO (first-in first-out), ao contrário da pilha, o primeiro elemento inserido será o primeiro a ser removido. Ela é muito útil para problemas que precisamos manter os elementos na ordem em que lhes foram dados.

Fila

Métodos

  • push - Adiciona um elemento no fim da fila.
  • front - Retorna o elemento do início da fila.
  • back - Retorna o elemento do final da fila.
  • pop - Remove o elemento do início da fila.
  • empty - Retorna true se estiver vazia, e false caso contrário.
  • size - Retorna quantos elementos tem na fila.

Exemplo

#include <bits/stdc++.h>
using namespace std;

int main(){
    queue<int> q;

    q.push(9);
    q.push(5);
    q.push(6);
    q.push(1);
    q.push(8);

    cout<< q.size() <<endl;

    while(!q.empty()){
        int elemento = q.front();
        cout<<elemento<<" ";

        q.pop();
    }

    return 0;
}

Saída

9 5 6 1 8
Capítulo 9

Fila de Prioridade

Uma fila de prioridade tem como principal característica a ordenação, ela mantém o elemento do topo como sempre sendo o maior (ou o menor) elemento sempre.

Caso esteja fixado para o elemento do topo ser o maior, a fila de prioridade estará em ordem descrescente do topo para baixo. Caso contrário, a ordem será crescente.

Por padrão, ela estará fixado para o elemento do topo ser o maior, logo, estará em ordem decrescente os elementos na fila de prioridade.

As filas de prioridades são muito úteis quando precisamos que nossos elementos sempre estejam ordenados conforme vamos inserindo elementos.

Métodos

  • push - Adiciona um elemento na fila de prioridade.
  • pop - Remove o elemento do topo da fila de prioridade.
  • top - Retorna o valor do topo
  • empty - Retorna true se a fila estiver vazia, caso contrário, retorna false
  • size - Retorna o tamanho da fila de prioridade.
Informação

A complexidade de inserção e remoção é O(log(n)), e a de olhar o topo do heap é O(1).

Exemplo

#include <bits/stdc++.h>
using namespace std;

int main(){
    priority_queue<int> q;

    q.push(9);
    q.push(5);
    q.push(6);
    q.push(1);
    q.push(8);

    cout<< q.size() <<endl;

    while(!q.empty()){
        int elemento = q.top();
        cout<<elemento<<" ";

        q.pop();
    }

    return 0;
}

Saída

9 8 6 5 1

Ordenação pelo menor valor

Para ordenar pelo menor valor usamos a seguinte sintaxe na declaração: priority_queue <int, vector<int>, greater<int>> q

Exemplo 2

#include <bits/stdc++.h>
using namespace std;

int main(){
    priority_queue <int, vector<int>, greater<int>> q;

    q.push(9);
    q.push(5);
    q.push(6);
    q.push(1);
    q.push(8);

    cout<< q.size() <<endl;

    while(!q.empty()){
        int elemento = q.top();
        cout<<elemento<<" ";

        q.pop();
    }

    return 0;
}

Saída

1 5 6 8 9

ED Não Linear

Subpáginas

Subsecções de ED Não Linear

Capítulo 10

Map

O map é uma estrutura interessante pois permite “mapear” chaves à valores, e dado uma chave encontrar o seu valor rapidamente (complexidade depende da implementação). Por exemplo, podemos fazer um map com strings de chave e int de valor, sendo possível recuperar o valor inteiro associado a aquela string rapidamente.

Deve-se ter cuidado com o uso de map pois ele é implementado em c++ como um set de pairs, isto é, vai ter complexidade O(log n) para inserir e modificar dados.

Informação

Existe também o unordered_map, que é uma estrutura que usa hash. No pior caso é linear, mas em média tem complexidade constante. O seu funcionamento é similar ao do map, com a diferença de que seus elementos não estão ordenados.

Métodos

  • insert({key, element}) - Insere uma chave e um valor no map
  • erase() - Remove uma key ou um iterator
  • find(element) - Retorna um iterator da posição do element
  • count - Retorna a quantidade de elementos de uma chave específica
  • size - Retorna o tamanho do map
  • clear - Limpa todo o conteúdo do Map
  • begin - Retorna um iterator para o início do map
  • end - Retorna um iterator para o final do map

Inicialização

#include <bits/stdc++.h>
using namespace std;

int main(){
    // map chave, valor de inteiros

    map<int, int> m; // Inicialização de map vazio
    
    map<int, int> m = {{2, 3}, {4, 6}}; // Inicialização de map com valor 

    m[7] = 3
    m[7] ++; // 4
}

Iteração

#include <bits/stdc++.h>
using namespace std;

int main(){
    // iterando por métodos iterator

    map<int, int> m = {{2, 3}, {4, 6}};


    // Printa a chave e o valor em cada linha
    for(auto it = m.begin(); it != m.end(); it++){
        cout<< it.first <<" "<< it.second<< endl;
    }

    // tambem pode ser escrito como:
    for(auto it: m){
        cout<< it.first << " "<< it.second<< endl;
    }
}

Saída

2 3
4 6

Apagando elemento

#include <bits/stdc++.h>
using namespace std;

int main(){
    // iterando por métodos iterator
    map<int, int> m = {{2, 3}, {4, 6}}
    
    m.erase(m.find(2));
    m.erase(4);
}
Informação

Da primeira maneira, ele apaga em tempo constante, pois está passando um iterator. Da segunda maneira, ele apaga em log(N), pois ele faz uma busca no elemento.

Verificar um elemento

#include <bits/stdc++.h>
using namespace std;

int main(){
    // iterando por métodos iterator
    map<int, int> m = {{2, 3}, {4, 6}}

    if( m.count(2) > 0 ){ // existe uma chave {2}
        cout<< "Elemento existe";
    }else{
        cout<< "Elemento não existe";
    }
}

Saída

Elemento existe
Capítulo 11

Set

A estrutura set é bem parecida com o que conhecemos de conjuntos da matemática; não existem elementos repetidos e a ordem não importa.

A implementação do set, porém, é feita com uma árvore binária de busca, sendo assim permitido inserir, remover e acessar um elemento em O(log n).

A vantagem do set em relação ao vector é que, caso queira inserir um elemento em um vector ordenado e preservar a ordenação, você terá que procurar o lugar que ele deve ser inserido, fazer a inserção e modificar a posição dos elementos à direita dele. Modificar todas as posições à direita tem uma complexidade ruim O(n), então este algoritmo será mais eficiente com o set.

Além da vantagem de eficiência, essas operações com set são feitas com alguns simples métodos!

Métodos

  • insert(element) - Insere um elemento no Set
  • erase() - Remove uma key ou um iterator
  • find(element) - Retorna um iterator da posição do element
  • count - Retorna a quantidade de elementos de uma chave específica
  • size - Retorna o tamanho do set
  • clear - Limpa todo o conteúdo do set
  • begin - Retorna um iterator para o início do set
  • end - Retorna um iterator para o final do set
  • lower_bound(element) - Retorna um iterator para o primeiro valor >= element
  • upper_bound(element) - Retorna um iterator para o primeiro valor > element

Exemplo 1


#include <bits/stdc++.h>
using namespace std;

int main() {
    set<int> s;

    s.insert(3); // insere elemento no set
    cout << s.size() << endl; // tamanho do set

    // para verificar se um elemento está contido no set ou nao podemos utilizar
    // o metodo find; caso nao esteja presente ele retornará o iterator para
    // o fim do set

    if(s.find(2) == s.end()) {
        cout << "O numero 2 nao esta no set" << endl;
    }
    else {
        cout << "O numero 2 esta no set" << endl;
    }

    if(s.find(3) == s.end()) {
        cout << "O numero 3 nao esta no set" << endl;
    }
    else {
        cout << "O numero 3 esta no set" << endl;
    }
    
    s.erase(3); // apaga elemento 3 do set
    
    if(s.find(3) == s.end()) {
        cout << "O numero 3 nao esta no set" << endl;
    }
    else {
        cout << "O numero 3 esta no set" << endl;
    }

    return 0;
}

Outro método extremamente útil é o lower_bound (e o upper_bound). O lower_bound recebe um inteiro x como argumento e retorna o menor inteiro maior ou igual a x. Caso não exista, ele retorna um iterator para o fim do set (set.end()).

Exemplo 2

#include <bits/stdc++.h>
using namespace std;

int main() {
    set<int> s;

    s.insert(3); // insere elemento no set
    s.insert(4);
    s.insert(5);
    s.insert(7);

    auto iterator1 = s.lower_bound(6);
    // se iterator eh igual a s.end() entao nao existe
    if(iterator1 != s.end()) {
        int numero = *iterator1;
        cout << "menor inteiro maior ou igual a 6 eh " << numero << endl;
    }
    else {
        cout << "nao existe inteiro numero maior ou igual a 6" << endl;
    }

    auto iterator2 = s.lower_bound(9);
    // se iterator eh igual a s.end() entao nao existe
    if(iterator2 != s.end()) {
        int numero = *iterator2;
        cout << "menor inteiro maior ou igual a 9 eh " << numero << endl;
    }
    else {
        cout << "nao existe inteiro numero maior ou igual a 9" << endl;
    }

    return 0;
}
Informação

Na verdade, você pode utilizar o lower_bound para qualquer tipo que implemente a operação “<”, como por exemplo o pair<int, int>.