Estruturas de Dados: Filas, Pilhas e Deques - Conceitos e Exercícios

INSTITUTO FEDERAL Rio Grande do Sul Canoas ESTRUTURAS DE DADOS Filas Pilhas e Deques Prof Roger Silva 20222 ESTRUTURAS DE DADOS Filas Pilhas e Deques 1 Fila 2 Pilha 3 Deque 4 Exercícios 1 INSTITUTO FEDERAL Rio Grande do Sul Canoas 1 Fila FILA Conceito Filas são estruturas de armazenamento lineares que tem um comportamento semelhante ao de uma fila de verdade Essas estruturas suportam pelo menos duas operações A operação enqueue enfileira um elemento ou seja adiciona esse elemento ao fim da fila A operação dequeue desenfileira um elemento ou seja remove o elemento que está no início da fila e retorna esse elemento para quem chamou Como o primeiro elemento a entrar será também o primeiro a sair uma fila também é chamada de uma estrutura do tipo FIFO first in first out 2 FILA Conceito Início do programa Fila vazia funcionamento da fila o comportamento de uma fila é regido por suas duas operações os elementos só podem entrar no fim e só podem sair do início da fila 3 FILA Conceito A enqueueA Fila com 1 elemento Fim Início funcionamento da fila o comportamento de uma fila é regido por suas duas operações os elementos só podem entrar no fim e só podem sair do início da fila 3 FILA Conceito A B enqueueB Fila com 2 elementos Fim Início funcionamento da fila o comportamento de uma fila é regido por suas duas operações os elementos só podem entrar no fim e só podem sair do início da fila 3 FILA Conceito A B C enqueueC Fila com 3 elementos Fim Início funcionamento da fila o comportamento de uma fila é regido por suas duas operações os elementos só podem entrar no fim e só podem sair do início da fila 3 FILA Conceito B C A dequeue Fila com 2 elementos Fim Início funcionamento da fila o comportamento de uma fila é regido por suas duas operações os elementos só podem entrar no fim e só podem sair do início da fila 3 FILA Conceito B C D enqueueD Fila com 3 elementos Fim Início funcionamento da fila o comportamento de uma fila é regido por suas duas operações os elementos só podem entrar no fim e só podem sair do início da fila 3 FILA Conceito B C D E enqueueE Fila com 4 elementos Fim Início funcionamento da fila o comportamento de uma fila é regido por suas duas operações os elementos só podem entrar no fim e só podem sair do início da fila 3 FILA Conceito B C D E F enqueueF Fila cheia Fim Início funcionamento da fila o comportamento de uma fila é regido por suas duas operações os elementos só podem entrar no fim e só podem sair do início da fila 3 FILA Conceito C D E F B dequeue Fila com 4 elementos Fim Início funcionamento da fila o comportamento de uma fila é regido por suas duas operações os elementos só podem entrar no fim e só podem sair do início da fila 3 FILA Conceito D E F C dequeue Fila com 3 elementos Fim Início funcionamento da fila o comportamento de uma fila é regido por suas duas operações os elementos só podem entrar no fim e só podem sair do início da fila 3 FILA Conceito E F D dequeue Fila com 2 elementos Fim Início funcionamento da fila o comportamento de uma fila é regido por suas duas operações os elementos só podem entrar no fim e só podem sair do início da fila 3 FILA Conceito F E dequeue Fila com 1 elemento Fim Início funcionamento da fila o comportamento de uma fila é regido por suas duas operações os elementos só podem entrar no fim e só podem sair do início da fila 3 FILA Conceito F dequeue Fila vazia funcionamento da fila o comportamento de uma fila é regido por suas duas operações os elementos só podem entrar no fim e só podem sair do início da fila 3 FILA Implementação linear Arquivo queueh 1 ifndef QUEUEH 2 define QUEUEH 3 define QMAX 10 4 typedef int Elem 5 typedef struct 6 unsigned int len 7 unsigned int front 8 Elem vetQMAX 9 Queue 10 11 Queue newqueue 12 int enqueueQueue q Elem e 13 int dequeueQueue q Elem e 14 endif Vamos considerar uma estrutura Queue cujo campo len que vai de zero até QMAX representa quantos elementos ela tem armazenados internamente Por enquanto front é sempre zero e cada elemento é do tipo int O arquivo de interface é esse apresentado ao lado Uma possível implementação é apresentada nos próximos slides 4 FILA Implementação linear Arquivo queuec 1 include queueh 2 3 Queue newqueue 4 Queue q 5 qfront 0 6 qlen 0 7 return q 8 A criação da fila é feita pela função newqueue e envolve apenas a inicialização do seu início front e comprimento len O início da fila linear será sempre a posição zero do vetor ou seja por enquanto não é usado para nada Porém mais tarde veremos como esse índice pode ser usado em uma implementação mais rápida da fila 5 FILA Implementação linear Arquivo queuec 10 int enqueueQueue q Elem e 11 if qlen QMAX 12 return 0 13 14 qvetqlen e 15 16 qlen 17 return qlen 18 A operação enqueue tem complexidade constante O1 Isso porque essa operação apenas salva o elemento no final da fila e atualiza o comprimento da mesma Note que obter o comprimento da fila também tem complexidade constante pois basta acessar o campo len 6 FILA Implementação linear Arquivo queuec 20 int dequeueQueue q Elem e 21 int i 22 if qlen 0 return 0 23 24 e qvet 0 25 26 qlen 27 28 for i 0 i qlen i 29 qveti qveti1 30 31 return qlen 1 32 A operação dequeue tem complexidade linear On onde n é o comprimento atual da fila len Isso porque essa operação copia o primeiro elemento da fila para o buffer e atualiza o comprimento e depois move todos os outros elementos para frente Note que poderíamos escolher mover os elementos ao enfileirar e aquela operação é que teria maior complexidade 7 FILA Exemplo de utilização Essa estrutura pode ser usada conforme o código a seguir cria a fila com QMAX posições vazias Queue q newqueue enqueue q 1 enfileira o valor 1 enqueue q 2 enfileira o valor 2 Elem x dequeue q x desenfileira 1 p dentro de x dequeue q x desenfileira 2 p dentro de x 8 FILA Implementação circular A implementação de dequeue pode ser melhorada para ter complexidade constante O1 se for utilizada uma fila circular em vez de uma fila linear O modo de armazenamento é o mesmo dentro de um vetor Quando um elemento é removido do início de uma fila circular em vez de movermos todos os elementos pra frente movemos apenas o índice do início da fila Como anteriormente quando um elemento é adicionado movemos o índice do fim da fila Portanto precisamos guardar os índices do vetor que apontam para o início e para o fim da fila ou seu comprimento Conforme os índices avançam eles podem dar a volta e apontar para o início do vetor que armazena os dados Ou seja é como se o fim e o início do vetor estivessem ligados formando um círculo 9 FILA Implementação circular 0 1 2 3 4 5 Organização Linear Juntar as duas pontas funcionamento da fila em uma fila circular os elementos vão sendo inseridos e removidos fazendo a volta ao redor da fila desse modo não é preciso mover todos os elementos durante uma operação 10 FILA Implementação circular 0 1 2 3 4 5 Mudando a Organização funcionamento da fila em uma fila circular os elementos vão sendo inseridos e removidos fazendo a volta ao redor da fila desse modo não é preciso mover todos os elementos durante uma operação 10 FILA Implementação circular 0 1 2 3 4 5 Organização Circular funcionamento da fila em uma fila circular os elementos vão sendo inseridos e removidos fazendo a volta ao redor da fila desse modo não é preciso mover todos os elementos durante uma operação 10 FILA Implementação circular Início do Programa Fila vazia 2 3 4 5 0 1 funcionamento da fila em uma fila circular os elementos vão sendo inseridos e removidos fazendo a volta ao redor da fila desse modo não é preciso mover todos os elementos durante uma operação 10 FILA Implementação circular A enqueueA Fila com 1 elemento 2 3 4 5 0 1 I F funcionamento da fila em uma fila circular os elementos vão sendo inseridos e removidos fazendo a volta ao redor da fila desse modo não é preciso mover todos os elementos durante uma operação 10 FILA Implementação circular A B enqueueB Fila com 2 elementos 2 3 4 5 0 1 I F funcionamento da fila em uma fila circular os elementos vão sendo inseridos e removidos fazendo a volta ao redor da fila desse modo não é preciso mover todos os elementos durante uma operação 10 FILA Implementação circular A B C enqueueC Fila com 3 elementos 2 3 4 5 0 1 I F funcionamento da fila em uma fila circular os elementos vão sendo inseridos e removidos fazendo a volta ao redor da fila desse modo não é preciso mover todos os elementos durante uma operação 10 FILA Implementação circular A B C D enqueueD Fila com 4 elementos 2 3 4 5 0 1 I F funcionamento da fila em uma fila circular os elementos vão sendo inseridos e removidos fazendo a volta ao redor da fila desse modo não é preciso mover todos os elementos durante uma operação 10 FILA Implementação circular B C D A dequeue Fila com 3 elementos 2 3 4 5 0 1 I F funcionamento da fila em uma fila circular os elementos vão sendo inseridos e removidos fazendo a volta ao redor da fila desse modo não é preciso mover todos os elementos durante uma operação 10 FILA Implementação circular C D B dequeue Fila com 2 elementos 2 3 4 5 0 1 F I funcionamento da fila em uma fila circular os elementos vão sendo inseridos e removidos fazendo a volta ao redor da fila desse modo não é preciso mover todos os elementos durante uma operação 10 FILA Implementação circular C D E enqueueE Fila com 3 elementos 2 3 4 5 0 1 F I funcionamento da fila em uma fila circular os elementos vão sendo inseridos e removidos fazendo a volta ao redor da fila desse modo não é preciso mover todos os elementos durante uma operação 10 FILA Implementação circular C D E F enqueueF Fila com 4 elementos 2 3 4 5 0 1 F I funcionamento da fila em uma fila circular os elementos vão sendo inseridos e removidos fazendo a volta ao redor da fila desse modo não é preciso mover todos os elementos durante uma operação 10 FILA Implementação circular G C D E F enqueueG Fila com 5 elementos 2 3 4 5 0 1 I F funcionamento da fila em uma fila circular os elementos vão sendo inseridos e removidos fazendo a volta ao redor da fila desse modo não é preciso mover todos os elementos durante uma operação 10 FILA Implementação circular G H C D E F enqueueH Fila cheia 2 3 4 5 0 1 I F funcionamento da fila em uma fila circular os elementos vão sendo inseridos e removidos fazendo a volta ao redor da fila desse modo não é preciso mover todos os elementos durante uma operação 10 FILA Implementação circular Arquivo queueCircc 1 include queueh 2 3 Queue newqueue 4 Queue q 5 qfront 0 6 qlen 0 7 return q 8 A operação de criação é idêntica à apresentada anteriormente Note que o arquivo de interface também é o mesmo afinal só o que foi modificado foi a implementação 11 FILA Implementação circular Arquivo queueCircc 10 int enqueueQueue q Elem e 11 if qlen QMAX 12 return 0 13 14 int end qfront qlen 15 end QMAX 16 17 qvetend e 18 19 qlen 20 return qlen 21 A operação enqueue ainda tem complexidade constante O1 pois insere no fim da fila e atualiza o comprimento A diferença é que agora o fim da fila end precisa ser calculado a partir de front len e QMAX para permitir que ele possa dar a volta no vetor 12 FILA Implementação circular Arquivo queueCircc 23 int dequeueQueue q Elem e 24 if qlen 0 return 0 25 26 e qvetqfront 27 28 qlen 29 qfront 30 qfront QMAX 31 return qlen 1 32 A grande melhoria está na operação dequeue que agora também tem complexidade constante O1 Observe que isso só pode ser alcançado com a inclusão do campo front na estrutura Queue Porém essa estrutura ainda tem complexidade de armazenamento constante Note que ao atualizar o campo front também precisamos levar em conta que ele pode dar a volta no vetor 13 INSTITUTO FEDERAL Rio Grande do Sul Canoas 2 Pilha PILHA Conceito Uma pilha é uma estrutura de armazenamento linear que permite a modificação de apenas uma de suas pontas Essas estruturas suportam pelo menos duas operações A operação push empilha um elemento ou seja adiciona esse elemento sobre o topo da pilha A operação pop desempilha um elemento ou seja remove o elemento que está no topo da pilha e retorna esse elemento para quem chamou Como o último elemento empilhado é sempre o primeiro a ser desempilhado uma pilha também é chamada de uma estrutura LIFO last in first out 14 PILHA Conceito Início do programa Pilha vazia funcionamento da pilha o comportamento de uma pilha é regido por suas duas operações os elementos só podem ser empilhados e desempilhados do topo da pilha 15 PILHA Conceito A pushA Pilha com 1 elemento Topo Base funcionamento da pilha o comportamento de uma pilha é regido por suas duas operações os elementos só podem ser empilhados e desempilhados do topo da pilha 15 PILHA Conceito A B pushB Pilha com 2 elementos Topo Base funcionamento da pilha o comportamento de uma pilha é regido por suas duas operações os elementos só podem ser empilhados e desempilhados do topo da pilha 15 PILHA Conceito A B C pushC Pilha com 3 elementos Topo Base funcionamento da pilha o comportamento de uma pilha é regido por suas duas operações os elementos só podem ser empilhados e desempilhados do topo da pilha 15 PILHA Conceito A B C pop Pilha com 2 elementos Topo Base funcionamento da pilha o comportamento de uma pilha é regido por suas duas operações os elementos só podem ser empilhados e desempilhados do topo da pilha 15 PILHA Conceito A B D pushD Pilha com 3 elementos Topo Base funcionamento da pilha o comportamento de uma pilha é regido por suas duas operações os elementos só podem ser empilhados e desempilhados do topo da pilha 15 PILHA Conceito A B D E pushE Pilha com 4 elementos Topo Base funcionamento da pilha o comportamento de uma pilha é regido por suas duas operações os elementos só podem ser empilhados e desempilhados do topo da pilha 15 PILHA Conceito A B D E pushF Pilha cheia F Topo Base funcionamento da pilha o comportamento de uma pilha é regido por suas duas operações os elementos só podem ser empilhados e desempilhados do topo da pilha 15 PILHA Conceito A B D E F pop Pilha com 4 elementos Topo Base funcionamento da pilha o comportamento de uma pilha é regido por suas duas operações os elementos só podem ser empilhados e desempilhados do topo da pilha 15 PILHA Conceito A B D E pop Pilha com 3 elementos Topo Base funcionamento da pilha o comportamento de uma pilha é regido por suas duas operações os elementos só podem ser empilhados e desempilhados do topo da pilha 15 PILHA Conceito A B D pop Pilha com dois elementos Topo Base funcionamento da pilha o comportamento de uma pilha é regido por suas duas operações os elementos só podem ser empilhados e desempilhados do topo da pilha 15 PILHA Conceito A B pop Pilha com 1 elementos Topo Base funcionamento da pilha o comportamento de uma pilha é regido por suas duas operações os elementos só podem ser empilhados e desempilhados do topo da pilha 15 PILHA Conceito A pop Pilha vazia funcionamento da pilha o comportamento de uma pilha é regido por suas duas operações os elementos só podem ser empilhados e desempilhados do topo da pilha 15 PILHA Implementação Arquivo stackh 1 ifndef STACKH 2 define STACKH 3 define SMAX 10 4 typedef int Elem 5 typedef struct 6 unsigned int depth 7 Elem vetSMAX 8 Stack 9 10 Stack newstack 11 int pushStack q Elem e 12 int popStack q Elem e 13 endif Vamos considerar uma estrutura Stack cuja quantidade de elementos é dada por sua profundidade depth que vai de zero até SMAX Observe que a pilha não precisa ser circular pois só pode crescer e encolher em uma das pontas Por isso também a pilha é a estrutura mais simples de implementar dessa aula 16 PILHA Implementação Arquivo stackc 1 include stackh 2 3 Stack newstack 4 Stack s 5 sdepth 0 6 return s 7 Na criação da nossa Stack basta inicializar a sua profundidade com o valor zero pilha vazia 17 PILHA Implementação Arquivo stackc 9 int pushStack s Elem e 10 if sdepth SMAX 11 return 0 12 13 svetsdepth e 14 15 sdepth 16 return sdepth 17 A operação de empilhar push apenas coloca o elemento no topo da pilha e incrementa a profundidade Essa operação é praticamente idêntica à operação de enfileirar um elemento na implementação linear da fila Se quiser compare com o código do slide 6 Portanto essa operação também tem complexidade constante 18 PILHA Implementação Arquivo stackc 19 int popStack s Elem e 20 if sdepth 0 return 0 21 22 sdepth 23 24 e svetsdepth 25 26 return sdepth 1 27 A operação de desempilhar pop apenas decrementa a profundidade e copia o elemento que estava no topo da pilha para o buffer e disponibilizando ele para quem chamou a função Por isso essa operação também tem complexidade constante 19 PILHA Exemplo de utilização Com a nossa Stack podemos manipular dados conforme o código a seguir Stack s newstack push s 2 empilha o valor 2 push s 5 empilha o valor 5 push s 7 empilha o valor 7 Elem x pops x desempilha 7 p dentro de x pops x desempilha 5 p dentro de x pops x desempilha 2 p dentro de x 20 INSTITUTO FEDERAL Rio Grande do Sul Canoas 3 Deque DEQUE Conceito Um deque pronunciado como um deck de cartas é uma fila com duas pontas do inglês doubleended queue Isso quer dizer que os elementos podem entrar e sair em qualquer uma das pontas Ou seja um deque é só uma combinação de uma fila e uma pilha Porém para garantir inserção e remoção com complexidade constante vamos utilizar uma implementação circular Por isso as coisas não são tão simples assim 21 DEQUE Conceito O nosso deque será definido por quatro operações a operação pushleft que insere um elemento na ponta esquerda do deque operação popleft que remove um elemento da ponta esquerda do deque a operação pushright que insere um elemento na ponta direita do deque e a operação popright que remove um elemento da ponta direita do deque 22 DEQUE Conceito Inicio do Programa Deque vazio funcionamento do deque o comportamento de um deque é regido por suas quatro operações os elementos podem ser inseridos e removidos de qualquer uma das pontas Para garantir acesso constante a implementação deve ser circular omitida na imagem 23 DEQUE Conceito A pushrightA Deque com 1 elemento Esquerda Direita funcionamento do deque o comportamento de um deque é regido por suas quatro operações os elementos podem ser inseridos e removidos de qualquer uma das pontas Para garantir acesso constante a implementação deve ser circular omitida na imagem 23 DEQUE Conceito A B pushrightB Deque com 2 elementos Esquerda Direita funcionamento do deque o comportamento de um deque é regido por suas quatro operações os elementos podem ser inseridos e removidos de qualquer uma das pontas Para garantir acesso constante a implementação deve ser circular omitida na imagem 23 DEQUE Conceito A B C pushrightC Deque com 3 elementos Esquerda Direita funcionamento do deque o comportamento de um deque é regido por suas quatro operações os elementos podem ser inseridos e removidos de qualquer uma das pontas Para garantir acesso constante a implementação deve ser circular omitida na imagem 23 DEQUE Conceito B C A popleft Deque com 2 elementos Esquerda Direita funcionamento do deque o comportamento de um deque é regido por suas quatro operações os elementos podem ser inseridos e removidos de qualquer uma das pontas Para garantir acesso constante a implementação deve ser circular omitida na imagem 23 DEQUE Conceito B C popright Deque com 3 elementos Esquerda Direita funcionamento do deque o comportamento de um deque é regido por suas quatro operações os elementos podem ser inseridos e removidos de qualquer uma das pontas Para garantir acesso constante a implementação deve ser circular omitida na imagem 23 DEQUE Conceito D B pushleftD Deque com 2 elementos Esquerda Direita funcionamento do deque o comportamento de um deque é regido por suas quatro operações os elementos podem ser inseridos e removidos de qualquer uma das pontas Para garantir acesso constante a implementação deve ser circular omitida na imagem 23 DEQUE Conceito D B E pushleftE Deque com 3 elementos Esquerda Direita funcionamento do deque o comportamento de um deque é regido por suas quatro operações os elementos podem ser inseridos e removidos de qualquer uma das pontas Para garantir acesso constante a implementação deve ser circular omitida na imagem 23 DEQUE Conceito D B F E pushleftF Deque com 4 elementos Esquerda Direita funcionamento do deque o comportamento de um deque é regido por suas quatro operações os elementos podem ser inseridos e removidos de qualquer uma das pontas Para garantir acesso constante a implementação deve ser circular omitida na imagem 23 DEQUE Conceito D B G F E pushleftG Deque cheio Esquerda Direita funcionamento do deque o comportamento de um deque é regido por suas quatro operações os elementos podem ser inseridos e removidos de qualquer uma das pontas Para garantir acesso constante a implementação deve ser circular omitida na imagem 23 DEQUE Conceito D G F E B popright Deque com 4 elementos Esquerda Direita funcionamento do deque o comportamento de um deque é regido por suas quatro operações os elementos podem ser inseridos e removidos de qualquer uma das pontas Para garantir acesso constante a implementação deve ser circular omitida na imagem 23 DEQUE Conceito D F E G popleft Deque com 3 elementos Direita Esquerda funcionamento do deque o comportamento de um deque é regido por suas quatro operações os elementos podem ser inseridos e removidos de qualquer uma das pontas Para garantir acesso constante a implementação deve ser circular omitida na imagem 23 DEQUE Conceito D E F popleft Deque com 2 elementos Direita Esquerda funcionamento do deque o comportamento de um deque é regido por suas quatro operações os elementos podem ser inseridos e removidos de qualquer uma das pontas Para garantir acesso constante a implementação deve ser circular omitida na imagem 23 DEQUE Conceito E D popright Deque com 1 elemento Direita Esquerda funcionamento do deque o comportamento de um deque é regido por suas quatro operações os elementos podem ser inseridos e removidos de qualquer uma das pontas Para garantir acesso constante a implementação deve ser circular omitida na imagem 23 DEQUE Conceito E popright Deque vazio funcionamento do deque o comportamento de um deque é regido por suas quatro operações os elementos podem ser inseridos e removidos de qualquer uma das pontas Para garantir acesso constante a implementação deve ser circular omitida na imagem 23 DEQUE Implementação Arquivo dequeh 1 ifndef DEQUEH 2 define DEQUEH 3 define DQMAX 10 4 typedef int Elem 5 typedef struct 6 unsigned int width 7 unsigned int left 8 Elem vetDQMAX 9 Deque Agora vamos considerar uma estrutura Deque cuja quantidade de elementos é dada por sua largura width que vai de zero até DQMAX Como um deque pode ser modificado pelas duas pontas optamos pela implementação circular Por isso incluímos um índice left que aponta para a ponta da esquerda do deque A primeira parte do arquivo de interface é mostrada acima 24 DEQUE Implementação Arquivo dequeh 11 Deque newdeque 12 int pushrightDeque dq Elem e 13 int pushleftDeque dq Elem e 14 int popleftDeque dq Elem e 15 int poprightDeque dq Elem e 16 endif O restante do arquivo são as definições das operações de criação inserção e remoção em cada uma das pontas No total agora são cinco operações cujas implementações serão apresentadas nos próximos slides 25 DEQUE Implementação Arquivo dequec 1 include dequeh 2 3 Deque newdeque 4 Deque dq 5 dqleft 0 6 dqwidth 0 7 return dq 8 A operação de criação do Deque apenas inicializa o índice da sua ponta esquerda left e a sua largura width com zero Essa operação tem sempre complexidade constante 26 DEQUE Implementação Arquivo dequec 10 int pushrightDeque dq Elem e 11 if dqwidth DQMAX 12 return 0 13 14 int right dqleft dqwidth 15 right DQMAX 16 17 dqvetright e 18 19 dqwidth 20 return dqwidth 21 A operação de inserção à direita é idêntica à operação de inserção no fim de uma fila circular do slide 12 Se o deque não estiver cheio calcula a posição onde deve ser inserido o elemento insere e incrementa a largura Como já determinamos antes essa operação sempre tem complexidade constante 27 DEQUE Implementação Arquivo dequec 23 int pushleftDeque dq Elem e 24 if dqwidth DQMAX 25 return 0 26 27 dqleft DQMAX 1 28 dqleft DQMAX 29 30 dqvetdqleft e 31 32 dqwidth 33 return dqwidth 34 A operação de inserção à esquerda do deque é semelhante mas ligeiramente diferente da inserção à direita Como devemos manter o índice da posição mais à esquerda do deque atualizamos ele primeiro Em seguida inserimos o elemento nessa posição e incrementamos a largura 28 DEQUE Implementação Arquivo dequec 36 int popleftDeque dq Elem e 37 if dqwidth 0 return 0 38 39 e dqvetdqleft 40 41 dqwidth 42 dqleft 43 dqleft DQMAX 44 return dqwidth 1 45 A operação de remoção da ponta esquerda é idêntica à operação de remoção do início da fila circular do slide 13 Se o deque não estiver vazio copia o elemento mais à esquerda para o buffer e disponibilizando para quem chamou a função da mesma maneira que vimos antes Em seguida decrementa a largura e atualiza o índice da ponta esquerda do deque Novamente essa operação tem complexidade constante 29 DEQUE Implementação Arquivo dequec 47 int poprightDeque dq Elem e 48 if dqwidth 0 return 0 49 50 dqwidth 51 int right dqleft dqwidth 52 right DQMAX 53 54 e dqvetright 55 56 return dqwidth 1 57 Por fim a operação de remover o item da ponta direita também é ligeiramente diferente da remoção da outra ponta Primeiro decrementamos a largura e usamos o novo valor para encontrar o índice da ponta direita em seguida copiamos o elemento dessa ponta para o buffer e Com isso temos todas as operações do deque com complexidade constante 30 DEQUE Exemplo de utilização Com o nosso Deque podemos manipular dados conforme o código a seguir Deque dq newdeque pushleft dq 2 insere o valor 2 à esquerda pushright dq 5 insere o valor 5 à direita pushleft dq 7 insere o valor 7 à esquerda Elem x popleft dq x remove 7 p dentro de x popleft dq x remove 2 p dentro de x popright dq x remove 5 p dentro de x 31 INSTITUTO FEDERAL Rio Grande do Sul Canoas 4 Exercícios EXERCÍCIOS 1 Em qual estrutura de dados a ordem de inserção é inversa à ordem de acesso 2 Qual estrutura de dados seria a melhor escolha para implementar um buffer de comunicação entre uma aplicação que produz dados e uma outra que os consome 3 Dê um exemplo de aplicação onde uma fila de duas pontas seria útil 4 As estruturas de dados apresentadas nessa aula foram implementadas para armazenar inteiros Modifique a estrutura Queue para que ela possa armazenar números decimais com ponto flutuante 5 Se uma aplicação embarcada precisa trabalhar com filas pilhas e deques mas não há espaço no dispositivo para incluir todas essas bibliotecas o que você sugeriria 32 EXERCÍCIOS 6 Adicione uma operação void printQueue q que imprime os 5 elementos mais do topo de uma pilha em ordem inversa na tela Por exemplo uma pilha onde os valores 2 3 5 7 11 13 17 foram inseridos nessa ordem deve ser impressa 2 5 3 7 4 11 5 13 6 17 33 EXERCICIOS calculadora com notagdao reversa polonesa RPN com as 4 Operacoes e a raiz quadrada Cada uma das quatro operagdes remove os dois elementos do topo da pilha opera sobre eles e empilha o resultado novamente Ja a raiz quadrada desempilha apenas um elemento e empilha de volta o resultado Por exemplo para encontrar uma das solucdes de x 12x35 0 calculamos 12 12 4x 1 x 35 es EXERCICIOS calculadora com notagdao reversa polonesa RPN com as 4 Operacoes e a raiz quadrada Cada uma das quatro operagdes remove os dois elementos do topo ae da pilha opera sobre eles e 12 empilha o resultado novamente Ja a raiz quadrada desempilha apenas um elemento e empilha de volta o resultado Por exemplo para encontrar uma das solucdes de x 12x35 0 calculamos 12 122 4 x 35 2 4 ce OLDN EXERCICIOS calculadora com notagdao reversa polonesa RPN com as 4 Operacoes e a raiz quadrada Cada uma das quatro operagdes 0 1D remove os dois elementos do topo ne da pilha opera sobre eles e 12 empilha o resultado novamente Ja a raiz quadrada desempilha apenas um elemento e empilha de volta o resultado Por exemplo para encontrar uma das solucdes de x 12x35 0 calculamos 12 122 4 x 35 2 4 LDN EXERCICIOS calculadora com notagdao reversa polonesa RPN com as 4 Operacoes e a raiz quadrada Cada 0 Lb uma das quatro operagdes L 4D remove os dois elementos do topo ne da pilha opera sobre eles e 12 empilha o resultado novamente Ja a raiz quadrada desempilha apenas um elemento e empilha de volta o resultado Por exemplo para encontrar uma das solucdes de x 12x35 0 calculamos 12 122 4 x 35 2 4 LDN EXERCICIOS calculadora com notagdao reversa polonesa RPN com as 4 operacées e a raiz quadrada Cada to uma das quatro operagdes 5 4D remove os dois elementos do topo ne da pilha opera sobre eles e empilha o resultado novamente Ja a raiz quadrada desempilha apenas um elemento e empilha de volta o resultado Por exemplo para encontrar uma das solucdes de x 12x35 0 calculamos 12 12 4 x 35 2 4 CLDN EXERCÍCIOS 7 TRABALHO Crie um programa calculadora com notação reversa polonesa RPN com as 4 operações e a raiz quadrada Cada uma das quatro operações remove os dois elementos do topo da pilha opera sobre eles e empilha o resultado novamente Terminal 0 12 1 144 4 Já a raiz quadrada desempilha apenas um elemento e empilha de volta o resultado Por exemplo para encontrar uma das soluções de x212x 35 0 calculamos 12 144 4 35 2 34 EXERCÍCIOS 7 TRABALHO Crie um programa calculadora com notação reversa polonesa RPN com as 4 operações e a raiz quadrada Cada uma das quatro operações remove os dois elementos do topo da pilha opera sobre eles e empilha o resultado novamente Terminal 0 12 1 144 2 4 35 Já a raiz quadrada desempilha apenas um elemento e empilha de volta o resultado Por exemplo para encontrar uma das soluções de x212x 35 0 calculamos 12 144 4 35 2 34 EXERCÍCIOS 7 TRABALHO Crie um programa calculadora com notação reversa polonesa RPN com as 4 operações e a raiz quadrada Cada uma das quatro operações remove os dois elementos do topo da pilha opera sobre eles e empilha o resultado novamente Terminal 0 12 1 144 2 4 3 35 Já a raiz quadrada desempilha apenas um elemento e empilha de volta o resultado Por exemplo para encontrar uma das soluções de x212x 35 0 calculamos 12 144 4 35 2 34 EXERCÍCIOS 7 TRABALHO Crie um programa calculadora com notação reversa polonesa RPN com as 4 operações e a raiz quadrada Cada uma das quatro operações remove os dois elementos do topo da pilha opera sobre eles e empilha o resultado novamente Terminal 0 12 1 144 2 140 Já a raiz quadrada desempilha apenas um elemento e empilha de volta o resultado Por exemplo para encontrar uma das soluções de x212x 35 0 calculamos 12 144 140 2 34 EXERCÍCIOS 7 TRABALHO Crie um programa calculadora com notação reversa polonesa RPN com as 4 operações e a raiz quadrada Cada uma das quatro operações remove os dois elementos do topo da pilha opera sobre eles e empilha o resultado novamente Terminal 0 12 1 4 sqrt Já a raiz quadrada desempilha apenas um elemento e empilha de volta o resultado Por exemplo para encontrar uma das soluções de x212x 35 0 calculamos 12 4 2 34 EXERCÍCIOS 7 TRABALHO Crie um programa calculadora com notação reversa polonesa RPN com as 4 operações e a raiz quadrada Cada uma das quatro operações remove os dois elementos do topo da pilha opera sobre eles e empilha o resultado novamente Terminal 0 12 1 2 Já a raiz quadrada desempilha apenas um elemento e empilha de volta o resultado Por exemplo para encontrar uma das soluções de x212x 35 0 calculamos 12 2 2 34 EXERCÍCIOS 7 TRABALHO Crie um programa calculadora com notação reversa polonesa RPN com as 4 operações e a raiz quadrada Cada uma das quatro operações remove os dois elementos do topo da pilha opera sobre eles e empilha o resultado novamente Terminal 0 14 2 Já a raiz quadrada desempilha apenas um elemento e empilha de volta o resultado Por exemplo para encontrar uma das soluções de x212x 35 0 calculamos 14 2 34 EXERCÍCIOS 7 TRABALHO Crie um programa calculadora com notação reversa polonesa RPN com as 4 operações e a raiz quadrada Cada uma das quatro operações remove os dois elementos do topo da pilha opera sobre eles e empilha o resultado novamente Terminal 0 14 1 2 Já a raiz quadrada desempilha apenas um elemento e empilha de volta o resultado Por exemplo para encontrar uma das soluções de x212x 35 0 calculamos 14 2 34 EXERCÍCIOS 7 TRABALHO Crie um programa calculadora com notação reversa polonesa RPN com as 4 operações e a raiz quadrada Cada uma das quatro operações remove os dois elementos do topo da pilha opera sobre eles e empilha o resultado novamente Terminal 0 7 Já a raiz quadrada desempilha apenas um elemento e empilha de volta o resultado Por exemplo para encontrar uma das soluções de x212x 35 0 calculamos 7 34