Estruturas Lineares - Stacks (PDF)

Stacks Algoritmos e Estrutura de Dados 19  Stacks À semelhança das coleções da JCF, vamos garantir que também o tipo de dados abstrato (ADT) Stack (pilha), e todas as outras coleções que iremos definir, colecionam objetos arbitrários. Numa Stack, a inserção e remoç...

Stacks Algoritmos e Estrutura de Dados 19  Stacks À semelhança das coleções da JCF, vamos garantir que também o tipo de dados abstrato (ADT) Stack (pilha), e todas as outras coleções que iremos definir, colecionam objetos arbitrários. Numa Stack, a inserção e remoção de elementos seguem o esquema conhecido por LIFO (last-in first-out) ou, equivalentemente, por FILO (first-in last-out). Pense, por exemplo, numa pilha de livros: o último que foi colocado será o primeiro a ser retirado. Operações específicas de uma stack: push(objeto): insere um objeto; objeto pop(): remove e devolve o último objeto inserido; objeto top(): devolve o último objeto inserido; Outras operações auxiliares: int size(): devolve a quantidade de objetos colecionados; boolean isEmpty(): indica se não existem objetos colecionados. Implementação de estruturas de dados lineares Algoritmos e Estrutura de Dados 20  Interface Java para as stacks A ADT Stack pode ser por nós public interface Stack { criada em Java através da int size(); definição duma interface genérica. boolean isEmpty(); Nela é assumido que os E top(); métodos pop() e top() void push(E element); devolvem null quando a stack E pop(); está vazia algo diferente do que acontece } na classe do Java java.util.Stack. Implementação de estruturas de dados lineares Algoritmos e Estrutura de Dados 21  Exemplo de operações sobre uma stack Implementação de estruturas de dados lineares Algoritmos e Estrutura de Dados 22  Possíveis aplicações duma Stack Histórico das páginas visitadas por um browser; Retrocesso nas operações efetuadas (Undo) numa qualquer aplicação que disponha dessa funcionalidade – editor de texto, por exemplo; Invocação de métodos pela máquina virtual Java (JVM); Como estrutura de dados auxiliar de determinados algoritmos; Etc. Implementação de estruturas de dados lineares Algoritmos e Estrutura de Dados 23  A classe do Java java.util.Stack Apenas por razões históricas, o Java continua a incluir a classe java.util.Stack, que implementa o comportamento LIFO de uma pilha. A sua interface tornou-se inconsistente com outras estruturas de dados mais atuais da framework de coleções do Java (JCF), por essa razão, é recomendável que, em vez dessa classe, se use a estrutura de dados mais geral Deque (por exemplo, como sabe, a LinkedList da JCF é uma coleção concreta que implementa a Deque), dado que também ela permite assegurar uma funcionalidade do tipo LIFO, como vimos já anteriormente. Segue-se uma tabela comparativa das interfaces da nossa stack e da classe da JCF java.util.Stack. Para além da diferença do nome de dois métodos, os métodos peek e pop comportam-se de forma diferente sempre que a stack esteja vazia, como se deve lembrar e como perceberemos já a seguir. Implementação de estruturas de dados lineares Algoritmos e Estrutura de Dados 24  Exceções vs. Retorno de null A tentativa de execução de uma operação sobre uma stack pode por vezes resultar em erro; É o que acontecerá com as operações pop() e top()/peek() da stack quando a mesma se encontre vazia. O Java, como vimos, põe ao nosso dispor um meio que nos permite lidar com os erros – as exceções Uma exceção é acionada por uma operação que não pode ser executada corretamente. A classe do Java java.util.Stack usa o mecanismo de exceções para lidar com os erros provenientes das operações pop() e peek() – algo semelhante acontecia, como deve estar recordado, com alguns dos métodos das Queues e Deques da JCF. Na nossa ADT Stack optámos por permitir a execução das operações pop() e top() mesmo com a stack vazia apenas sinalizando esse facto pela devolução do valor null. Implementação de estruturas de dados lineares Algoritmos e Estrutura de Dados 25  Stack estática A forma mais simples de implementar uma Stack é baseando-a num array. Basta que: adicionemos os elementos pelo lado direito do array; retiremos os elementos sempre também pela direita; e mantenhamos o índice t com a posição do elemento que se encontre no topo da stack (o mais à direita). Porém o array pode a dado momento ficar cheio esta representa a principal limitação deste tipo de stack; o tamanho da stack tem que ser definido à priori; e não pode depois ser alterado; Implementação de estruturas de dados lineares Algoritmos e Estrutura de Dados 26 Stack estática – possível implementação Implementação de estruturas de dados lineares Algoritmos e Estrutura de Dados 27  Stack Dinâmica Embora a implementação da stack num array seja simples e se traduza numa solução eficiente, sofre do grave inconveniente de ter capacidade fixa. Felizmente a interface Stack pode também ser implementada usando, por exemplo, uma lista ligada simples (SLL) no lugar do array com esta nova abordagem conseguimos resolver por completo a limitação do array; a memória ocupada pela stack será sempre a necessária para acomodar todos os elementos colecionados a cada momento – solução dinâmica. Numa Stack Dinâmica, a política de inserção e remoção continua, como é obvio, a estar condicionada aos métodos push() e pop(), e o elemento que poderá ser consultado a cada momento será o do topo, através do método top(). Na implementação de uma Stack sobre uma SLL podemos assumir como topo quer o inicio quer o fim da Lista Porém, por facilidade de implementação, é normal considerarmos para topo o início da lista; Assim, o acesso à Stack, faz-se inserindo e removendo os elementos sempre pelo início da lista. Implementação de estruturas de dados lineares Algoritmos e Estrutura de Dados 28  Stack Dinâmica – LinkedStack Para criarmos uma stack suportada por uma SLL, bastar-nos-á mapear os métodos da nossa classe SinglyLinkedList para os da interface Stack, de forma a ficarmos com uma nova classe com as funcionalidades da SinglyLinkedList mas com a API da stack. Designemos essa nova classe por LinkedStack, a qual terá como atributo privado uma SinglyLinkedList; e usará, na definição dos seus métodos, as correspondências mostradas na tabela. Implementação de estruturas de dados lineares Algoritmos e Estrutura de Dados 29  Exemplo de aplicação de uma stack Atendendo ao seu funcionamento LIFO, uma stack pode ser usada para inverter uma qualquer sequência de elementos, tal como se ilustra no exemplo que se segue, onde se inverte um array de inteiros. Implementação de estruturas de dados lineares Algoritmos e Estrutura de Dados 30 Queue Algoritmos e Estrutura de Dados 31  Queues A ADT Queue (fila), como todos as outras coleções, coleciona objetos arbitrários. A inserção e remoção de elementos seguem o esquema conhecido por FIFO (first-in first-out). Trata-te de uma estrutura de dados, por norma linear, que permite inserir elementos por um dos extremos da coleção e retirá-los pelo outro, Assegurando dessa forma o comportamento FIFO; O primeiro a ser inserido (o que se encontra à cabeça da queue) é o primeiro a ser removido; Implementa o comportamento típico de uma fila de espera. Principais operações de uma queue: enqueue(objeto): insere um objeto no fim da queue; objeto dequeue(): remove e devolve o objeto da frente da queue; objeto first(): devolve o objeto da frente, sem o remover; Outras operações auxiliares: int size(): devolve a quantidade de objetos colecionados; boolean isEmpty(): indica se não existem objetos colecionados. Implementação de estruturas de dados lineares Algoritmos e Estrutura de Dados 32  Interface Java para as queues A ADT Queue pode ser por nós public interface Queue { criada em Java através da int size(); definição duma interface genérica. boolean isEmpty(); E first(); Nela é assumido que os métodos first() e dequeue() void enqueue(E element); devolvem null quando a E dequeue(); coleção está vazia } Implementação de estruturas de dados lineares Algoritmos e Estrutura de Dados 33  Exemplo de operações sobre uma queue Implementação de estruturas de dados lineares Algoritmos e Estrutura de Dados 34  Possíveis aplicações duma Queue Implementação de filas de espera (tão presentes no nosso dia-a-dia); Acesso a recursos partilhados (impressora de rede, por exemplo); Atendimento de pedidos por parte de um servidor Web; Como estrutura de dados auxiliar de determinados algoritmos; Etc. Implementação de estruturas de dados lineares Algoritmos e Estrutura de Dados 35  A interface do Java java.util.Queue O Java disponibiliza-nos a interface java.util.Queue, com as funcionalidades típicas de uma queue. Segue-se uma tabela de correspondências entre os métodos da nossa Queue e os da interface do Java java.util.Queue. Como vimos já anteriormente, para muitas das operações, a interface Java suporta dois estilos no que concerne ao tratamento dos casos excecionais: quando a queue está vazia, os métodos remove( ) e element( ) lançam uma NoSuchElementException, enquanto os métodos correspondentes poll( ) e peek( ) limitam-se a devolver null; para implementações de capacidade limitada, o método add lança uma llegalStateException sempre que se encontre cheia, enquanto o método correspondente offer limita-se a não inserir e a devolver false. Implementação de estruturas de dados lineares Algoritmos e Estrutura de Dados 36  Queue estática As Queues também podem ser implementadas com base em estruturas estáticas como o array. Basta que: adicionemos os elementos pelo lado direito do array; retiremos os elementos sempre pela esquerda; e mantenhamos o índice f com a posição do elemento que se encontre na frente (o mais à esquerda) e o número de elementos sz presentes na queue. Por razões de eficiência, opta-se por não remover “fisicamente” o elemento que se encontra na frente (o mais à esquerda) na verdade, limitamo-nos a sinalizar que a frente da fila passa a iniciar-se na posição seguinte (daí a necessidade do atributo f); dessa forma evita-se estar constantemente a deslocar todos os restantes elementos uma posição à esquerda (shift left). Implementação de estruturas de dados lineares Algoritmos e Estrutura de Dados 37  Queue baseada num array circular Com sucessivas inserções à direita e remoções à esquerda, a queue vai-se deslocando no interior do array (como se de uma “lagarta” se tratasse☺) A uma dada altura a queue encostar-se-á completamente à direita. Esta não é notoriamente uma gestão eficiente dos recursos de memória Queue lotada: não é possível inserir novos elementos, ainda que tenha ficado à esquerda uma grande quantidade de espaço inutilizada. Uma solução bastante mais eficiente, consiste em aproveitar as posições livres que vão ficando para trás Isso consegue-se, utilizando um array circular; O array é o mesmo, o modo como o usamos é que é circular. Implementação de estruturas de dados lineares Algoritmos e Estrutura de Dados 38  Queue baseada num array circular – operação enqueue Para que um array ‘funcione’ na forma circular basta considerar que a seguir à posição de índice N- 1 seguir-se-á a posição 0. Logo que haja espaço na queue, a posição de inserção é sempre dada por: r = (f+sz) % N; A operação enqueue lança uma exceção sempre que a queue esteja cheia Algoritmo enqueue(obj): if sz=N then throw IllegalStateException; else r ← (f+sz)%N; data[r] ← obj; sz++; Implementação de estruturas de dados lineares Algoritmos e Estrutura de Dados 39  Queue baseada num array circular – operação dequeue A operação dequeue devolve null caso a queue esteja vazia. Sempre que se remove um elemento da queue, a posição do seu primeiro elemento passa a ser dada por: f = (f+1) % N; Algoritmo dequeue(): if sz=0 then return null; else obj ← data[f]; f ← (f+1)%N; sz--; return obj; Implementação de estruturas de dados lineares Algoritmos e Estrutura de Dados 40  Queue estática – possível implementação [1/2] Implementação de estruturas de dados lineares Algoritmos e Estrutura de Dados 41  Queue estática – possível implementação [2/2] Implementação de estruturas de dados lineares Algoritmos e Estrutura de Dados 42  Queue Dinâmica – LinkedQueue Para criarmos uma queue suportada por uma SLL, bastar-nos-á mapear os métodos da classe SinglyLinkedList para os da nossa interface Queue, de forma a ficarmos com uma nova classe com as funcionalidades da SinglyLinkedList mas com a interface da queue. Designemos essa nova classe por LinkedQueue, a qual terá como atributo privado uma SinglyLinkedList; e usará, na definição dos seus métodos, as correspondências mostradas na tabela. Implementação de estruturas de dados lineares Algoritmos e Estrutura de Dados 43 Deque Fila com dupla terminação Algoritmos e Estrutura de Dados 44  Deque Uma Deque (Double-ended queue – fila com dupla terminação) é uma fila que suporta a inserção e remoção de elementos quer pelo início quer pelo fim da coleção. A Deque é uma ADT mais geral que a Stack e Queue em conjunto, e essa caraterística poderá ser útil em algumas aplicações específicas. Por exemplo, a lista de espera num restaurante poderá ser melhor representada pelo comportamento duma deque: por vezes o cliente que está à frente pode ser retirado da fila e posteriormente constatar-se não haver ainda mesa disponível; nesse caso será de todo conveniente recolocar a pessoa no início e não no fim da fila; outra situação recorrente é o cliente que está no fim ficar impaciente e abandonar o restaurante (e teríamos que ter uma fila ainda mais geral caso pretendêssemos modelar o abandono de clientes do meio da fila). Portanto, uma Deque pode-se comportar como uma Queue, como uma Stack, ou então como uma estrutura de dados mais completa e mais versátil. dispõe de dois conjuntos simétricos de métodos destinados a assegurar as operações de inserção e remoção e consulta por ambos os extremos da fila. Implementação de estruturas de dados lineares Algoritmos e Estrutura de Dados 45  Interface Deque Implementação de estruturas de dados lineares Algoritmos e Estrutura de Dados 46  Exemplo de operações sobre uma deque Implementação de estruturas de dados lineares Algoritmos e Estrutura de Dados 47  Implementação duma deque Também uma deque pode ser facilmente implementada quer usando uma array (solução estática) quer usando uma lista ligada (solução dinâmica). Implementação dinâmica – classe LinkedDeque dado que a deque requer que as inserções e remoções se possam fazer por ambos os extremos da coleção, a lista duplamente ligada será a opção mais indicada; com essa opção, a complexidade da operação de remoção do último nodo será de ordem constante em vez de linear (continuando assim todas operações de O(1)) na verdade, a classe DoublyLinkedList já implementa toda a interface Deque; podemos assim rapidamente criar a nova classe LinkedDeque, fazendo-a derivar da classe DoublyLinkedList e declarando-a como implementando a interface Deque, podendo mesmo ficar com o corpo completamente vazio. public class LinkedDeque extends DoublyLinkedList implements Deque{ ☺☺☺ } Implementação estática – classe ArrayDeque usa-se um array com comportamento circular, similar ao do ArrayQueue; para além desse array, o ArrayDeque deve conter também os atributos f e sz, de forma a manter quer o índice da posição do 1º elemento quer a quantidade de elementos corrente. Implementação de estruturas de dados lineares Algoritmos e Estrutura de Dados 48  Deque baseada num array circular – inserção e remoção Já sabemos que para que um array ‘funcione’ na forma circular devemos considerar que a seguir à posição de índice N-1 seguir-se-á a posição 0 (sendo N a dimensão do array). Logo que haja espaço na deque, a posição de inserção no início será dada por: r = (f+N-1) % N; Algoritmo addFirst(e): if sz=N then // lança uma exceção sempre que a deque esteja cheia throw IllegalStateException; else f ← (f+N-1)%N; data[f] ← e; sz++; O método removeLast(), para além de devolver o último elemento, que estará na posição (f+sz-1)%N, e de forçar a desalocação do mesmo, apenas tem que decrementar o número de elementos (atributo sz). Os métodos addLast(e) e removeFirst() implementam-se da mesma forma que os métodos, respetivamente, enqueue(e) e dequeue() da queue estática ArrayQueue. O método last() devolve o último elemento, que estará na posição (f+sz-1)%N. Implementação de estruturas de dados lineares Algoritmos e Estrutura de Dados 49 Implementação de iteradores Algoritmos e Estrutura de Dados 50  Implementação de iteradores – a interface Iterator Como vimos já anteriormente, o Java, visando a unificação do processo de iteração e a sua independência em relação à organização interna das coleções, disponibiliza-nos a interface java.util.Iterator, com os seguintes métodos: hasNext( ): verifica se existe pelo menos mais um elemento na coleção; next( ): devolve o próximo elemento da coleção e avança para o seguinte. A combinação destes dois métodos permite-nos, como sabemos, contruir facilmente um ciclo para aceder, um a um, os elementos referenciados pelo iterador (em geral, todos os elementos duma coleção). Por exemplo, se tivermos uma dada coleção de strings, designada collection, podemos mostrar todo o seu conteúdo, através de uma iteração explícita ou usando simplesmente a construção for-each: Iterator it = collection.iterator(); while (it.hasNext()) { for(String val: collection) String val = it.next(); System.out.println(val) System.out.println(val); // next() e hasNext() invocados } // de forma implícita A interface java.util.Iterator dispõe ainda de outro método que opcionalmente pode ser suportado pelos iteradores: remove( ): remove da coleção o elemento devolvido pela invocação mais recente do método next(); Devolve a exceção IllegalStateException se o método next() ainda não foi chamado ou então se foi já chamado o remove() depois da última invocação do next(). Este método pode ser útil, por exemplo, para filtrar os elementos duma coleção (por ex. excluir todos os valores negativos duma coleção de inteiros). No entanto, para simplificarmos as nossas soluções, não vamos implementar o método remove() nos iteradores das nossas coleções. Limitar-nos-emos a lançar a exceção UnsupportedOperationException sempre que esse método seja invocado. Implementação de estruturas de dados lineares Algoritmos e Estrutura de Dados 51  Implementação de iteradores – a interface Iterable Na versão mais simples (iteradores unidirecionais), cada iterador é usado para uma única passagem, uma vez que, quando chegado ao fim da coleção, não tem forma de voltar ao seu início. Ainda assim, a coleção poderá ser iterada várias vezes, mas por iteradores diferentes. (No Java, apenas os iteradores específicos de listas (java.util.ListIterator) não têm esse comportamento – iteradores bidirecionais) Para isso a coleção deve suportar um método especial, responsável por criar e devolver um novo iterador, de cada vez que for chamado. Para possibilitar uma maior uniformização, o Java disponibiliza-nos outra interface, chamada Iterable, que inclui precisamente esse método: iterator( ): cria e devolve um iterador para os elementos da coleção; Uma qualquer coleção do Java é iterável (implementa a interface Iterable), mas não é ela própria um iterador, tem, isso sim, a capacidade de produzir um iterador para os seus elementos, através do seu método iterator(). Cada invocação do método iterator() de uma dada coleção devolve então um novo iterador para os seus elementos, sendo assim possível múltiplas passagens (iterações) sobre uma mesma coleção; podendo mesmo processarem-se em simultâneo. Implementação de estruturas de dados lineares Algoritmos e Estrutura de Dados 52  Estilos de Iteradores Existem, essencialmente, duas formas de implementar iteradores, que diferem naquilo que é feito, quer no momento inicial da criação do iterador, quer nos vários momentos em que se faz avançar o iterador com a invocação do next(). Snapshot iterator (iterador instantâneo) – ver ilustração que se segue mantém a sua própria cópia privada (normalmente linear) da sequência de elementos, construída logo no momento em que o iterador é criado – faz uma captura instantânea do estado da coleção nesse preciso momento; é como se guardasse uma foto instantânea dos elementos da coleção, tirada logo no início; por isso, este iterador não é afetado por alterações subsequentes que venham a acontecer na coleção original; a sua implementação requer que se faça a travessia (se percorra), logo no início, toda a coleção; por isso, a criação deste iterador numa coleção linear é de complexidade O(n), quer nas operações envolvidas, quer no espaço ocupado. Lazy iterator (iterador ‘preguiçoso’) – ver ilustração que se segue em vez de se munir logo à partida de uma cópia da sequência de elementos colecionados, para depois passar a aceder aos elementos dessa cópia, acede diretamente ao elemento da coleção original no momento em que o método next() é invocado; por isso, o comportamento deste iterador é afetado se ocorrerem alterações na coleção durante a iteração; uma vantagem deste iterador é a sua criação ser de complexidade temporal e espacial O(1). Como exemplo, demonstraremos como implementar iteradores do tipo ‘lazy’ para as nossas coleções: ArrayStack, LinkedStack, ArrayQueue… iteradores instantâneos revelar-se-ão particularmente uteis em coleções que se suportem em estruturas de dados não lineares, como veremos no próximo capítulo. Implementação de estruturas de dados lineares Algoritmos e Estrutura de Dados 53  Estilos de Iteradores Snapshot iterator Coleção iterável cursor Lazy iterator cursor Implementação de estruturas de dados lineares Algoritmos e Estrutura de Dados 54  Tornemos as nossas coleções iteráveis Vamos mostrar como tornar iteráveis as coleções que andámos a desenvolver: ArrayStack, LinkedStack, ArrayQueue… depois, seguindo um processo análogo, facilmente se conseguirá adicionar a uma qualquer outra coleção um mecanismo de iteração equivalente. Basicamente, para que uma coleção se torne iterável, a mesma deve passar a implementar a interface Iterable, que subentende os seguintes procedimentos: a coleção deve declarar que implementa a interface Iterable; e consequentemente implementar o método iterator() dessa interface, que deverá devolver um iterador específico para o tipo de coleção em causa; para isso, o tipo desse iterador específico já deve estar definido como classe interna da própria coleção, devendo essa classe interna implementar a interface java.util.Iterator. Se assumirmos que qualquer stack deve ser iterável, então a própria interface Stack já deve refletir esse requisito, estendendo ela própria a interface Iterable: public interface Stack extends Iterable {... } E como ambas as stacks concretas implementam a interface Stack, o primeiro dos procedimentos acaba por já estar a ser cumprido, sequem-se as devidas adaptações das coleções ArrayStack, LinkedStack, ArrayQueue… refletindo o cumprimento dos restantes procedimentos. Como também vamos pretender que qualquer queue ou deque seja iterável, então as interfaces Queue e Deque deverão igualmente estender (derivar de) a interface Iterable Implementação de estruturas de dados lineares Algoritmos e Estrutura de Dados 55  Tornar a coleção ArrayStack iterável [1/2] Método imposto pela interface Iterable, da qual passou a derivar a interface Stack. Implementação de estruturas de dados lineares Algoritmos e Estrutura de Dados 56  Tornar a coleção ArrayStack iterável [2/2] Implementação de estruturas de dados lineares Algoritmos e Estrutura de Dados 57