Queue -

Aula por Victor Camilo

Queue vs Vector

Todos vocês com certeza já entraram em uma fila, e você provavelmente se lembra de como funciona, a pessoa mais a frente da fila é a primeira a ser atendida e sair, e as pessoas que chegam sempre vão para o final da fila (não furem filas).

Assim sendo, imagine uma queue como uma estrutura para facilitar e permitir que criemos filas e as manipulemos como tais dentro do código. Para exemplificar, suponha que você tenha alguns elementos em um vector e queira eliminar o primeiro. Teríamos o seguinte código:

	#include <iostream>
	#include <vector>

	using namespace std;

	int main()
	{
	vector<int> V;

	V.push_back(1);
	V.push_back(2);
	V.push_back(3);
	V.push_back(4);
	V.push_back(5);

	// Removendo o primeiro elemento
	for(int i = 0 ; i < (int)V.size() - 1 ; i++)
	{
	V[i] = V[i+1];
	}

	V.pop_back();

	return 0;
	}

view raw Removendo_primeiro_elemento_vector.cpp hosted with ❤ by GitHub

Note que para remover o primeiro elemento, passamos por todos os outros elementos do vector, sendo assim, temos uma complexidade de $O(n)$ para a operação, enquanto usando uma Queue teríamos uma complexidade linear e um código mais simples. No tópico a seguir veremos como utilizar e manipular queues.

Declarando e utilizando uma queue

A declaração desta estrutura é igual a de um vector, e possui aplicação simples e dedutivas, facilitando a resolução de problemas em que pode ser aplicada quando comparada a uma resolução utilizando outras estruturas, por exemplo. Uma queue tem duas operações principais: adicionar um elemento no final de uma fila e remover o elemento no início. Vamos ver como fazer cada um desses por meios dos exemplos a seguir.

	#include <iostream>
	#include <queue>

	using namespace std;

	int main()
	{
	queue<int> fila;

	int n;

	// Adicionando n elementos
	cin >> n;

	for(int i = 0 ; i < n ; i++)
	{
	int id;
	cin >> id;
	fila.push(id);
	}

	// Removendo os n elementos da frente da fila

	for(int i = 0 ; i < n ; i++) fila.pop();

	/*
	Agora imagine uma situaÃ§Ã£o em que hÃ¡ k pessoas inicialmente em uma fila para sacarem
	cada um uma quantia diferente de dinheiro e queremos saber quanto dinheiro foi sacado
	no final enquanto administramos a fila. Cada pessoa tem um id, que vai aumentando de
	1 em 1 a partir do primeiro de acordo com que as pessoas entram na fila.
	*/

	int atv; // variÃ¡vel que vai definir que atividade realizar
	int din; // quantidade de dinheiro sacado por cada pessoa
	int dintotal;// quantidade de dinheiro sacada por todas as pessoas juntas

	int k;
	cin >> k;

	for(int i = 1 ; i < k + 1 ; i++) fila.push(i); // adicionando as pessoas iniciais na fila

	while(cin >> atv)
	{
	if(atv == 1) // Se a atividade for 1, vamos adicionar alguÃ©m na fila ao final da fila
	{
	int id;
	cin >> id;

	fila.push(id);
	}
	else if(atv == 2) // Se a atividade for 2, vamos atender atender a primeira pessoa da fila
	{
	cin >> din; // quantidade de dinheiro que a pessoa sacou
	dintotal += din;
	fila.pop(); // excluimos a pessoa que acabamos de atender da fila
	}

	if(fila.empty()) // se a fila estiver vazia, encerramos o processo
	break;
	}

	cout << dintotal; // apÃ³s acabar o processo, imprimimos a todo o dinheiro sacado

	return 0;
	}

view raw Operacoes_queue.cpp hosted with ❤ by GitHub

Ao lermos o código podemos notar que ambos os processos de adicionar e remover elementos possuem complexidade linear, o que pode nos ser muito útil em problemas nos quais precisamos tratar de filas, e isso torna claro sua utilidade para aplicação na solução de problemas.

Finalização

Agora que já apresentamos o funcionamento de uma queue e o porquê de usá-la, confira nossas outras aulas e teste seus conhecimentos pelos nossos simulados. Para mais métodos utilizando queue, verifique a Referência C++.

Aula por Victor Camilo

Queue vs Vector

Declarando e utilizando uma queue

Finalização

Fale conosco!