Estruturas de Dados Sequenciais | Typescript

📚 Lib para estruturas de dados sequenciais clássicas

Tabela de Conteúdo

• 1. Sobre
• 2. Pré-requisitos
• 3. Como Utilizar
• 4. Exemplos de Utilização
• 5. Lista Encadeada
• 5.1. Importação
• 5.2. Criação
• 5.3. Inserção no início
• 5.4. Inserção no fim
• 5.5. Recuperação do início
• 5.6. Recuperação do fim
• 5.7. Remoção do início
• 5.8. Remoção do fim
• 5.9. Clonar
• 6. Pilha
• 6.1. Importação
• 6.2. Criação
• 6.3. Inserção
• 6.4. Recuperação
• 6.5. Remoção
• 7. Fila
• 7.1. Importação
• 7.2. Criação
• 7.3. Inserção
• 7.4. Recuperação
• 7.5. Remoção
• 8. Funcionalidades Gerais
• 8.1. Vazio
• 8.2. Tamanho
• 8.3. Contém
• 8.4. Limpar
• 8.5. Iterador
• 8.6. Printar [debug only]
• 9. Customização

1. Sobre

Este repositório tem por objetivo prover uma pequena biblioteca livre escrita em Typescript puro para Estruturas de Dados Sequenciais Clássicas, isto é, para Listas Encadeadas , Pilhas e Filas.

2. Pré-requisitos

Os pré-requisitos para a utilização da biblioteca são mínimos:

• Instalar Typescript Transpiler em sua máquina;
• Possuir um editor de código que suporte Typescript.

3. Como Utilizar

Veja como é simples utilizar esta biblioteca em seu projeto:

• Faça o download/clone desta biblioteca para sua máquina;
• Extraia o diretório "lib/" localizado em "src/lib/" para seu projeto;
• Importe a estrutura de dados que deseja utilizar usando a diretiva "import" do Typescript.

4. Exemplos de Utilização

Cada Estrutura de Dados conta com um exemplo de utilização contido no diretório "src/". Já, para ver o exemplo em funcionamento, abra o respectivo exemplo.html de sua escolha contido no diretório "dist/".

5. Lista Encadeada

Lista Encadeada é uma estrutura de dados linear, composta de nós interligados. Confira a seguir as principais funcionalidades implementadas que caracterizam-a:

5.1. Importação

Para importar a classe LinkedList para seu projeto, utilize a diretiva "import" do Typescript. Por padrão:

import { LinkedList } from "./lib/collection/LinkedList";

5.2. Criação

Para criar uma nova Lista Encadeada, instancie um novo objeto a partir da Classe LinkedList e escolha o tipo de dado que quer armazenar.

Exemplos:

const list = new LinkedList(); //por padrão [any]

const list = new LinkedList<number>(); //para números

const list = new LinkedList<string>(); //para caracteres

5.3. Inserção no início

Para inserir elementos no início da lista, utilize a função addFirst, ou ainda, utilize a função de apelido add.

Exemplos:

list.addFirst(20);
//list.add(20); //alternativa...

list.addFirst('a');
//list.add('a'); //alternativa...

5.4. Inserção no fim

Para inserir elementos no fim da lista, utilize a função addLast.

Exemplos:

list.addLast(20);

list.addLast('z');

5.5. Recuperação do início

Para pegar/recuperar o início da lista, sem removê-lo, utilize a função peekFirst, ou ainda, utilize a função de apelido peek.

Exemplo:

const element = list.peekFirst();
//const element = list.peek(); //alternativa...

5.6. Recuperação do fim

Para pegar/recuperar o fim da lista, sem removê-lo, utilize a função peekFirst, ou ainda, utilize a função de apelido peek.

Exemplo:

const element = list.peekLast();

5.7. Remoção do início

Para remover o início da lista e retorná-lo, utilize a função removeFirst, ou ainda, utilize a função de apelido remove.

Exemplo:

const element = list.removeFirst();
//const element = list.remove();

5.8. Remoção do fim

Para remover o fim da lista e retorná-lo, utilize a função removeLast.

Exemplo:

const element = list.removeLast();

5.9. Clonar

Para clonar todos os elementos de uma lista para uma nova lista, utilize a função **clone**.

Exemplo:

const cloned_list = list.clone();

6. Pilha

Pilha é uma estrutura de dados do tipo LIFO (last-in first-out), onde o último elemento a ser inserido, será o primeiro a ser retirado. Confira a seguir as principais funcionalidades implementadas que caracterizam-a:

6.1. Importação

Para importar a classe Stack para seu projeto, utilize a diretiva "import" do Typescript. Por padrão:

import { Stack } from "./lib/collection/Stack";

6.2. Criação

Para criar uma nova Pilha, instancie um novo objeto a partir da Classe Stack e escolha o tipo de dado que quer armazenar.

Exemplos:

const stack = new Stack(); //por padrão [any]

const stack = new Stack<number>(); //para números

const stack = new Stack<string>(); //para caracteres

6.3. Inserção

Na Pilha, inserções ocorrem sempre no início/topo, para isso, utilize a função push, com uma nova pilha instanciada.

Exemplos:

stack.push(20); //para números

stack.push('a'); //para caracteres

6.4. Recuperação

Para pegar/recuperar o início/topo da Pilha, sem removê-lo, utilize a função peek.

Exemplo:

const element = stack.peek();

6.5. Remoção

Para remover o início/topo da Pilha e retorná-lo, utilize a função pop.

Exemplo:

const element = stack.pop();

7. Fila

Filas são estruturas de dados do tipo FIFO (first-in first-out), onde o primeiro elemento a ser inserido, será o primeiro a ser retirado. Confira a seguir as principais funcionalidades implementadas que caracterizam-a:

7.1. Importação

Para importar a classe Queue para seu projeto, utilize a diretiva "import" do Typescript. Por padrão:

import { Queue } from "./lib/collection/Queue";

7.2. Criação

Para criar uma nova Fila, instancie um novo objeto a partir da Classe Queue e escolha o tipo de dado que quer armazenar.

Exemplos:

const queue = new Queue(); //por padrão [any]

const queue = new Queue<number>(); //para números

const queue = new Queue<string>(); //para caracteres

7.3. Inserção

Na Fila, inserções ocorrem sempre no fim, para isso, utilize a função add, com uma nova fila instanciada.

Exemplos:

queue.add(10); //para números

queue.add('a'); //para caracteres

7.4. Recuperação

Para pegar/recuperar o fim da Fila, sem removê-lo, utilize a função peek.

Exemplo:

const element = queue.peek();

7.5. Remoção

Para remover o início da Fila e retorná-lo, utilize a função remove.

Exemplo:

const element = queue.remove();

8. Funcionalidades Gerais

Além das funcionalidades específicas listadas de cada estrutura de dados apresentada, a estrutura base de todas elas possui funcionalidades padrões, comuns à todas, confira a seguir:

8.1. Vazio

Para verificar se uma estrutura está vazia, utilize a função empty.

Exemplos:

if(list.empty())  console.log("Lista vazia");

if(stack.empty()) console.log("Pilha vazia");

if(queue.empty()) console.log("Fila vazia");

8.2. Tamanho

Para retornar a quantidade de elementos atuais na estrutura, utilize a função size.

Exemplos:

let size = list.size(); //tamanho da lista

let size = stack.size(); //tamanho da pilha

let size = queue.size(); //tamanho da fila

8.3. Contém

Para verificar se um estrutura contém um determinado elemento, utilize a função contains.

Exemplos:

if(list.contains(20))  console.log("Contém 20");

if(stack.contains('+')) console.log("Contém +");

if(queue.contains(1.5)) console.log("contém 1.5");

8.4. Limpar

Para remover todos os elementos de uma estrutura, utilize a função clear.

Exemplos:

list.clear();

stack.clear();

queue.clear();

8.5. Iterador

Para iterar sobre elementos de uma estrutura, utilize o padrão Iterator em conjunto com as funções hasNext e next

Exemplos

const it = list.iterator(); //retorna um Iterator de lista
while(it.hasNext()) //enquanto tiver elementos...
	console.log(it.next()); //printa o elemento

const it = stack.iterator(); //retorna um Iterator de pilha
while(it.hasNext()) //enquanto tiver elementos...
	console.log(it.next()); //printa o elemento

const it = queue.iterator(); //retorna um Iterator de fila
while(it.hasNext()) //enquanto tiver elementos...
	console.log(it.next()); //printa o elemento

8.6. Printar [debug only]

[apenas para debug] Para printar todos os elementos de uma estrutura utilize a função print.

Atenção: Você pode/deve remover esta função em ambiente de produção.

Exemplos:

list.print();

stack.print();

queue.print();

9. Customização

Para implementar sua própria estrutura de dados customizada, você pode estender a classe base abstrata SequentialList ou estender uma das estruturas sequenciais da biblioteca, criando, assim, novas funcionalidades ou especializando funcionalidades já existentes.

Exemplo:

import { SequentialList } from './lib/collection/SequentialList';

export class Queue<E> extends SequentialList<E> {

    constructor() {
        super();
        this.STRUCTURE = 'myCustomSequentialList';
    }
    
	//functions...
	
}