Neste artigo, discutiremos a fila dupla ou deque. Devemos primeiro ver uma breve descrição da fila.
O que é uma fila?
Uma fila é uma estrutura de dados na qual o que vier primeiro sairá primeiro e segue a política FIFO (First-In-First-Out). A inserção na fila é feita a partir de uma extremidade conhecida como extremidade traseira ou o cauda, enquanto a exclusão é feita de outra extremidade conhecida como front-end ou o cabeça da fila.
Madhuri disse
O exemplo real de fila é a fila de ingressos fora de uma sala de cinema, onde a pessoa que entra primeiro na fila recebe o ingresso primeiro, e a pessoa que entra por último na fila recebe o ingresso por último.
O que é um Deque (ou fila dupla)
O deque significa Fila Dupla. Deque é uma estrutura de dados linear onde as operações de inserção e exclusão são realizadas em ambas as extremidades. Podemos dizer que deque é uma versão generalizada da fila.
Embora a inserção e exclusão em um deque possam ser realizadas em ambas as extremidades, ela não segue a regra FIFO. A representação de um deque é dada da seguinte forma -
Tipos de deque
Existem dois tipos de deque -
- Fila restrita de entrada
- Fila restrita de saída
Fila restrita de entrada
Na fila de entrada restrita, a operação de inserção pode ser realizada em apenas uma extremidade, enquanto a exclusão pode ser realizada em ambas as extremidades.
Fila restrita de saída
Na fila restrita de saída, a operação de exclusão pode ser realizada em apenas uma extremidade, enquanto a inserção pode ser realizada em ambas as extremidades.
Operações realizadas no deque
Existem as seguintes operações que podem ser aplicadas em um deque -
- Inserção na frente
- Inserção na parte traseira
- Exclusão na frente
- Exclusão na parte traseira
Também podemos realizar operações de espiada no deque junto com as operações listadas acima. Através da operação peek, podemos obter os elementos frontal e traseiro do deque. Portanto, além das operações acima, as seguintes operações também são suportadas no deque -
lista vinculada
- Obtenha o item da frente do deque
- Pegue o item traseiro do deque
- Verifique se o deque está cheio ou não
- Verifica se o deque está vazio ou não
Agora, vamos entender a operação realizada no deque usando um exemplo.
Inserção na extremidade frontal
Nesta operação, o elemento é inserido no front end da fila. Antes de implementar a operação, primeiro temos que verificar se a fila está cheia ou não. Se a fila não estiver cheia, o elemento poderá ser inserido no front-end usando as condições abaixo -
pés versus pés
- Se a fila estiver vazia, traseira e frontal serão inicializadas com 0. Agora, ambas apontarão para o primeiro elemento.
- Caso contrário, verifique a posição da frente se a frente for menor que 1 (frente<1), then reinitialize it by front = n - 1 , ou seja, o último índice do array.
Inserção na extremidade traseira
Nesta operação, o elemento é inserido no final da fila. Antes de implementar a operação, primeiro temos que verificar novamente se a fila está cheia ou não. Se a fila não estiver cheia, o elemento poderá ser inserido pela parte traseira usando as condições abaixo -
- Se a fila estiver vazia, traseira e frontal serão inicializadas com 0. Agora, ambas apontarão para o primeiro elemento.
- Caso contrário, aumente a parte traseira em 1. Se a parte traseira estiver no último índice (ou tamanho - 1), então em vez de aumentá-la em 1, temos que torná-la igual a 0.
Exclusão no front-end
Nesta operação, o elemento é excluído do front end da fila. Antes de implementar a operação, primeiro precisamos verificar se a fila está vazia ou não.
Se a fila estiver vazia, ou seja, front = -1, é a condição de underflow e não podemos realizar a exclusão. Se a fila não estiver cheia, o elemento poderá ser inserido no front-end usando as condições abaixo -
Se o deque tiver apenas um elemento, defina rear = -1 e front = -1.
Caso contrário, se a frente estiver no final (isso significa frente = tamanho - 1), defina frente = 0.
trabalho de computador
Caso contrário, aumente a frente em 1 (ou seja, frente = frente + 1).
Exclusão na extremidade traseira
Nesta operação, o elemento é excluído do final da fila. Antes de implementar a operação, primeiro precisamos verificar se a fila está vazia ou não.
Se a fila estiver vazia, ou seja, front = -1, é a condição de underflow e não podemos realizar a exclusão.
Se o deque tiver apenas um elemento, defina rear = -1 e front = -1.
Se traseira = 0 (a traseira está na frente), então defina traseira = n - 1.
Caso contrário, diminua a parte traseira em 1 (ou traseira = traseira -1).
Verifique vazio
Esta operação é realizada para verificar se o deque está vazio ou não. Se front = -1, significa que o deque está vazio.
Verifique completo
Esta operação é realizada para verificar se o deque está cheio ou não. Se frente = traseira + 1, ou frente = 0 e traseira = n - 1 significa que o deque está cheio.
A complexidade de tempo de todas as operações do deque acima é O(1), ou seja, constante.
Aplicações de deque
- Deque pode ser usado tanto como pilha quanto como fila, pois suporta ambas as operações.
- Deque pode ser usado como um verificador de palíndromo, o que significa que se lermos a string em ambas as extremidades, a string será a mesma.
Implementação de deque
Agora, vamos ver a implementação do deque na linguagem de programação C.
rudyard kipling se explicação
#include #define size 5 int deque[size]; int f = -1, r = -1; // insert_front function will insert the value from the front void insert_front(int x) { if((f==0 && r==size-1) || (f==r+1)) { printf('Overflow'); } else if((f==-1) && (r==-1)) { f=r=0; deque[f]=x; } else if(f==0) { f=size-1; deque[f]=x; } else { f=f-1; deque[f]=x; } } // insert_rear function will insert the value from the rear void insert_rear(int x) { if((f==0 && r==size-1) || (f==r+1)) { printf('Overflow'); } else if((f==-1) && (r==-1)) { r=0; deque[r]=x; } else if(r==size-1) { r=0; deque[r]=x; } else { r++; deque[r]=x; } } // display function prints all the value of deque. void display() { int i=f; printf('
Elements in a deque are: '); while(i!=r) { printf('%d ',deque[i]); i=(i+1)%size; } printf('%d',deque[r]); } // getfront function retrieves the first value of the deque. void getfront() { if((f==-1) && (r==-1)) { printf('Deque is empty'); } else { printf('
The value of the element at front is: %d', deque[f]); } } // getrear function retrieves the last value of the deque. void getrear() { if((f==-1) && (r==-1)) { printf('Deque is empty'); } else { printf('
The value of the element at rear is %d', deque[r]); } } // delete_front() function deletes the element from the front void delete_front() { if((f==-1) && (r==-1)) { printf('Deque is empty'); } else if(f==r) { printf('
The deleted element is %d', deque[f]); f=-1; r=-1; } else if(f==(size-1)) { printf('
The deleted element is %d', deque[f]); f=0; } else { printf('
The deleted element is %d', deque[f]); f=f+1; } } // delete_rear() function deletes the element from the rear void delete_rear() { if((f==-1) && (r==-1)) { printf('Deque is empty'); } else if(f==r) { printf('
The deleted element is %d', deque[r]); f=-1; r=-1; } else if(r==0) { printf('
The deleted element is %d', deque[r]); r=size-1; } else { printf('
The deleted element is %d', deque[r]); r=r-1; } } int main() { insert_front(20); insert_front(10); insert_rear(30); insert_rear(50); insert_rear(80); display(); // Calling the display function to retrieve the values of deque getfront(); // Retrieve the value at front-end getrear(); // Retrieve the value at rear-end delete_front(); delete_rear(); display(); // calling display function to retrieve values after deletion return 0; } Saída:
Então, isso é tudo sobre o artigo. Espero que o artigo seja útil e informativo para você.