Função deque c ++
Os elementos são frequentemente adicionados na parte traseira e removidos da frente em uma fila normal. Por outro lado, podemos adicionar e remover os componentes da frente e de trás de um deque. A implementação de um deque em C ++ pode ser feita usando uma matriz ou uma lista vinculada.
Abaixo está uma lista da implementação da matriz do deque. Utilizamos as matrizes circulares para implementá-lo porque é uma fila de ponta dupla. A fila de ponta dupla é mais rápida e mais eficiente do que qualquer outra fila quando se trata de adicionar e remover os componentes de ambas as extremidades.
Representação de Deque
Os aspectos demorados de fazer vários processos DEQUE incluem:
- Chegando em elementos: o (1)
- Adição ou exclusão de elementos- o (n)
- Adição ou exclusão de componentes no início do final (1)
Tipos de deque
Vamos verificar os tipos relacionados a Deque em C++.
Entrada deque restrito
A entrada é confinada em uma extremidade, mas permitida nos outros dois.
Saída deque restrito
Neste deque, a saída é proibida em uma extremidade, mas a inserção é permitida nas duas extremidades.
Criação de função deque C ++
Devemos primeiro incluir o arquivo de cabeçalho Deque para gerar um deque em C++.
#incluirDepois de importar esse arquivo, a seguinte sintaxe pode ser usada para gerar um deque:
# Deque deque-name;O tipo de dados que gostaríamos de armazenar no deque é indicado pelo tipo de objeto neste caso. Por exemplo: int, flutuador, string, etc. Deque-name é um nome variável para os dados que vamos usar.
Inicializando a função deque
Em C ++, a função DEQUE pode ser inicializada das seguintes maneiras:
dequedeque
Ambos os métodos são usados para inicializar deque. Em ambos os nomes deque, “arr” é inicializado com valores inteiros 1, 3, 7, 0, 5, 8.
Métodos de Deque
A seguir estão os métodos de Deque:
- Inserir(): Adiciona um novo elemento e devolve um iterador com o primeiro dos elementos recém -adicionados como seu ponto.
- RBegin (): Gera um iterador reverso apontando para o último valor do deque.
- Rend (): Gera um iterador reverso com uma posição inicial antes da origem do deque.
- Cbegin (): Retorna um iterador constante que sempre aponta para o primeiro elemento do contêiner; Como resultado, o iterador só pode ser utilizado para atravessar o deque e não ser modificado.
- Tamanho máximo(): O número de elementos que um recipiente deque pode segurar é devolvido por esta função.
- Atribuir(): Usado para atribuir valores a um recipiente deque que é o mesmo ou diferente.
- REDIMENTE (): Função usada para modificar o tamanho do deque.
- Retrocesso(): Com a ajuda desta função, os componentes podem ser adicionados da traseira a um deque.
- Frente(): É usado para se referir ao elemento inicial do contêiner deque.
- Voltar(): É usado para se referir ao último elemento do contêiner deque.
- Claro(): É usado para limpar todos os elementos de Deque, reduzindo seu tamanho para 0.
- Apagar(): Usado para excluir os objetos de um recipiente de um determinado ponto ou alcance.
- Deque :: vazio (): É usado para determinar se o deque está vazio.
- Operador =: Usado para alocar novos dados para o contêiner e trocar os antigos.
- Operador[]: Usado para se referir ao elemento no operador no local especificado.
- No(): Usado para se referir ao componente presente no local especificado como o parâmetro da função.
- Trocar(): Esta função é usada para trocar as deques do mesmo tipo de dados.
- Começar(): É usado para fornecer um iterador apontando para o objeto inicial do recipiente deque.
- Emplace_front (): Um novo elemento é inserido no recipiente deque usando esta função. O início do deque é alterado para incluir o componente adicional.
- Emplace_back (): Usado para adicionar um novo valor ao recipiente deque. O novo componente está incluído no final do deque.
Deque estrutura de dados
Vamos verificar os detalhes da estrutura de dados DEQUE na seção a seguir:
Procedimentos em um deque
Essas etapas devem ser seguidas antes de realizar as operações subsequentes:
Passo 1: Tome uma matriz n-dimensional (DEQUE). Na primeira posição, coloque dois ponteiros e defina a frente = -1 e traseira = 0.
Configure uma matriz deque e ponteiros.
Inserção na frente
Passo 1: Esta ação adiciona um componente na frente. Verifique a localização da frente.
Se a frente for menor que 5, redefina a frente para N-1 (último índice).
Passo 2: Reduza a frente em 1 se necessário. Agora, adicione a nova chave n à matriz [front]. Vamos supor n = 6.
Inserção na traseira
Passo 1: Esta ação adiciona um componente no raro. Certifique -se de que a matriz não esteja cheia.
Passo 2: Se a fila estiver cheia, redefina o valor traseiro para 0 (r = 0). Caso contrário, levante o raro em 1.
etapa 3: Em uma matriz [traseira], adicione a nova chave 6.
Retire de frente
Passo 1: Um elemento na frente é removido durante o processo. Certifique -se de que o deque não esteja vazio.
Passo 2: A exclusão não é possível se o deque estiver vazio (front = -1) (condição de subfluxo). Defina a frente = -1 apenas e a traseira = -1 se o deque consistir em um elemento como a frente = traseira. Atribua o valor à frente (frente = 0) se a frente estiver no final (front = n - 1). Caso contrário, defina a frente para frente = frente+1.
Retire da parte traseira
Passo 1: Um elemento no final é removido durante o processo. Certifique -se de que o deque não esteja vazio.
Passo 2: A exclusão não é possível se o deque estiver vazio (front = -1) (condição de subfluxo). Defina a frente = -1 e a traseira = -1 se o deque tiver apenas um único elemento (front = traseiro). Caso contrário, prossiga com as seguintes etapas. Vamos seguir em direção à frente, traseira = n - 1 se a traseira estiver na frente (traseira = 0). Caso contrário, defina o raro = raro-1.
Exemplo 1: Criando Deque
Neste exemplo, criamos um deque. Primeiro, incluímos nossos arquivos de cabeçalho "#include" e #include, onde #include comanda o pré -processador para incluir o arquivo de cabeçalho iostream e deque, que contém todas as funções do programa.
#incluir#incluir
usando namespace std;
void Display_deque (DEQUE);
int main ()
deque mydeque 4, 2, 7, 5, 8;
cout << "mydeque values are = ";
para (int var: mydeque)
cout << var << ", ";
retornar 0;
Depois disso, descrevemos uma função de exibição que é usada para executar os valores de deque que atribuímos a ele.
Movendo -se para nossa função principal, o int main () indica que nossa função deve retornar um valor inteiro no final da execução, o que retornamos 0 na conclusão do programa usando uma inicialização uniforme “Deque Mydeque 4, 2, 7 , 5,8 ”. Neste "int" é o tipo de dados de valores que atribuímos e Mydeque é o nome que usamos para o nosso deque. Atribuímos os valores inteiros ao deque chamado Mydeque que são 4, 2, 7, 5, 8. Para exibir nosso deque, usamos o loop for para um tamanho fixo. E então, pressionamos o botão Executar ou F7 para obter a saída do programa.
Exemplo 2: Adicionando mais valores a um deque
Neste exemplo, adicionamos mais valores a um deque. Depois de adicionar os arquivos de cabeçalho necessários para este programa, passamos para nossa principal função do tipo de dados inteiro “Deque var 0, 1, 2”. Neste "int" é o tipo de dados de valores que atribuímos e "var" é o nome que usamos para o nosso deque. Atribuímos os valores inteiros ao deque chamado "var" que são 0, 1 e 2. Em seguida, empurramos dois elementos, elemento 8 na frente do deque e elemento 5 no final do deque, usando as funções push_front () e push_back (). Então, o deque resultante que temos é 8, 0, 1 e 5.
#incluir#incluir
usando namespace std;
int main ()
deque var 0, 1, 2;
cout << "Initial Deque values are: ";
para (const int & var: var)
cout << var << ", ";
var.push_back (5);
var.push_front (8);
cout << "\nFinal Deque values are: ";
para (const int & var: var)
cout << var << ", ";
retornar 0;
Depois que terminamos com a codificação deste exemplo, compilamos e executamos em qualquer compilador. O resultado está representando a saída esperada do código anterior.
Exemplo 3: Atualizando elementos em índices especificados
Neste exemplo, atualizamos os valores em um deque depois de incluir nossos arquivos de cabeçalho "#include" e "#include" para este código executável.
#incluir#incluir
usando namespace std;
int main ()
deque var = 1, 2;
cout << "Initial Deque values are: ";
para (const int & var: var)
cout << var << ", ";
var.em (0) = 3;
var.em (1) = 4;
cout << "\nUpdated Deque values are: ";
para (const int & var: var)
cout << var << ", ";
retornar 0;
Agora, vamos para a nossa principal função, na qual inicializamos nosso deque chamado "var" com os valores 1 e 2. Em seguida, usamos um loop para exibir os valores do nosso deque inicializado. Para atualizar os valores deque, usamos a função AT () (como sabemos, a função AT () é usada para se referir à posição especificada no DEQUE) no índice 0 e 1, atribuindo novos valores a "var". Estes são 3 e 4. Então, nosso dequeue atualizado é 3 e 4. Depois de preparar nosso código, compilamos -o usando qualquer ferramenta do compilador. Aqui está a saída desejada do nosso código:
Exemplo 4: Usando o iterador para remover os valores
Neste exemplo, usamos os iteradores para acessar os elementos no deque. Um objeto que aponta para um elemento dentro de um contêiner é chamado de iterador.
#incluir#incluir
usando namespace std;
int main ()
deque var 0, 3, 5, 8;
deque :: iterator var_iter;
var_iter = var.começar();
int primeiro_element = *var_iter;
cout << "var[0] = " << first_element << endl;
var_iter = var.begin () + 1;
int element_index1 = *var_iter;
cout << "var[1] = " << element_index1 << endl;
var_iter = var.end () - 1;
int last_element = *var_iter;
cout << "var[2] = " << last_element;
retornar 0;
Deque pode ser iterado para frente e para trás usando o deque :: cbegin e deque :: cend, e nos dois sentidos usando o deque :: crbegin e deque :: crend.
Inicialmente, criamos um iterador que pode apontar para um deque de números inteiros chamados "var". Então, apontamos para os seguintes elementos usando o iterador "var_inter". O iterador que o método BEGN () retorna aponta para o primeiro elemento. O "Begin () + 1" gera um iterador usando o índice 1 do elemento como ponto de partida. Como você pode ver, usamos o VAR.end () - 1 em vez do Var.fim().
Isso ocorre porque o iterador para o método end () links para um iterador que passa pelo último elemento. Para obter o último elemento, deduzimos 1. Usamos o operador de indireção * para obter o valor de um elemento depois de usar o inter_var para apontar para ele.
Operações de Deque
As operações fundamentais que podem ser realizadas em Deque são as seguintes:
- Insertfront é geralmente usado para adicionar ou inserir algo na frente do deque.
- Inserir ou adicione algo no final do deque usando o insertlast comando.
- DeleteFront é usado para remover o item da frente da fila, excluindo -o.
- Remova o final Neste, o item deve ser excluído ou movido para o final da fila.
- Obtenha o primeiro item no deque usando o getfront método.
- Obtenha o último item na fila usando o Obtenha o último método.
- está vazia é usado para verificar se o deque é nulo.
- está cheio é usado para determinar se o deque está cheio.
Conclusão
Deque é a melhor opção porque é mais rápido e ajuda o código a ser executado mais rapidamente. O deque opera melhor para sequências de log. Este artigo é baseado na implementação da DEQUE e em seus principais métodos, que nos ajudam a modificar o deque de acordo com nossas necessidades. Nosso objetivo é explicar o deque e seus métodos, bem como exemplos de como usar o deque e quando usá -lo. A ferramenta que usamos para implementar o código é o compilador C ++. Fizemos um esforço sincero para tornar este tutorial o mais simples e compreensível para você possível.