Publicação

Listas, pilhas e filas em C++

foto de
Gabriel Goulart

    Listas,pilhas e filas são estruturas de dados, que nos permitem organizar e interagir com nossos dados e organizá-los de diferentes formas. Em C++ existem bibliotecas que nos permitem implementar esses tipos de estruturas, o que torna nosso trabalho mais simples do que se tivéssemos de criá-las manualmente.
    Primeiro vamos falar sobre pilhas:
    

#include <stack>
#include <iostream>

using namespace std;

int main(){
    stack<int> pilha;
    for(int i=0;i<10;i++){
        pilha.push(i);
    }
    cout << pilha.top() << endl;
    pilha.pop();
    cout << pilha.top() << endl;
    for(int i=0;i<9;i++){
        pilha.pop();
        if(pilha.empty()){
            cout << "Fiquei vazia na iteração: " << i+1 << endl;
        }
}

    A biblioteca para se usar pilha em c++ é a "stack". Logo após declararmos nossa "stack", indicando qual tipo de dado colocaremos nela, com o nome pilha, temos um for e uma função chamada push(). A função push é a função que nos permite empilhar os nossos objetos em nossa pilha. Caso não saibam, uma pilha funciona seguindo o padrao FILO (First in Last out), que significa que o primeiro elemento a entrar é o ultimo a sair, como se os elementos realmente estivessem empilhados um em cima do outro.
    Logo a seguir temos a função top(), que nos retorna o elemento do topo sem removê-lo. Já a função pop() remove o elemento no topo da lista porém não retorna o seu valor. Na primeira vez que printamos no console o top(), teremos o valor 9. Depois de darmos o pop e printarmos o top de novo, teremos o valor 8. No ultimo for temos a função empty(), que retornará true caso a pilha esteja vazia. Ou seja, só entraremos naquele if na ultima iteração e o print que aparecerá será "Fiquei vazia na iteração 8".
    Em seguida temos filas. Filas seguem o padrão FIFO (First In First Out), ou seja, o primeiro a chegar é o primeiro a sair.
    

#include <iostream>
#include <queue>

using namespace std;

int main(){
	queue<int> fila;
	for(int i=0;i<10;i++){
		fila.push(i);
	}
	cout << fila.front() << endl;
	cout << fila.pop() << endl;
	cout << fila.front() << endl;

	for(int i=0;i<9;i++){
		fila.pop();
		if(fila.empty()){
			cout << "Vazio na iteração " << i+1 << endl;
		}
	}
}

    Como podemos ver em fila temos funções semelhantes as de pilha. As diferenças são poucas, como o include, que deixa de ser "stack" para "queue" e ao invés de top() em fila temos front(). A principal diferença é que na pilha ao usarmos top() veríamos o ultimo elemento que foi adicionado a pilha (no exemplo acima o 9), já na fila ao usarmos front() vemos o primeiro elemento (Nesse caso o 0) e ao usarmos pop() o nosso próximo elemento será o inteiro de valor 1.

    Já a lista é, de certa forma, uma estrutura mais completa, porque podemos utilizá-la de diversas formas, incluindo no estilo de pilha e fila. Em uma lista podemos adicionar um elemento tanto no inicio quanto no fim da lista, assim como podemos escolher se vamos retirar o elemento do inicio ou do fim também! Porém em uma lista podemos inserir os elementos onde queremos assim como remover o elemento que quisermos. Vamos ver:
    

#include <iostream>
#include <list>

using namespace std;

int main(){
	list<int> lista;
	list<int>::iterator it;
	for(int i=0;i<5;i++){
		lista.push_back(i);
	}
	for(int i=5;i<10;i++){
		lista.push_front(i);
	}
    // Conteudo da lista: 9 8 7 6 5 0 1 2 3 4
    cout << lista.front() << endl;
    //printa 9 na tela
    cout << lista.back() << endl;
    // printa 4 na tela
    cout << lista.size() << endl;
    //printa o tamanho da lista na tela, que é igual a 10

	for(it = lista.begin(); it!=lista.end();it++){
		//printa os numeros pares começando do inicio da lista
		if(*it %2 == 0){
			cout << *it << endl;
		}
	}
    it--;
    // adiciona dois 11 antes do 4 na lista
    lista.insert(it,2,11);
	for(it = lista.begin(); it!=lista.end();it++){
		//printa os numeros pares
		cout << *it << " ";
	}
	cout << endl;
	it--;
    //retira o 4 da lista
	lista.erase(it);
    // printa o 3 que agora é o novo ultimo elemento da lista
	cout << lista.back() << endl;
    // limpa a lista inteira
	lista.clear();
    // printará 0 pois a lista está vazia
	cout << lista.size() << endl;
}

    Primeiro vamos começar com os comandos pusb_back() e push_front(). Eles respectivamente adicionam o elemento passado no final da lista e no inicio da lista (nos comentários temos os resultados dos prints). Em seguida checamos qual o nosso primeiro elemento e qual o nosso ultimo respectivamente. Depois temos a função size() (que também existe para filas e pilhas) que nos retorna o tamanho da nossa lista. Agora temos a grande diferença de lista para os demais, em listas podemos iterar entre todos os elementos ,assim como fazemos em um vetor. Porém para isso precisamos de um iterador, o nosso iterator it que nada mais é do que um ponteiro que aponta para elementos de listas que tenham o tipo int como dado.
    os comandos begin() e end() retornam respectivamente um ponteiro para o inicio e para o fim da lista, a diferença é que o ponteiro do begin aponta realmente para o primeiro elemento da lista enquanto o end aponta para depois do ultimo elemento. Depois que pritamos todos os numeros pares, usamos o it-- para voltarmos a apontar para o ultimo elemento e usamos a função insert(). Essa função nos permite inserir elementos na posição anterior a que nosso iterador está apontando. O segundo parâmetro é opcional e serve para dizermos quantas cópias daquele elemento queremos inserir (O default é 1). Em seguida temos o erase(), que apaga o elemento que nosso iterador está apontando. Por fim temos a função clear(), que limpa nossa lista inteira!
Para mais informações sobre listas em c++ dá uma olhada no link:http://www.cplusplus.com/reference/list/list/

Comentários