Fila de média móvel java

Implementando uma fila FIFO de comprimento fixo em Java Ao trabalhar com dados de séries temporais, muitas vezes é necessário calcular somas de números consecutivos por um período de tempo predeterminado. Imagine, por exemplo, calcular uma média móvel com um tamanho fixo. Vamos olhar para uma série de tempo muito simples. Supondo que uma média móvel de comprimento 4 resulta na seguinte matriz: A fórmula para uma média móvel de comprimento 4 é assim: MA t (Soma de todos os elementos de t-3 a t) / 4 Como implementaríamos eficientemente isto em código Java O problema é que precisamos calcular a Soma na fórmula para cada média móvel. Claro que é possível sempre reiterar sobre todos os números no período de tempo atual para fazê-lo, mas isso é desnecessariamente lento. Em vez disso, podemos simplesmente subtrair o último elemento no período de tempo e adicionar o mais novo a Sum. Desta forma, podemos salvar um número significativo de computações desnecessárias. Ainda temos que acompanhar o que realmente são os elementos antigos e novos. Temos de armazenar esses números em algum lugar. Uma estrutura de dados apropriada seria uma fila de números first-in-first-out (FIFO). Mas como exatamente uma fila FIFO pode ser implementada em uma linguagem de programação (não-funcional) como Java? A primeira idéia é tipicamente usar uma implementação baseada em array e mudar a posição de elementos na matriz criando repetidamente cópias ligeiramente deslocadas de A matriz. No exemplo acima, precisamos criar uma nova matriz cinco vezes, uma vez para cada nova soma que está sendo calculada. Isto é, naturalmente, muito ineficiente, porque a criação de uma matriz na memória é relativamente lento. Implementações baseadas em classes como java. util. ArrayList ou java. util. Vector já são muito melhores, porque internamente eles dependem de matrizes e índices mais longos. Ainda assim, esta não é a melhor solução, uma vez que os índices internos se movem para fora dos limites da matriz interna, uma nova cópia da matriz interna deve ser criada. Uma alternativa típica para implementar filas FIFO está, portanto, usando uma lista vinculada: A vantagem é óbvia, não mais copiar ou recriar matrizes na memória. Tudo o que temos a fazer é manipular alguns ponteiros. Claro que perdemos a vantagem de avaliar diretamente um elemento na fila por índice, mas para o nosso propósito - calculando médias móveis - isso é algo que não queremos fazer de qualquer maneira. Ontem, de repente me ocorreu que há realmente uma alternativa ainda melhor se o comprimento da fila é fixo (como no nosso exemplo). Podemos efetivamente usar um anel. Adicionar um novo número à fila e largar o mais antigo é o mesmo que simplesmente substituir o elemento mais antigo neste anel por um novo. Internamente, podemos usar novamente uma matriz de um comprimento fixo em combinação com um índice rotativo. É assim que o código se parece em Java. Primeiro, vamos criar nossa própria interface de fila: Esta interface se desvia um pouco da fornecida nas bibliotecas Java, mas isso não é importante por enquanto. Em seguida, a implementação da nossa fila: A fila quotrollsquot através do anel. Adicionar um novo elemento na cabeça da fila remove automaticamente o elemento mais antigo da fila - não é necessário copiar arrays ou redefinir referências de objeto. Ao contrário das listas vinculadas, podemos acessar cada elemento do anel diretamente com o método get. Finalmente, podemos criar uma subclasse do nosso objeto de fila que rodará graciosamente à medida que novos valores são adicionados à fila / anel. Podemos usar a classe agora. O comprimento da média móvel é inicialmente definido através do comprimento da matriz dado ao seu constructor. I necessidade de manter o controle dos últimos 7 dias de trabalho horas em um arquivo plano de leitura loop. Seu ser usado para medir fatigueability de rosters do trabalho. Agora eu tenho algo que funciona, mas parece bastante detalhado e Im não tenho certeza se theres um padrão thats mais sucinto. Atualmente, eu tenho uma classe Java com uma matriz estática para armazenar os últimos dados x dias, então como eu leio através do arquivo, eu cortar o primeiro elemento e mover os outros 6 (por uma semana rodando total) de volta por um. O processamento dessa matriz estática é feito em seu próprio método ie. Minha pergunta: esta é uma abordagem de design razoável, ou há algo ofuscantemente óbvio e simples para fazer essa tarefa Caras de agradecimento perguntou 30 ago 11 at 14:33 Thanks alot guys: I39ve tem a mensagem: use um objeto de nível mais alto e explorar o Métodos relevantes ou um tampão circular. Grandes respostas, todas elas. Quando você pensa sobre isso, você sempre precisa de acesso a toda a matriz para que você possa se livrar da primeira entrada - que eu wasn39t 100 certeza do meu próprio. I39m aliviado que eu hadn39t perdeu um forro 1 e foi basicamente em uma faixa razoável, se não eficiente e concisa Isso é o que eu amo sobre este site: de alta qualidade, respostas relevantes de pessoas que sabem o seu sht. Ndash Pete855217 Aug 30 11 at 15:05 Por que você inicializar runningTotal para null Qual é o seu tipo Onde é declarado Faria bem se você colocar alguns exemplos de código que se assemelham ao código Java real. Seguindo em frente, minha crítica seria a seguinte: a sua função faz muito. Uma função ou método deve ser coeso. Mais apropriadamente, eles deveriam fazer uma coisa e uma coisa só. Pior ainda, o que acontece no seu loop for quando x 5 Você copiar runningTotal6 em runningTotal5. Mas então você tem duas cópias do mesmo valor na posição 5 e 6. No seu projeto, sua função move / shuffles os itens em sua matriz calcula o total imprime coisas para o erro padrão retorna o total Ele faz muito. Minha primeira sugestão é não mover coisas ao redor da matriz. Em vez disso, implementar um buffer circular e utilizá-lo em vez da matriz. Simplificará seu projeto. Minha segunda sugestão é dividir as coisas em funções que são coesas: ter uma estrutura de dados (um buffer circular) que permite adicionar a ele (e que descarta a entrada mais antiga sempre que atingir sua capacidade.) Ter a estrutura de dados implementar um Interator tem uma função que calcula o total no iterador (você não se importa se você está calculando o total de uma matriz, lista ou bufer circular.) Não chamá-lo total. Chamá-lo de soma, que é o que você está computando. Isso é o que fazer :) That39s grande informação luis, no entanto lembre-se esta função é uma pequena parte da funcionalidade da classe, e seria exagero para adicionar muito código para torná-lo perfeito. Você está tecnicamente correto, e eu entendo que meu código faz muito 39, mas ao mesmo tempo às vezes é melhor errar do lado do código menor, mais claro do que ir para a perfeição. Dado o meu Java habilidades, mesmo fazendo o pseudocode você descreve compilação teria me soprar meu orçamento sobre este (), mas obrigado pela descrição clara. Ndash Pete855217 Aug 31 11 at 2:23 Hmmm, não é sobre a perfeição, mas sobre as práticas industriais estabelecidas que temos conhecimento para as últimas 3 décadas. Código limpo é sempre um que é particionado. Temos décadas de evidências que indicam que este é o caminho a percorrer no caso geral (em termos de custo-eficiência, redução de defeitos, compreensão, etc.). A menos que seja um código descartável para um tipo único de coisa. Nunca é custoso fazer isso quando se inicia qualquer análise de problemas desta maneira. Codificação 101, quebrar o problema eo código segue, nem overkill nem difícil) ndash luis. espinal Aug 31 11 at 15:55 Sua tarefa é muito simples eo aproach que você adotou é certamente bom para o trabalho. No entanto, se você quiser usar um projeto melhor, você deve se livrar de todo esse movimento número você melhor usar uma fila FIFO e fazer bom uso de métodos push e pop dessa forma o código não vai refletir qualquer movimento de dados, apenas as duas ações lógicas De novos dados e remover dados com mais de 7 dias. Respondido ago 30 11 at 14: 49Stacks and Queues Introdução Tanto as pilhas como as filas são como listas (coleções ordenadas de itens), mas com operações mais restritas. Ambos podem ser implementados usando uma matriz ou usando uma lista vinculada para armazenar os itens reais. Pilhas A imagem conceitual de uma pilha ADT é algo como isto: Pense em uma pilha de jornais ou bandejas em uma cafeteria. O único item que pode ser retirado (ou mesmo visto) é o item mais recentemente adicionado (ou superior) um Stack é um tipo de dados abstratos Last-In-First-Out (LIFO). Aqui estão as operações de ADT da pilha: return true iff a pilha está vazia add ob na parte superior da pilha remove e retorna o item da parte superior da pilha (erro se a pilha estiver vazia) retorna o item que está no topo da pilha A pilha. Mas não removê-lo (erro se a pilha estiver vazia) Em Java criamos a interface StackADT como: Filas A imagem conceitual de uma fila ADT é algo como isto: Pense em pessoas em pé na fila. Uma Fila é um tipo de dados abstratos First-In-First-Out (FIFO). Os itens só podem ser adicionados na parte traseira da fila e o único item que pode ser removido é o que está na frente da fila. Aqui estão as operações ADT da fila: return true iff a Fila está vazia void enqueue (E ob) adiciona ob à parte traseira da Fila remove e retorna o item da frente da Fila (erro se a Fila estiver vazia) Em Java nós Crie a interface QueueADT como: Implementando pilhas A pilha ADT é muito semelhante à lista ADT, portanto, suas implementações também são bastante semelhantes. Implementação de matrizes Abaixo está a definição da classe ArrayStack, usando uma matriz para armazenar os itens na pilha note que incluímos uma variável estática final INITSIZE. Para ser usado pelo construtor ArrayStack como o tamanho inicial da matriz (a mesma coisa foi feita para a classe ArrayList). TESTE-SE 1 Escreva o construtor ArrayStack. O método push é como a versão do método List add que adiciona um objeto ao final da lista (porque os itens são sempre empurrados para o topo da pilha). Observe que cabe a nós como os projetistas da classe ArrayStack decidir qual final da matriz corresponde ao topo da pilha. Poderíamos escolher sempre adicionar itens no início da matriz ou sempre adicionar itens no final da matriz. No entanto, é claramente não é uma boa idéia para adicionar itens no início da matriz, uma vez que requer mover todos os itens existentes, ou seja, essa escolha faria push ser O (N) (onde N é o número de itens na pilha). Se adicionarmos itens no final da matriz, então o tempo de envio dependerá de como lidamos com a expansão da matriz. A implementação ingênua faz empurrar O (1) quando a matriz não está cheia, O (N) quando está cheia e O (1) em média. Se usarmos o truque de array de sombra, então push é sempre O (1). Aqui estão as imagens antes e depois, ilustrando os efeitos de uma chamada para empurrar: E heres o código para o método push: O método pop precisa remover o item top-of-stack e retorná-lo, conforme ilustrado abaixo. Observe que, na imagem, o valor bbb ainda está em items2, no entanto, esse valor não está mais na pilha porque numItems é 2 (o que significa que items1 é o último item na pilha). TEST YOURSELF 2 Complete o método pop, usando o cabeçalho seguinte O método peek é muito semelhante ao método pop, exceto que ele retorna somente o valor top-of-stack sem alterar a pilha. O método isEmpty simplesmente retorna true iff numItems é zero. TEST YOURSELF 3 Preencha a tabela a seguir, usando a notação Big-O para dar as piores e médias vezes para cada um dos métodos ArrayStack para uma pilha de tamanho N. Implementação da lista vinculada Para implementar uma pilha usando uma lista vinculada, Deve primeiro definir a classe Listnode. A definição de Listnode é a mesma que usamos para a implementação de lista vinculada da classe LinkedList. As assinaturas dos métodos da interface StackADT são independentes de se a pilha é implementada usando uma matriz ou usando uma lista vinculada para implementar o StackADT usando uma lista vinculada, bem alterar o nome da classe que implementa a pilha eo tipo de itens Campo: Como discutido acima, uma propriedade importante de pilhas é que os itens são apenas empurrado e estalou em uma extremidade (o topo da pilha). Se implementarmos uma pilha usando uma lista vinculada, podemos escolher qual final da lista corresponde ao topo da pilha. É mais fácil e mais eficiente adicionar e remover itens na frente de uma lista vinculada, portanto, vamos escolher a frente da lista como o topo da pilha (ou seja, o campo de itens será um ponteiro para o nó que contém o Item de topo da pilha). Abaixo está uma imagem de uma pilha representada usando uma lista vinculada neste caso, os itens foram empurrados em ordem alfabética, então cc está no topo da pilha: Observe que, na imagem, o topo da pilha é para a esquerda ( Na frente da lista), enquanto que para a implementação de matriz, o topo da pilha estava para a direita (no final da matriz). Vamos considerar como escrever o método pop. Ele precisará executar as seguintes etapas: Verifique se a pilha está vazia, em caso afirmativo, lance um EmptyStackException. Remova o primeiro nó da lista vinculada definindo itens items. getNext (). Diminuir numItems. Retorna o valor que estava no primeiro nó na lista. Note que no momento em que chegamos ao último passo (retornando o valor do topo da pilha), o primeiro nó já foi removido da lista, então precisamos salvar seu valor para retorná-lo (bem, chame esse passo 2 (a)). Heres o código e uma ilustração do que acontece quando pop é chamado para uma pilha contendo cc, bb, aa (com cc na parte superior). Agora vamos considerar o método push. Aqui estão as imagens antes e depois, ilustrando o efeito de uma chamada para empurrar quando a pilha é implementada usando uma lista vinculada: As etapas que precisam ser executadas são: Criar um novo nó cujo campo de dados contém o objeto a ser empurrado e cujo próximo Contém um ponteiro para o primeiro nó da lista (ou null se a lista estiver vazia). Observe que o valor para o próximo campo do novo nó é o valor no campo LLStack s itens. Alterar itens para apontar para o novo nó. Increment numItems. TESTE-SE 4 Complete o método push, usando o seguinte cabeçalho. Os métodos restantes (o construtor, peek. E vazio) são bastante simples. Você deve ser capaz de implementá-los sem grandes problemas. TESTE-SE 5 Preencha a tabela a seguir, usando a notação Big-O para dar as piores vezes para cada um dos métodos LLStack para uma pilha de tamanho N, assumindo uma implementação de lista vinculada. Olhe para trás na tabela que você preencheu para a implementação de array. Como as horas comparam Quais são as vantagens e desvantagens de usar uma matriz vs usando uma lista vinculada para implementar a pilha ADT Implementar filas A principal diferença entre uma pilha e uma fila é que uma pilha é acessada apenas a partir do topo, enquanto uma fila É acessado de ambas as extremidades (a partir da parte traseira para adicionar itens, e da frente para remover itens). Isso torna tanto a matriz quanto a implementação de lista vinculada de uma fila mais complicada do que as implementações de pilha correspondentes. Implementação de Array Vamos considerar primeiro uma implementação de Fila que é muito semelhante à nossa implementação de lista (baseada em array). Aqui está a definição de classe: Podemos implementar enqueue adicionando o novo item no final da matriz e implementar dequeue, salvando o primeiro item na matriz, movendo todos os outros itens um lugar para a esquerda e retornando o valor salvo. O problema com esta abordagem é que, embora a operação enqueue é eficiente, a operação dequeue não é - ele requer tempo proporcional ao número de itens na fila. Para tornar enqueue e dequeue eficiente, precisamos do seguinte insight: Não há nenhuma razão para forçar a frente da fila sempre para estar em items0. Nós podemos deixá-lo mover acima como os artigos são dequeued. Para fazer isso, precisamos acompanhar os índices dos itens na frente e atrás da fila (por isso precisamos adicionar dois novos campos para a classe ArrayQueue, frontIndex e rearIndex. Ambos de tipo int). Para ilustrar esta idéia, aqui está uma imagem de uma fila depois de algumas operações de enqueue e dequeue terem sido realizadas: Agora pense sobre o que deve acontecer a esta fila se enqueue mais dois itens: dd e ee. Claramente dd deve ser armazenado em items6. Então o que poderíamos aumentar o tamanho da matriz e colocar ee em items7. Mas que levaria a desperdício de espaço - que nunca iria reutilizar items0. Itens1. Ou itens2. Em geral, os itens na fila ficariam deslizando para a direita na matriz, causando mais e mais espaço desperdiçado no início da matriz. Uma abordagem melhor é permitir que o índice traseiro se encaixe (neste caso, de 6 a 0), desde que haja espaço vazio na frente da matriz. Da mesma forma, se após enqueuing dd e ee nós dequeue quatro itens (de modo que somente ee é deixado na fila), o índice dianteiro terá que envolver em torno de 6 a 0. Heres uma imagem do que acontece quando nós enqueue dd e ee: Conceitualmente, a matriz é uma matriz circular. Pode ser mais fácil visualizá-lo como um círculo. Por exemplo, a matriz para a fila final mostrada acima pode ser pensado como: Nós ainda precisamos pensar sobre o que deve acontecer se a matriz estiver cheia bem considerar esse caso em um minuto. Heres o código para o método enqueue, com o caso de matriz completa ainda a ser preenchido: Note que em vez de usar incrementIndex, podemos usar o mod operator (), e escrever: rearIndex (rearIndex 1) items. length. No entanto, o operador mod é bastante lento e é fácil obter essa expressão errada, por isso vamos usar o método auxiliar (com uma verificação para o caso wrap-around) em vez disso. Para ver por que não podemos simplesmente usar expandArray quando a matriz está cheia, considere a imagem mostrada abaixo. Depois de chamar expandArray. O último item na fila ainda está bem antes do primeiro item - ainda não há lugar para colocar o novo item (e há uma grande lacuna no meio da fila, de items7 para items13). O problema é que o expandArray copia os valores na matriz antiga para as mesmas posições na nova matriz. Isso não funciona para a implementação de fila que precisamos para mover os valores wrapped-around para vir após os valores non-wrapped-around na nova matriz. As etapas que precisam ser executadas quando a matriz está cheia são: Alocar uma nova matriz de duas vezes o tamanho. Copie os valores no intervalo itemsfrontIndex para itemsitems. length-1 na nova matriz (começando na posição frontIndex na nova matriz). Copie os valores no intervalo items0 para itemsrearIndex na nova matriz (começando na posição items. length na nova matriz). Nota: se a frente da fila estava em items0. Em seguida, todos os valores foram copiados pela etapa 2, portanto, este passo não é necessário. Defina itens para apontar para a nova matriz. Corrija o valor de rearIndex. Heres uma ilustração: E heres o código final para enqueue: O método dequeue também usará o método incrementIndex para adicionar um ao frontIndex (com wrap-around) antes de retornar o valor que estava na frente da fila. O outro método ArrayQueue, isEmpty. É o mesmo que para a classe ArrayStack - ele apenas usa o valor do campo numItems. Implementação de lista vinculada A primeira decisão no planejamento da implementação de lista vinculada do ADT de fila é qual final da lista corresponderá à frente da fila. Lembre-se de que os itens precisam ser adicionados à parte traseira da fila e removidos da frente da fila. Portanto, devemos fazer a nossa escolha com base em saber se é mais fácil adicionar / remover um nó do front / end de uma lista vinculada. Se mantemos ponteiros para o primeiro eo último nós da lista, podemos adicionar um nó em qualquer extremidade em tempo constante. No entanto, embora possamos remover o primeiro nó na lista em tempo constante, remover o último nó requer primeiro localizar o nó anterior, o que leva tempo proporcional ao comprimento da lista. Portanto, devemos escolher fazer com que o fim da lista seja a parte traseira da fila ea frente da lista seja a frente da fila. A definição de classe é a semelhante à implementação de matriz: Heres uma imagem de uma fila com três itens, aa, bb, cc, com aa na frente da fila: Você deve ser capaz de escrever todos os métodos LLQueue usando o Código que você escreveu para a implementação da lista vinculada do ADT de lista como um guia. Comparação de Implementações de Array e Linked-List As vantagens e desvantagens das duas implementações são essencialmente as mesmas que as vantagens e desvantagens no caso do List ADT: Na implementação de lista vinculada, um ponteiro deve ser armazenado para cada item no Pilha / fila, enquanto a matriz armazena apenas os itens próprios. Por outro lado, o espaço usado para uma lista vinculada é sempre proporcional ao número de itens na lista. Isso não é necessariamente verdadeiro para a implementação de matriz conforme descrito: se um monte de itens são adicionados a uma pilha / fila e, em seguida, removidos, o tamanho da matriz pode ser arbitrariamente maior do que o número de itens na pilha / fila. No entanto, podemos corrigir esse problema modificando as operações pop / dequeue para encolher a matriz quando se torna muito vazio. Para a implementação de matriz, os tempos de pior caso para os métodos push e enqueue são O (N) para a implementação naive, para uma pilha / fila com N itens (para alocar uma nova matriz e copiar os valores) , Essas duas operações são O (1). Para a implementação da lista vinculada, push e enqueue são sempre O (1). Aplicativos de pilhas e filas As pilhas são usadas para gerenciar métodos em tempo de execução (quando um método é chamado, seus parâmetros e variáveis ​​locais são empurrados para uma pilha quando o método retorna, os valores são extraídos da pilha). Muitos algoritmos de análise (usados ​​pelos compiladores para determinar se um programa é sintaticamente correto) envolvem o uso de pilhas. As pilhas podem ser usadas para avaliar expressões aritméticas (por exemplo, por um programa de calculadora simples) e também são úteis para algumas operações em gráficos. Uma estrutura de dados que aprenderemos mais adiante no semestre. As filas são úteis para muitas simulações e também são usadas para algumas operações em gráficos e árvores. TEST YOURSELF 6 Complete o método reverseQ. Cujo cabeçalho é dado abaixo. O método reverseQ deve usar uma pilha para inverter a ordem dos itens em seu parâmetro Queue.4.3 Pilhas e filas Nesta seção, apresentamos dois tipos de dados estreitamente relacionados para manipular coleções arbitrariamente grandes de objetos: a pilha ea fila. Pilhas e filas são casos especiais da idéia de uma coleção. Cada um é caracterizado por quatro operações: criar a coleção, inserir um item, remover um item e testar se a coleção está vazia. Pilhas. Uma pilha é uma coleção que se baseia na diretiva last-in-first-out (LIFO). Por tradição, nomeamos o método de inserção de pilha push () ea pilha remove a operação pop (). Também incluímos um método para testar se a pilha está vazia, conforme indicado na seguinte API: Implementações de matriz de pilhas. Representar pilhas com matrizes é uma idéia natural. Em particular, mantemos uma variável de instância n que armazena o número de itens na pilha e um item de matriz que armazena os n itens, com o item mais recentemente inserido em itemsn-1 eo item inserido menos recentemente em items0. Esta política permite-nos adicionar e remover itens no final sem mover qualquer um dos outros itens na pilha. Implementação de matriz de comprimento fixo de uma pilha de strings. ArrayStackOfStrings. java implementa esta abordagem para uma pilha de strings cuja capacidade máxima é especificada pelo argumento para o construtor. Para remover um item, decrementamos n e retornamos um para inserir um novo item, definimos um igual ao novo item e, em seguida, incrementamos n. Redimensionando a implementação de matriz de uma pilha de strings. ResizingArrayStackOfStrings. java é uma versão do ArrayStackOfStrings. java que dinamicamente ajusta o comprimento dos itens de matriz de modo que ele é suficientemente grande para armazenar todos os itens e mas não tão grande como para desperdiçar uma quantidade excessiva de espaço. Primeiro, em push (). Verificamos se há espaço para o novo item, se não, criamos uma nova matriz de duplo o comprimento da matriz antiga e copiar os itens da matriz antiga para a nova matriz. Da mesma forma, em pop (). Verificamos se a matriz é muito grande e, se for esse o caso, reduzimos para metade seu comprimento. Essa estratégia de duplicação e redução de metade garante que a pilha nunca desborda e nunca se torna menos de um quarto cheia. Redimensionando a implementação de matriz de uma pilha genérica. ResizingArrayStack. java implementa uma pilha genérica usando uma matriz de redimensionamento. Por razões técnicas, um elenco é necessário ao alocar a matriz de genéricos. Listas vinculadas. Uma lista ligada individualmente compreende uma sequência de nós. Com cada nó contendo uma referência (ou link) para seu sucessor. Por convenção, o link no último nó é nulo. Para indicar que ele termina a lista. Com a programação orientada a objetos, implementar listas vinculadas não é difícil. Definimos uma classe para a abstração do nó que é recursiva na natureza: Um objeto Node tem duas variáveis ​​de instância: uma String e um Node. A String é um espaço reservado neste exemplo para quaisquer dados que possamos querer estruturar com uma lista vinculada (podemos usar qualquer conjunto de variáveis ​​de instância) a variável de instância do tipo Node caracteriza a natureza vinculada da estrutura de dados. Vinculando uma lista vinculada. Por exemplo, para criar uma lista vinculada que contém os itens para. estar . E ou. Criamos um Nó para cada item: Inserir. Suponha que você deseja inserir um novo nó em uma lista vinculada. O local mais fácil para fazer isso é no início da lista. Por exemplo, para inserir a seqüência de caracteres não no início de uma determinada lista vinculada cujo primeiro nó é o primeiro. Nós salvamos primeiro em uma variável temporária oldFirst. Atribuir primeiro a um novo nó. E atribuir seu campo de item para não e seu próximo campo para oldFirst. Remover. Suponha que você deseja remover o primeiro nó de uma lista. Esta operação é ainda mais fácil: basta atribuir primeiro o valor first. next. Traversal. Para examinar cada item em uma lista vinculada, inicializamos uma variável de índice de laço x que faz referência ao primeiro nó da lista vinculada. Em seguida, encontramos o valor do item associado com x acessando x. item. E depois atualizar x para referir-se ao próximo Nó na lista vinculada, atribuindo-lhe o valor de x. next e repetindo este processo até que x seja nulo (o que indica que chegamos ao final da lista vinculada). Esse processo é conhecido como percorrendo a lista e é expressa sucintamente neste fragmento de código: Implementando pilhas com listas vinculadas. Representar pilhas com listas vinculadas é uma idéia natural. Em particular, mantemos primeiramente uma variável de instância que armazena uma referência ao item inserido mais recentemente. Esta política permite-nos adicionar e remover itens no início da lista vinculada sem acessar os links de quaisquer outros itens na lista vinculada. Implementação de lista vinculada de uma pilha de strings. LinkedStackOfStrings. java usa uma lista vinculada para implementar uma pilha de strings. A implementação é baseada em um nó de classe aninhado como o que estamos usando. Java nos permite definir e usar outras classes dentro de implementações de classe desta forma natural. Designamos a classe aninhada como privada porque os clientes não precisam saber nenhum dos detalhes das listas vinculadas. Implementação de listagem vinculada de uma pilha genérica. Stack. java implementa uma pilha genérica usando uma lista ligada individualmente. Fila. Uma fila suporta as operações de inserção e remoção usando uma disciplina first-in first-out (FIFO). Por convenção, nomeamos o enqueue de operação de inserção de fila ea operação de remoção de cola. Como indicado na API a seguir: Implementação de lista vinculada de uma fila. Queue. java implementa uma fila FIFO de cadeias usando uma lista vinculada. Como Stack. Nós mantemos uma referência primeiramente ao nó recentemente-mais recentemente adicionado na fila. Para eficiência, também mantemos uma última referência para o nó mais recentemente adicionado na fila. Redimensionando a implementação de matriz de uma fila. ResizingArrayQueue. java implementa uma fila usando uma matriz de redimensionamento. É semelhante a ResizingArrayStack. java. Mas mais complicado, uma vez que precisamos adicionar e remover itens de extremidades opostas da matriz. Genéricos. Desenvolvemos implementações de pilha que nos permitem construir uma pilha de um tipo específico, como String. Um mecanismo específico em Java conhecido como tipos genéricos nos permite criar coleções de objetos de um tipo a ser especificado pelo código do cliente. Implementando uma coleção genérica. Para implementar uma coleção genérica, especificamos um parâmetro de tipo. Como Item. Em parênteses angulares e usar esse parâmetro de tipo em nossa implementação em vez de um tipo específico. Por exemplo, Stack. java é a versão genérica de LinkedStackOfStrings. java Usando uma coleção genérica. Para usar uma coleção genérica, o cliente deve especificar o argumento de tipo quando a pilha é criada: Autoboxing. Desenvolvemos nossas pilhas para serem genéricas. De modo que eles objetos de qualquer tipo. Os recursos de linguagem Java conhecidos como autoboxing e unboxing nos permitem reutilizar código genérico com tipos primitivos também. O Java fornece tipos de objetos internos conhecidos como tipos de wrapper. Um para cada um dos tipos primitivos: Boolean. Inteiro. Duplo. Personagem. e assim por diante. Java converte automaticamente entre estes tipos de referência e os tipos primitivos correspondentes para que possamos escrever código como o seguinte: Iteração. Às vezes, o cliente precisa acessar todos os itens de uma coleção, um de cada vez, sem excluí-los. Para manter o encapsulamento, não queremos revelar a representação interna da fila (matriz ou lista vinculada) ao cliente. Para acomodar esse padrão de design, o Java fornece a instrução foreach. Você deve interpretar o seguinte para instrução no fragmento de código a seguir como para cada seqüência de caracteres s na coleção, print s. A implementação de uma coleção que ofereça suporte a iteração dessa maneira requer a implementação das interfaces Java java. util. Iterator e java. util. Iterable. Veja o livro para mais detalhes. Aplicativos de pilha e fila. Pilhas e filas têm inúmeras aplicações úteis. Avaliação da expressão aritmética. Uma aplicação importante de pilhas é na análise. Por exemplo, um compilador deve analisar expressões aritméticas escritas usando a notação infix. Por exemplo, a seguinte expressão de infixo é avaliada em 212. Evaluate. java avalia uma expressão aritmética totalmente entre parênteses. Abstração de chamada de função. A maioria dos programas usa pilhas implicitamente porque suportam uma maneira natural de implementar chamadas de função, da seguinte forma: em qualquer ponto durante a execução de uma função, defina seu estado como sendo os valores de todas as suas variáveis ​​e um ponteiro para a próxima instrução a ser executado. A maneira natural de implementar a abstração de chamada de função é usar uma pilha. Para chamar uma função, empurre o estado em uma pilha. Para retornar de uma chamada de função, pop o estado da pilha para restaurar todas as variáveis ​​para seus valores antes da chamada de função e retomar a execução na próxima instrução a ser executada. M / M / 1 fila. Um dos mais importantes modelos de enfileiramento é conhecido como uma fila M / M / 1, que tem sido mostrado para modelar com precisão muitas situações do mundo real. É caracterizada por três propriedades: Há uma fila servermdasha FIFO. Os tempos de intercalação para a fila obedecem a uma distribuição exponencial com taxa lambda por minuto. Os tempos de serviço de uma fila não vazia obedecem a uma distribuição exponencial com taxa mu por minuto. MM1Queue. java simulates an M / M /1 queue and plots a histogram of waiting times to standard drawing. Load balancing. LoadBalance. java simulate the process of assigning n items to a set of m servers. For each item, it chooses a sample of s servers and assigns the item to the server that has the fewest current items. Exercises Add a method isFull() to ArrayStackOfStrings. java. Write a filter Reverse. java that reads strings one at a time from standard input and prints them to standard output in reverse order. Write a stack client Parentheses. java that reads a string of parentheses, square brackets, and curly braces from standard input and uses a stack to determine whether they are properly balanced. For example, your program should print true for () and false for () . What does the following code fragment print when n is 50 Give a high-level description of what the code fragment does when presented with a positive integer n . Solution . prints the binary representation of n ( 110010 when n is 50). What does the following code fragment do to the queue queue . Solution . reverses the order of the strings in the queue. Add a method peek() to Stack. java that returns the most recently inserted element on the stack (without removing it). Add a method size() to both Queue. java and Stack. java that returns the number of items in the collection. Write a filter InfixToPostfix. java that converts an arithmetic expression from infix to postfix. Write a program EvaluatePostfix. java that takes a postfix expression from standard input, evaluates it, and prints the value. (Piping the output of your program from the previous exercise to this program gives equivalent behavior to Evaluate. java .) Develop a data type ResizingArrayQueueOfStrings. java that implements a queue wit ha fixed-length array in such a way that all operations take constant time. Modify MM1Queue. java to make a program MD1Queue. java that simulates a queue for which the service times are fixed (deterministic) at rate mu. Verify Littles law for this model. Develop a class StackOfInts. java that uses a linked-list representation (but no generics) to implement a stack of integers. Write a client that compares the performance of your implementation with StackltIntegergt to determine the performance penalty from autoboxing and unboxing on your system. Linked-List Exercises Suppose x is a linked-list node. What is the effect of the following code fragment Solution . Deletes from the list the node immediately following x . Write a method delete() that takes the first node in a linked list and an int argument k and deletes the k th node in the linked list, if it exists. Suppose that x is a linked-list node. What is the effect of the following code fragment Solution . Inserts node t immediately after node x . Why does the following code fragment not have the same effect as in the previous question Solution . When it comes time to update t. next . x. next is no longer the original node following x . but is instead t itself Creative Exercises Josephus problem. In the Josephus problem from antiquity, n people are in dire straits and agree to the following strategy to reduce the population. They arrange themselves in a circle (at positions numbered from 0 to n minus1) and proceed around the circle, eliminating every mth person until only one person is left. Legend has it that Josephus figured out where to sit to avoid being eliminated. Write a Queue client Josephus. java that takes two integer command-line arguments m and n and prints the order in which people are eliminated (and thus would show Josephus where to sit in the circle). Topological sort. You have to sequence the order of n jobs that are numbered 0 to n-1 on a server. Some of the jobs must complete before others can begin. Write a program TopologicalSorter. java that takes a command-line argument n and a sequence on standard input of ordered pairs of jobs (i, j), and then prints a sequence of integers such that for each pair (i, j) in the input, job i appears before job j. First, from the input, build, for each job (1) a queue of jobs that must follow it and (2) its indegree (the number of jobs that must come before it). Then, build a queue of all nodes whose indegree is 0 and repeatedly delete any job with a 0 indegree, maintaining all the data This process has many applications. For example, you can use it to model course prerequisites for your major so that you can find a sequence of courses to take so that you can graduate. Copy constructor for a stack. Create a new constructor for the linked - list implementation of Stack. java so that StackltStringgt t new StackltStringgt(s) makes t reference a new and independent copy of the stack s . You should be able to push and pop from either s or t without influencing the other. Recursive solution . create a copy constructor for a Node and use this to create the new stack. Non-recursive solution (untested): Quote. Develop a data type Quote. java that implements the following API: To do so, define a nested class Card that holds one word of the quotation and a link to the next word in the quotation: Circular quote. Repeated the previous exercise, but use a circular linked list . In a circular linked list, each node points to its successor, and the last node in the list points to the first node (instead of null, as in a standard null-terminated linked list). Reverse a linked list (iteratively). Write a nonrecursive function that takes the first Node in a linked list as an argument, and reverses the list, returning the first Node in the result. Solution . To accomplish this, we maintain references to three consecutive nodes in the linked list, reverse . first . and second . At each iteration we extract the node first from the original linked list and insert it at the beginning of the reversed list. We maintain the invariant that first is the first node of whats left of the original list, second is the second node of whats left of the original list, and reverse is the first node of the resulting reversed list. Reverse a linked list (recursively). Write a recursive function that takes the first Node in a linked list as an argument and reverses the list, returning the first Node in the result. Solution . Assuming the linked list has n elements, we recursively reverse the last n-1 elements, then append the first element to the end. Listing files. A folder is a list of files an folders. Write a program Directory. java that takes the name of a folder as a command line argument and prints all of the files contained in that folder, with the contents of each folder recursively listed (indented) under that folders name. Web Exercises Write a recursive function that takes as input a queue, and rearranges it so that it is in reverse order. Hint: dequeue() the first element, recursively reverse the queue, and the enqueue the first element. Add a method Item multiPop(int k) to Stack that pops k elements from the stack and returns them as an array of objects. Add a method Item toArray() to Queue that returns all N elements on the queue as an array of length N. What does the following code fragment do Fibonacci What data type would you choose to implement an Undo feature in a word processor Suppose you have a single array of size N and want to implement two stacks so that you wont get overflow until the total number of elements on both stacks is N1. How would you proceed Suppose that you implemented push in the linked list implementation of StackList with the following code. What is the mistake Solution . By redeclaring first . you are create a new local variable named first . which is different from the instance variable named first . Stack with one queue. Show how to implement a stack using one queue. Hint: to delete an item, get all of the elements on the queue one at a time, and put them at the end, except for the last one which you should delete and return. Listing files with a stack. Write a program that takes the name of a directory as a command line argument, and prints out all of the files contained in this directory and any subdirectories. Also prints out the file size (in bytes) of each file. Use a stack instead of a queue. Repeat using recursion and name your program DirectoryR. java. Modify DirectoryR. java so that it prints out each subdirectory and its total size. The size of a directory is equal to the sum of all of the files it contains or that its subdirectories contain. Stack max. Create a data structure that efficiently supports the stack operations (pop and push) and also return the maximum element. Assume the elements are integers or reals so that you can compare them. Hint: use two stacks, one to store all of the elements and a second stack to store the maximums. Tag systems. Write a program that reads in a binary string from the command line and applies the following (00, 1101) tag-system: if the first bit is 0, delete the first three bits and append 00 if the first bit is 1, delete the first three bits and append 1101. Repeat as long as the string has at least 3 bits. Try to determine whether the following inputs will halt or go into an infinite loop: 10010, 100100100100100100. Use a queue. Set of integers. Create a data type that represents a set of integers (no duplicates) between 0 and n-1. Support add(i), exists(i), remove(i), size(), intersect, difference, symmetricDifference, union, isSubset, isSuperSet, and isDisjointFrom. Indexing a book. Write a program that reads in a text file from standard input and compiles an alphabetical index of which words appear on which lines, as in the following input. Ignore case and punctuation. Similar to FrequencyCount, but for each word maintain a list of location on which it appears. Copy constructor for a resizing array implementation of a stack. Add a copy constructor to ArrayStackOfStrings. java Last modified on August 02, 2016. Copyright copy 2000ndash2016 Robert Sedgewick and Kevin Wayne. All rights reserved. Produce A Moving Average From A Queue(of MyDataClass) I have a scientific datalogging program which I have been developing for a number of years now. We now need to add some functionality so that it produces a moving average of the data being gathered. I can create a queue of myDataClass to do the fifo buffer but I was wondering what the best way doing the averaging might be. As you can see from the code example below myDataClass contains various data structures some of which can be averaged and some which cannot (e. g. the string). I039m working on a function to return a exponential average and there are a lot of examples of exponential moving averages but they all start with a moving average that is just the mean as a lead in to calculating the continuing moving average. I needed just a exponential average of a value set. After Googling my Bing off I still haven039t seen anything so here is my attempt at a basic exponential average. Is this correct Are there any errors I have seen some text about adding a smoothing value to change the curve of the exponential average but not how that would be implemented. I am looking for a way to find the moving average for customers over a 30 day period. However I was not able to find any sample VB code to help get me started. I did find this C sample on Code Project but my attempts at conversion have not been successfull. Does anybody have an existing VB class they would like to share or do you know of a sample that I could use to build my own I want to include an average in a column where the average ignores zero values in a report cell where the column may have I want 16, not 11 so (17 19 12 13 19) / 5 not (17 19 0 0 12 13 19) / 7 Something like this if it would work. SUM(Fieldsfieldname. Value) / Count(iif(Fieldscountcycleperhour. Value gt 0,Fieldsfieldname. Value,0)) Essentially just average everything in the column NOT a zero I put comments on the average output since I kept getting error messages about that. My out keeps saying: Maximum value: 33 Minimum value: 33 what am I doing wrong Option Explicit On Option Strict On I039m in a computer science class, and we are writing simple programs using Visual Basic 2008. I am really inept when it comes to this, as I have never done it before. I need to write a program that: quotAsks the user for 5 numbers and computes the average. It then displays the average with an appropriate message before the average. quot I have been really close with this, but I can039t get the numbers to add up, then divide by 5, and display a pop up message. I have a form that has a queue and i want to transfer that queue to another queue in another form. however when i try to use the elements in the second queue after transfer, I get the error message queue emptybelow is my code First Form Imports System. Collections. Generic Public Class Form1 Private mPerformanceCounter As New System. Diagnostics. PerformanceCounter( quotProcessorquot, quot Processor Timequot, quotTotalquot) I have an array that I039m basically treating like a queue (FIFO)I039m trying to decide the fastest way to implement this. Currently I039m just iterating through and shifting everything up an element and placing the new data 0. This was fine when I was dealing with 1000 element arrays, but now I039m moving up to 100k element arrays and it039s stalling my code. It has been useful to have the data in array form because I039m using the array. sort method and a few other statistical modifications that use the element number (of the sorted list) to work. I039m not sure if VB lists are (like Java) pointer based, and if so I think that shifting pointers would execute faster than my current approach. My question is, if I did move to a list would it a) be faster, and b) is there a way to call a quick sort from the list classIf the execution time is the same for the array vs. list is there a better way to make a FIFO structure in VB how quotpeekquot really operates or something but what I039m trying to do is have 2 separate audio files play one after the other over and over again. I was expecting that I would hear wav1 and wav2 alternate but I only hear wav1 on each cycle. Doesn039t peek use the first data then push it to the back without discarding itTherefore wav2 would be next in line to be played code Has anyone seen a email queue I want to be able to specify the SMTP server to send via, report problems and retry emails if necessary or requested. 039I am having trouble with the line quotsenda suba(sendaobj, EventArgs. Empty)quot. code. Sub DestroyUser(ByRef Victomcheck As Integer, ByRef Victorcheck As Integer) Dim num As Object WriteSub(quotdestroyuserquot) i am making a hairstyle and makeup software in vb and i need to upload the picture which will be edited, to put a hairstyle and makeup on. ive no idea how i can do it. it is a virtual makeover software and i need to produce the before and after images. please someone help me, my deadline is on the 31st How can I clear the printer queue from VB if I was doing it manually I would stop spooler service, empty the windowssystem32spoolprinters folder and restart the service What is the difference between a queue(of t) and list(of t) I039ve been working a lot with list(of t), but up until recently I haven039t even heard of queue(of t). I know that they are both general list. I am currently creating a FTPWebrequest to handle my uploading (the webrequest section of my function is below). At the moment my code loops through this webrequest section for each file - giving the file path of each file in the string quotCompleteLocalPathquot. For each file it creates a webrequest and giving the required file path, uploading the file using a file stream, and then closing the stream. This works, but seems to take quite a long time. Can you recommend a more efficient way Perhaps by using one webrequest but modifying the upload path I have a program that is using API039s to send mouse events and keyboard events to another application that is running. I need to know how to tell if there are any messages left to process for that window after I have click on a button or moved to the next field. I need to know this so I don039t send any more mouse or keyboard events until it has finishing processing everything in its message queue. An example is that I click out of the key field and the form has to go out and read a client record. This may take a second or two, so I need to wait until the form is ready for more input. The below code (VB 2008) will check the print queue every milisecond for a job. It will then show the pagecount in a text box. It works great when im printing to a local printer, but As soon as I change my pc default printer to a network printer, I cant capture any data. I039m looking for a way to move a printjob from a paused printer to another printer. I have looked at the new name space System. printing in framework 3.X. Is there a way to do it in An externa application creates a printjob. I catch the event quota printjob addquot in the printqueue. I pause the printjob. Now I want to move the printjob to another printerIs there a way to do it in Say I have a rolling collection of values where I specify the size of the collection and any time a new value is added, any old values beyond this specified size are dropped off. Obviously (and I039ve tested this) the best type of collection to use for this behavior is a Queue: myQueue. Enqueue(newValue) If myQueue. Count gt specifiedSize Then myQueue. Dequeue() We have made code for writing to and from a IBM message queue. Writin goes well, but reading gives an error, see bold text Are the following 2 SQL statements the same Will they produce the same results sql1 quotSELECT FROM StudentDetials WHERE (Subject1 LIKE 039quot amp Subject(0) amp quot039 OR Subject2 LIKE 039quot amp Subject(0) amp quot039) AND (Day1 LIKE 039quot amp TabDay amp quot039 OR Day2 LIKE 039quot amp TabDay amp quot039) AND (Time1 gt 039quot amp Time(0) amp quot039 AND ETime1 lt 039quot amp Time(1) amp quot039 OR Time2 gt 039quot amp Time(0) amp quot039 AND ETime2 lt 039quot amp Time(1) amp quot039)quot sql1 quotSELECT FROM StudentDetials WHERE (Subject1 LIKE 039quot amp Subject(0) amp quot039 AND Day1 LIKE 039quot amp TabDay amp quot039 AND Time1 gt 039quot amp Time(0) amp quot039 AND ETime1 lt 039quot amp Time(1) amp quot039) OR (Subject2 LIKE 039quot amp Subject(0) amp quot039 AND Day2 LIKE 039quot amp TabDay amp quot039 AND Time2 gt 039quot amp Time(0) amp quot039 AND ETime2 lt 039quot amp Time(1) amp quot039)quot In my case they simply produce the same results but that039s because of the data i039m using. I tried to convert following C code into VB and got quotExpression does not produce a valuequot error while compiling the code return Fluently. Configure().Mappings(m gt m. FluentMappings. AddFromAssemblyOfltMyEntityMappinggt()).Database(SQLiteConfiguration. Standard. InMemory().ShowSql()).ExposeConfiguration(x gt new SchemaExport(x).Execute(false, true, false)).BuildSessionFactory() Return Fluently. Configure().Mappings(Function(m) m. FluentMappings. AddFromAssemblyOf(Of SubscriptionMap)()).Database(SQLiteConfiguration. Standard. InMemory().ShowSql()).ExposeConfiguration(Function(x) New SchemaExport(x).Execute(False, True, False)).BuildSessionFactory() The error happens on 2nd last line of VB code, while C code is compiled without problem. What is wrong with the converting I tried to convert following C code into VB and got quotExpression does not produce a valuequot error while compiling the code I am porting over some code from (vb) to php and I came across some md5 hashing that I can039t reproduce in php. In the one there are two functions one uses UTF-8 encoding and the other uses Unicode encoding. The output is a different hash when passed in a string // First function (returns GUID) Dim oHasher As Cryptography. MD5 Cryptography. MD5.Create() Dim oEncoder As New System. Text. UTF8Encoding() Dim csData() As Byte but they both produce the same result. Is it possible to produce the same results in php with md5 hashing I039m using the below code to produce a ToolTip for each row of a ListView. When moving vertically across the ListView a ToolTip will appear when the mouse touches between two rows - bypassing any of the ToolTip039s options. Private mHoveredItem As ListViewItem Private Sub ListView1MouseMove(ByVal sender As Object, ByVal e As System. Windows. Forms. MouseEventArgs) Handles lv. MouseMove I039m not using the ShowItemToolTips property of the ListView because I want to have a more formatted ToolTip (ToolTipIcon, Title etc) I don039t believe these options can be set for the ListViews ToolTip I039ve updloaded a sample project of the issue here: URL. I have created an program that can produce an XML file from the SQL database. and the code is looks like below: why is there a ltNewDataSetgtlt/NewDataSetgt node2. How to remove that node I am now looking for a way to produce pdf files from xls files. Since the completed programme will be distributed to others, it would have to work on environment without the quotpdf producerquot I am using. Which is the quotpdf producerquot to usequotI am now working on the express version of VB 2005 (which does not have crystal report). I have acrobat 8.0 installed but have not figured out how to do that.