<jupyter_start><jupyter_text>Listas linearesA lista linear é uma forma de representação, como estrutura linear, onde o objetivo é que a representação de dados de um problema no computador seja de tal maneira, que o algoritmo que os utilize seja auxiliado em sua tarefa de obter uma solução de forma confiável e eficiente.Para a compreensão do funcionamento da lista, é necessário compreendermos o funcionamento da memória do computador.A memória do computador é um recurso que pode ser acessado de duas formas por um programa:	* Primeiro, um algoritmo pode alocar estruturas de dados no que chamaremos de memória estática, alocação esta  que deve ser feita antes de sua execução;	* Segundo, um algoritmo pode utilizar-se da memória dinâmica do computador, alocando estruturas na medida do necessário durante a execução do algoritmo.Em ambos os casos, podemos imaginar que a memória é organizada como uma série sequencial de células. Associados a cada célula estão dois atributos: o endereço do início da célula e seu tamanho. As células não precisam ser de tamanho uniforme.O tamanho de uma célula é dado numa unidade peculiar ao equipamento em questão, mas geralmente a unidade fundamental é o byte, que é o espaço necessário para representar um caractere, por exemplo a letra “a”. Um byte é composto de 8 bits, sendo que um bit é um digito binário (0 ou 1). Tudo que é representável num computador é fundamental uma seqüência de bits.A maioria dos programadores está acostumada a trabalhar com a alocação estática de memória, que nos obriga a definir com antecedência o tamanho máximo das estruturas de dados. A segunda forma nos desobriga dessa definição e, portanto, é muito mais flexível, embora esteja sujeita a perigos que lhe são característicos.<jupyter_code>from estruturas.pilha import *
from estruturas.fila import *
from estruturas.deque import *

from estruturas.pilha_dinamica import *
from estruturas.fila_dinamica import *
from estruturas.deque_dinamico import *

from estruturas.lista import *<jupyter_output><empty_output><jupyter_text>Pilhas Listas lineares em que inserções, remoções e acessos a elementos ocorrem no primeiro ou no último elemento são muito frequentemente encontradas. Tais listas linears recebem nomes especiais como pilha e fila. É uma lista linear em que todas as inserções e remoções sãofeitas numa mesma extremidade da lista linear. Esta extremidade se denomina topo (em inglês “top”) ou lado aberto da pilha. As operações definidas para uma pilha incluem: * Verificar se a pilha está vazia* Inserir um elemento na pilha (empilhar ou “push”), no lado do topo.* Remover um elemento da pilha (desempilhar ou “pop”), do lado do topo.* Esvaziar a pilha (clear) Pilha é uma estrutura LIFOComo o último elemento que entrou na pilha será o primeiro asair da pilha, a pilha é conhecida como uma estrutura do tipo LIFO(“Last In First Out”). Exemplos:* Na vida real: pilhas de pratos numa cafeteria (acréscimos e retiradas de pratos sempre feitos num mesmo lado da pilha - lado de cima)* Na execução de uma programa: uma pilha pode ser usadana chamada de procedimentos, para armazenar o endereço de retorno (e os parâmetros reais). A medidaque procedimentos chamam outros procedimentos, mais emais endereços de retorno devem ser empilhados. Estes são desempilhados à medida que os procedimentos chegam ao seu fim.* Na avaliação de expressões aritméticas, a pilha pode ser usada para transformar expressões em notação polonesa ou pós-fixa. A pilha também pode ser usada na avaliaçãode expressões aritméticas em notação polonesa. Pilha EstásticaOs elementos da lista linear ocupam posições consecutivas da memória do computador, com tamanho fixo. Área de memória é alocada no momento da execução.Abaixo mostraremos uma série de testes realizadas com a estrutura de pilha estática criada. Por ser estática, há uma limitação de tamanho definida ao instanciar a estrutura. Ao atingirmos este limite, a pilha deixa de permitir novas inserções até que haja espaço.<jupyter_code>def main():
    pilha = Pilha(10)
    pilha.push("Paulo")
    pilha.push("Ana")
    pilha.push("Maria")
    pilha.push("Gabriela")
    pilha.push("Pedro")
    pilha.push("Renata")
    pilha.push("João")
    pilha.push("Sergio")
    pilha.push("Ricardo")
    pilha.push("Bruno")
    pilha.push("Angela")
    pilha.mostra()
    print(pilha.tamanho)
    print(pilha.topo)
    pilha.pop()
    pilha.mostra()
    pilha.push("Angela")
    pilha.mostra()
    pilha.push("Angela")
    print(pilha.peek())
    
if __name__ == "__main__":
    main()<jupyter_output>Estouro de pilha
['Paulo', 'Ana', 'Maria', 'Gabriela', 'Pedro', 'Renata', 'João', 'Sergio', 'Ricardo', 'Bruno']
10
9
['Paulo', 'Ana', 'Maria', 'Gabriela', 'Pedro', 'Renata', 'João', 'Sergio', 'Ricardo']
['Paulo', 'Ana', 'Maria', 'Gabriela', 'Pedro', 'Renata', 'João', 'Sergio', 'Ricardo', 'Angela']
Estouro de pilha
Angela<jupyter_text>FilasÉ uma lista linear em que todas as inserções de novos elementos são realizadas numa extremidade da lista e todas as remoções são feitas na outra extremidade. Uma fila é uma estrutura do tipo FIFO (“First In First Out”).Elementos novos são inseridos no lado In(fim da fila) e a retirada ocorre no lado Out (frente ou começo da fila). Exemplo: Num sistema operacional, os processos prontos para entrar em execução (aguardando apenas a disponibilidade da CPU) são geralmente mantidos numa fila.Existe um tipo de fila em que as retiradas de elementos da fila depende de um valor chamado prioridade de cada elemento. O elemento de maior prioridade entre todos os elementos da fila é o próximo a ser retirado. Tal fila recebe o nome de fila de prioridade.<jupyter_code>def main():
    fila = Fila(10)
    fila.insere("Paulo")
    fila.insere("Ana")
    fila.insere("Maria")
    fila.insere("Gabriela")
    fila.insere("Pedro")
    fila.insere("Renata")
    fila.insere("João")
    fila.insere("Sergio")
    fila.insere("Ricardo")
    fila.insere("Bruno")
    fila.insere("Angela")
    fila.mostra()
    print(fila.get_tamanho())
    fila.remove()
    fila.mostra()
    fila.insere("Angela")
    fila.mostra()
    fila.insere("Fernanda")
    print(fila.peek())
    
if __name__ == "__main__":
    main()<jupyter_output>Estouro de fila
['Paulo', 'Ana', 'Maria', 'Gabriela', 'Pedro', 'Renata', 'João', 'Sergio', 'Ricardo', 'Bruno']
10
['Ana', 'Maria', 'Gabriela', 'Pedro', 'Renata', 'João', 'Sergio', 'Ricardo', 'Bruno']
['Ana', 'Maria', 'Gabriela', 'Pedro', 'Renata', 'João', 'Sergio', 'Ricardo', 'Bruno', 'Angela']
Estouro de fila
Ana<jupyter_text>Deque Estático<jupyter_code>def main():
    lista = Deque(10)
    lista.insere_esq("Paulo")
    lista.insere_esq("Ana")
    lista.insere_dir("Maria")
    lista.insere_dir("Gabriela")
    lista.insere_esq("Pedro")
    lista.insere_dir("Renata")
    lista.insere_esq("João")
    lista.insere_dir("Sergio")
    lista.insere_esq("Ricardo")
    lista.insere_dir("Bruno")
    lista.insere_esq("Angela")
    lista.mostra()
    print(lista.get_tamanho())
    lista.remove_esq()
    lista.mostra()
    lista.remove_dir()
    lista.mostra()
    #lista.insere_dir("José")
    #lista.mostra()
    #lista.insere_esq("Fernanda")
    
if __name__ == "__main__":
    main()<jupyter_output>Deque cheio
['Ricardo', 'João', 'Pedro', 'Ana', 'Paulo', 'Maria', 'Gabriela', 'Renata', 'Sergio', 'Bruno']
10
['João', 'Pedro', 'Ana', 'Paulo', 'Maria', 'Gabriela', 'Renata', 'Sergio', 'Bruno']
['João', 'Pedro', 'Ana', 'Paulo', 'Maria', 'Gabriela', 'Renata', 'Sergio']<jupyter_text>Listas dinâmicasNeste caso, o espaço de memória é alocado em tempo de execução. Uma lista com alocação dinâmica cresce à medida que novos elementos precisam ser armazenados (e diminui à medida que elementos anteriormente armazenados são retirados da lista) Pilha dinâmica<jupyter_code>def main():
    pilha = PilhaDinamica()
    pilha.push("Paulo")
    pilha.push("Ana")
    pilha.push("Maria")
    pilha.push("Gabriela")
    pilha.push("Pedro")
    pilha.push("Renata")
    pilha.push("João")
    pilha.push("Sergio")
    pilha.push("Ricardo")
    pilha.push("Bruno")
    pilha.push("Angela")
    pilha.mostra()
    #print(pilha.tamanho)
    #print(pilha.topo)
    print(str(pilha.pop().conteudo))
    pilha.mostra()
    pilha.pop()
    pilha.mostra()
    pilha.push("Angela")
    pilha.mostra()
    pilha.push("Angela")
    print(pilha.peek())
    
if __name__ == "__main__":
    main()<jupyter_output>Paulo >> Ana >> Maria >> Gabriela >> Pedro >> Renata >> João >> Sergio >> Ricardo >> Bruno >> Angela
Angela
Paulo >> Ana >> Maria >> Gabriela >> Pedro >> Renata >> João >> Sergio >> Ricardo >> Bruno
Paulo >> Ana >> Maria >> Gabriela >> Pedro >> Renata >> João >> Sergio >> Ricardo
Paulo >> Ana >> Maria >> Gabriela >> Pedro >> Renata >> João >> Sergio >> Ricardo >> Angela
Angela<jupyter_text>Fila dinâmica<jupyter_code>def main():
    fila = FilaDinamica()
    fila.insere("Paulo")
    fila.insere("Ana")
    fila.insere("Maria")
    fila.insere("Gabriela")
    fila.insere("Pedro")
    fila.insere("Renata")
    fila.insere("João")
    fila.insere("Sergio")
    fila.insere("Ricardo")
    fila.insere("Bruno")
    fila.insere("Angela")
    fila.mostra()
    print(fila.get_tamanho())
    print(fila.remove().conteudo)
    fila.mostra()
    fila.insere("Angela")
    fila.mostra()
    fila.insere("Fernanda")
    print(fila.peek())
    
if __name__ == "__main__":
    main()<jupyter_output>Angela >> Bruno >> Ricardo >> Sergio >> João >> Renata >> Pedro >> Gabriela >> Maria >> Ana >> Paulo
11
Paulo
Angela >> Bruno >> Ricardo >> Sergio >> João >> Renata >> Pedro >> Gabriela >> Maria >> Ana
Angela >> Angela >> Bruno >> Ricardo >> Sergio >> João >> Renata >> Pedro >> Gabriela >> Maria >> Ana
Ana<jupyter_text>AtividadeImplemente um deque dinâmico. Instruções:É uma estrutura de dados na qual os elementos podem ser inseridos ou excluídos de qualquer umade suas extremidades (do início ou do fim).* Use uma implementação duplamente ligada (ou duplamente encadeada), na qual cada elemento possui o endereço de seu antecessor e de seu sucessor.* Use um nó cabeça para facilitar o gerenciamentoda estrutura.Temos um ponteiro para o nó cabeça Cada elemento indica seu antecessor e seu sucessor (o último tem o nó cabeça como sucessor e o nó cabeça tem o último como antecessor).![Esquema do Deque](img/deque.png) Funções a serem implementadas: * Inicializar a estrutura* Retornar a quantidade de elementos válidos* Exibir os elementos da estrutura* Inserir elementos na estrutura (duas funções, uma para cada ponta)* Excluir elementos da estrutura (duas funções, uma para cada ponta)* Reinicializar a estruturaTeste abaixo sua estrutura<jupyter_code>https://github.com/VanessaSilva99/EstruturaDeDados2/tree/main/Lab03/Lab02/Deque<jupyter_output>José >> Ana >> Maria<jupyter_text>Lista encadeadaConstruiremos agora uma estrutura genérica, sem restrições para a inserção, consulta ou remoção de elementos. Nossa lista linear também não terá restrições de tamanho.<jupyter_code>def main():
    lista = Lista()
    lista.insere_esq("Paulo")
    lista.insere_esq("Ana")
    lista.insere_dir("Maria")
    lista.insere_dir("Gabriela")
    lista.insere_esq("Pedro")
    lista.insere_dir("Renata")
    lista.insere_esq("João")
    lista.insere_dir("Sergio")
    lista.insere_esq("Ricardo")
    lista.insere_dir("Bruno")
    lista.insere_esq("Angela")
    lista.mostra()
    print(lista.get_tamanho())
    lista.remove_esq()
    lista.mostra()
    lista.remove_dir()
    lista.mostra()
    print(lista.pesquisa("Renato"))
    #lista.insere_dir("José")
    #lista.mostra()
    #lista.insere_esq("Fernanda")
    
if __name__ == "__main__":
    main()<jupyter_output>Angela >> Ricardo >> João >> Pedro >> Ana >> Paulo >> Maria >> Gabriela >> Renata >> Sergio >> Bruno
11
Ricardo >> João >> Pedro >> Ana >> Paulo >> Maria >> Gabriela >> Renata >> Sergio >> Bruno
Ricardo >> João >> Pedro >> Ana >> Paulo >> Maria >> Gabriela >> Renata >> Sergio
Elemento não encontrado<jupyter_text>Remoção por índiceImplemente a função para remover um elemento em uma dada posição na lista. No arquivo lista.py, codifique a função def remove(self, elemento, posicao).Teste sua removendo o item de índice 4 na lista instanciada acima (Paulo):<jupyter_code>https://github.com/VanessaSilva99/EstruturaDeDados2/tree/main/Lab03/Lab02/Deque/listas_encadeadas<jupyter_output><empty_output><jupyter_text>Ordenação simplesImplemente a função para ordenar a lista. No arquivo lista.py, codifique a função def ordena(self). Utilize a estratégia que preferir.Teste seu algoritmo ordenando a lista instanciada:<jupyter_code>https://github.com/VanessaSilva99/EstruturaDeDados2/tree/main/Lab03/Lab02/Deque/listas_encadeadas<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.10884621438690383, 'fraction_numerical': 0.0033055249488430664, 'mean_word_length': 4.600264433671221, 'pattern_counts': {'":': 6, '<': 34, '<?xml version=': 0, '>': 222, 'https://': 3, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '10', 'dir': 'jupyter-structured-clean-dedup', 'id': '231299', 'license': 'MIT', 'n_tokens_mistral': 4682, 'n_tokens_neox': 4651, 'n_words': 1370, 'path': 'lab01.ipynb', 'repo_name': 'VanessaSilva99/EstruturaDeDados2', 'size': '12706'}