double ended queue c with examples
Um tutorial aprofundado sobre Deque ou fila dupla em C ++. O tutorial explica o que é Deque, operações básicas, implementação e aplicativos C ++ e Java:
Fila com terminação dupla ou simplesmente chamada de “Deque” é uma versão generalizada de Queue.
A diferença entre Queue e Deque é que ele não segue a abordagem FIFO (First In, First Out). A segunda característica do Deque é que podemos inserir e remover elementos tanto das extremidades dianteiras quanto traseiras.
=> Leia a série de treinamento Easy C ++
O que você aprenderá:
- Classificação de fila dupla
- Operações básicas de toque
- e ilustração
- e implementação
- Formulários
- Conclusão
- Leitura recomendada
Classificação de fila dupla
Deque pode ser classificado da seguinte forma:
Entrada de toque restrito; Na restrição de entrada, a exclusão pode ser feita de ambas as extremidades, mas a inserção pode ser feita apenas na extremidade posterior da fila.
Deque de saída restrita: Na fila de saída restrita, a inserção pode ser feita de ambas as extremidades, mas a exclusão é feita apenas em uma extremidade, ou seja, a extremidade dianteira da fila.
Também podemos implementar pilhas e filas usando deque.
Operações básicas de toque
A seguir estão as operações básicas que podem ser executadas no deque.
- inserir frente: Insira ou adicione um item na frente do deque.
- insertLast: Insira ou adicione um item na parte traseira do deque.
- deleteFront: Exclua ou remova o item da frente da fila.
- deletar último: Exclua ou remova o item da parte traseira da fila.
- getFront: Recupera o item da frente no deque.
- Obtenha o último: Recupera o último item da fila.
- está vazia: Verifica se o deque está vazio.
- está cheio: Verifica se o deque está cheio.
e ilustração
Um deque vazio é representado da seguinte forma:
c ++ gera um número aleatório entre 1 e 10
Em seguida, inserimos o elemento 1 na frente.
Agora, inserimos o elemento 3 na parte traseira.
Em seguida, adicionamos o elemento 5 à frente e quando incrementamos os pontos da frente para 4.
quanto custa a torrada
Em seguida, inserimos os elementos 7 na parte traseira e 9 na frente. O deque terá a aparência mostrada abaixo.
A seguir, vamos remover um elemento da frente.
Assim, vemos que quando os elementos são inseridos na frente, a posição frontal é decrementada enquanto é incrementada quando um elemento é removido. Para a extremidade traseira, a posição é incrementada para inserção e diminuída para remoção .
e implementação
Implementação 100 ++ touch
Podemos implementar um deque em C ++ usando arrays, bem como uma lista vinculada. Além disso, a Standard Template Library (STL) possui uma classe “deque” que implementa todas as funções para esta estrutura de dados.
A implementação da matriz do deque é fornecida abaixo. Como é uma fila de duas pontas, usamos matrizes circulares para implementação.
#include using namespace std; #define MAX_size 10 // Maximum size of array or Dequeue // Deque class class Deque { int array(MAX_size); int front; int rear; int size; public : Deque(int size) { front = -1; rear = 0; this->size = size; } // Operations on Deque: void insertfront(int key); void insertrear(int key); void deletefront(); void deleterear(); int getFront(); int getRear(); // Check if Deque is full bool isFull()front == rear+1); // Check if Deque is empty bool isEmpty(){ return (front == -1); } }; // Insert an element at front of the deque void Deque::insertfront(int key) { if (isFull()) { cout << 'Overflow!!
' << endl; return; } // If queue is initially empty,set front=rear=0; start of deque if (front == -1) { front = 0; rear = 0; } else if (front == 0) // front is first position of queue front = size - 1 ; else // decrement front 1 position front = front-1; array(front) = key ; // insert current element into Deque } // insert element at the rear end of deque void Deque ::insertrear(int key) { if (isFull()) { cout << ' Overflow!!
' << endl; return; } // If queue is initially empty,set front=rear=0; start of deque if (front == -1) { front = 0; rear = 0; } else if (rear == size-1) // rear is at last position of queue rear = 0; else // increment rear by 1 position rear = rear+1; array(rear) = key ; // insert current element into Deque } // Delete element at front of Deque void Deque ::deletefront() { if (isEmpty()) { cout << 'Queue Underflow!!
' << endl; return ; } // Deque has only one element if (front == rear) { front = -1; rear = -1; } else // back to initial position if (front == size -1) front = 0; else // remove current front value from Deque;increment front by 1 front = front+1; } // Delete element at rear end of Deque void Deque::deleterear() { if (isEmpty()) { cout << ' Underflow!!
' << endl ; return ; } // Deque has only one element if (front == rear) { front = -1; rear = -1; } else if (rear == 0) rear = size-1; else rear = rear-1; } // retrieve front element of Deque int Deque::getFront() { if (isEmpty()) { cout << ' Underflow!!
' << endl; return -1 ; } return array(front); } // retrieve rear element of Deque int Deque::getRear() { if(isEmpty() || rear < 0) { cout << ' Underflow!!
' << endl; return -1 ; } return array(rear); } //main program int main() { Deque dq(5); cout << 'Insert element 1 at rear end
'; dq.insertrear(1); cout << 'insert element 3 at rear end
'; dq.insertrear(3); cout << 'rear element of deque ' << ' ' << dq.getRear() << endl; dq.deleterear(); cout << 'After deleterear, rear = ' << dq.getRear() << endl; cout << 'inserting element 5 at front end
'; dq.insertfront(5); cout << 'front element of deque ' << ' ' << dq.getFront() << endl; dq.deletefront(); cout << 'After deletefront, front = ' << dq.getFront() << endl; return 0; } Resultado:
Insira o elemento 1 na extremidade traseira
insira o elemento 3 na extremidade traseira
elemento traseiro do deque 3
Após deleterear, traseiro = 1
inserir o elemento 5 na extremidade frontal
elemento frontal do deque 5
Depois de deletefront, front = 1
Recontagem de implementação Java
A interface deque em Java, “java.util.Deque” é derivada da interface “java.util.Queue”. Deque pode ser usado como uma fila (Primeiro a Entrar, Primeiro a Sair) ou uma pilha (Último a Entrar, Primeiro a Sair). Essas implementações funcionam mais rápido do que a lista vinculada.
A seguir está a hierarquia da interface Deque em Java.
Precisamos lembrar alguns pontos sobre a interface Deque em Java:
- A implementação não é segura para thread, pois não há sincronização externa.
- Deque não oferece suporte à simultaneidade de vários threads.
- Implementado de Deque usando matrizes não permite o uso de elementos NULL.
- Os arrays podem crescer de acordo com os requisitos, com capacidade livre de restrições e suporte a array redimensionável sendo os dois recursos mais importantes.
A seguir estão os vários métodos suportados pela interface Deque:
mysql vs oracle vs sql server
| Não. | Método | Descrição |
|---|---|---|
| 7 | iterador () | Retorna um iterador para o deque. |
| 1 | adicionar (elemento) | Adiciona um elemento à cauda. |
| dois | addFirst (elemento) | Adiciona um elemento à cabeça / frente. |
| 3 | addLast (elemento) | Adiciona um elemento à cauda / traseira. |
| 4 | oferta (elemento) | Adiciona um elemento à cauda; retorna um valor booleano para indicar se a inserção foi bem-sucedida. |
| 5 | offerFirst (elemento) | Adiciona um elemento à cabeça; retorna um valor booleano para indicar se a inserção foi bem-sucedida. |
| 6 | offerLast (elemento) | Adiciona um elemento à cauda; retorna um valor booleano para indicar se a inserção foi bem-sucedida. |
| 8 | descendingIterator () | Retorna um iterador que possui a ordem inversa para este deque. |
| 9 | empurrar (elemento) | Adiciona um elemento à cabeça do deque. |
| 10 | pop (elemento) | Remove um elemento da cabeça do deque e o retorna. |
| onze | removeFirst () | Remove o elemento na cabeça do deque. |
| 12 | removeLast () | Remove o elemento na cauda do deque. |
| 13 | enquete() | Recupera e remove o primeiro elemento do deque (representado pela cabeça do deque); retorna NULL se o deque estiver vazio. |
| 14 | pollFirst () | Recupera e remove o primeiro elemento deste deque; retorna nulo se este deque estiver vazio. |
| quinze | pollLast () | Recupera e remove o último elemento deste deque; retorna nulo se este deque estiver vazio. |
| 16 | olhadinha() | Recupera a cabeça (primeiro elemento do deque) da fila representada por este deque; retorna nulo se este deque estiver vazio. Nota: esta operação não remove o elemento. |
| 17 | peekFirst () | Recupera o primeiro elemento deste deque; retorna nulo se este deque estiver vazio. Nota: esta operação não remove o elemento. |
| 18 | peekLast () | Recupera o último elemento deste deque ou retorna nulo se este deque estiver vazio. Nota: esta operação não remove o elemento. |
A implementação Java a seguir demonstra as várias operações discutidas acima.
import java.util.*; class Main { public static void main(String() args) { Deque deque = new LinkedList (); // We can add elements to the queue in various ways deque.add(1); // add to tail deque.addFirst(3); deque.addLast(5); deque.push(7); //add to head deque.offer(9); deque.offerFirst(11); deque.offerLast(13); System.out.println('The deque : ' + deque + '
'); // Iterate through the queue elements. System.out.println('Standard Iterator'); Iterator iterator = deque.iterator(); while (iterator.hasNext()) System.out.print(' ' + iterator.next()); // Reverse order iterator Iterator reverse = deque.descendingIterator(); System.out.println('
Reverse Iterator'); while (reverse.hasNext()) System.out.print(' ' + reverse.next()); // Peek returns the head, without deleting // it from the deque System.out.println('
Peek ' + deque.peek()); System.out.println('After peek: ' + deque); // Pop returns the head, and removes it from // the deque System.out.println('
Pop ' + deque.pop()); System.out.println('After pop: ' + deque); // We can check if a specific element exists // in the deque System.out.println('
Contains element 3?: ' + deque.contains(3)); // We can remove the first / last element. deque.removeFirst(); deque.removeLast(); System.out.println('Deque after removing ' + 'first and last elements: ' + deque); } } Resultado:
E o (11, 7, 3, 1, 5, 9, 13)
Iterador Padrão
11 7 3 1 5 9 13
Iterador reverso
13 9 5 1 3 7 11
Peek 11
Depois da espiada: (11, 7, 3, 1, 5, 9, 13)
Pop 11
Depois do pop: (7, 3, 1, 5, 9, 13)
Contém o elemento 3 ?: verdadeiro
Deque após remover o primeiro e o último elemento: (3, 1, 5, 9)
No programa acima, usamos a interface Deque de Java e definimos um deque de elementos inteiros. Em seguida, realizamos várias operações neste deque e na saída os resultados dessas operações são exibidos.
Formulários
O Deque pode ser usado em alguns dos aplicativos a seguir.
# 1) Algoritmo de programação: Um algoritmo de agendamento, “algoritmo de agendamento A-steal” implementa agendamento de tarefas para vários processadores no sistema multiprocessador. Essa implementação usa deque e o processador obtém o primeiro elemento do deque para execução.
# 2) Desfazer lista de atividades: Em aplicativos de software, temos muitas ações. Um é “desfazer”. Quando executamos a ação de desfazer várias vezes, todas essas ações são armazenadas em uma lista. Esta lista é mantida como um deque para que possamos adicionar / remover prontamente entradas de qualquer extremidade.
# 3) Remova as entradas após algum tempo: Os aplicativos atualizam entradas em sua lista, como aplicativos que listam as entradas de estoque, etc. Esses aplicativos removem as entradas depois de algum tempo e também inserem novas entradas. Isso é feito usando um deque.
Conclusão
Deque é uma fila de duas extremidades que nos permite adicionar / remover elementos de ambas as extremidades, ou seja, frontal e traseira da fila. Deque pode ser implementado usando matrizes ou listas vinculadas. No entanto, também temos uma classe Standard Template Library (STL) que implementa as várias operações do Deque.
Em Java, temos uma interface Deque que é herdada da interface de fila para implementar Deque. Além das operações básicas padrão do Deque, esta interface suporta várias outras operações que podem ser realizadas no Deque.
Deque é geralmente usado para aplicações que requerem adição / remoção de elementos de ambas as extremidades. Ele também é usado principalmente na programação de processadores em sistemas multiprocessados.
=> Confira a série completa de treinamento C ++
Leitura recomendada
- Fila prioritária em STL
- O que é teste de comparação (aprenda com exemplos)
- Tutorial Python DateTime com exemplos
- Classificação Shell em C ++ com exemplos
- Cortar comando no Unix com exemplos
- Sintaxe de comando Unix Cat, opções com exemplos
- Uso do cursor no MongoDB com exemplos
- Comando Ls no Unix com exemplos