Stacks (Pilhas) em JavaScript

Stack (Pilha) é uma estrutura de dados abstrata que respeita a regra LIFO (Last In, First Out), em português Último Dentro, Primeiro Fora.

Stacks fazem parte das estruturas de dados lineares juntamente com: Array, Linked List, Queue

As Stacks podem ser implementadas usando:

• Array
• Linked List

Neste artigo veremos a implementação de Stack usando Array.

Exemplo gráfico:

PROPRIEDADES DE UMA STACK:

• Tail: corresponde ao índice do último elemento da pilha (no caso de uma pilha vazia, o seu valor é -1)
• Size: corresponde ao tamanho da pilha(valor estáticamente definido na criação da mesma)

MÉTODOS DE UMA STACK:

• Push: método para adicionar elementos na pilha
• Pop: método para remover elementos da pilha
• Peek: método para mostrar o último elemento da pilha
• IsEmpty: método que informa se a pilha está vazia
• IsFull: método que informa se a pilha está cheia
• DeleteStack: método para apagar uma pilha

Criando uma Stack

Criaremos uma pilha e nela adicionaremos os números 100, 200, 300.

Adicionando elementos na Stack

A adição de novos elementos numa stack é sempre feita no final da mesma(no primeiro espaço livre), os elementos são adicionados um de cada vez.

Removendo elementos da Stack

A remoção de elementos é sempre feita no topo da pilha, ou seja, a partir do último elemento da mesma.

Chega de bla bla bla, e vejamos como implementar uma Stack usando o JavaScript

Criando a Stack

class Stack {
  constructor(size) {
    this.stack = new Array(size);
    this.size = size;
    this.tail = -1;
  }
}

let pilha = new Stack(3);

No código acima, fizemos a criação de uma pilha que irá armazenar três elementos, logo a seguir inicializamos a pilha e atribuimos-na à varíavel pilha que usaremos para referências posteriores.

Verificando se a Stack está completa

class Stack {
  // código anterior ocultado aqui
  isFull() {
    return this.size - 1 === this.tail;
  }
}

A propriadade tail contém o indíce do último elemento da pilha, no nosso caso, a pilha é de tamanho 3. A contagem do valor de tail começa do indíce 0, isto quer dizer que, para uma pilha de 3 elementos, o valor de tail será 2(0 = 100, 1 = 200, 2 = 300), no entanto:

size = 3 - 1
size(2) === tail(2)

Neste caso, a comparação do valor das duas propriedades resultará em true caso elas sejam iguais.

Adicionando elementos na Stack

class Stack {
  // códigos anteriores ocultados aqui
  push(elemento) {
    if (this.isFull()) {
      return "Pilha cheia, a adição de novos elementos não é possivel";
    } else {
      this.tail++;
      this.stack[this.tail] = elemento;
      return `O valor ${elemento} foi adicionado à pilha`;
    }
  }
}

No código acima, antes de efectuarmos a adição de um novo elemento à pilha, primeiro verificamos se a mesma encontra-se cheia, caso esteja, a operação não é efectuada. Caso ainda haja espaço na pilha, a operação é efectuada, e de seguida incrementamos o valor de tail para que aponte para o último elemento adicionado.

Adicionando os números à pilha:

pilha.push(100); // O valor 100 foi adicionado à pilha
pilha.push(200); // O valor 200 foi adicionado à pilha
pilha.push(300); // O valor 300 foi adicionado à pilha

Imprimindo o último elemento da Stack

class Stack {
  // códigos anteriores ocultados aqui
  if(this.isEmpty()) {
    return "A pilha está vazia"
  } else {
    return this.stack[this.tail];
  }
}

pilha.peek(); // 300

Ao imprimirmos o último elemendo da pilha, como esperado, o valor retornado é o número 300

Verificando se a Stack está vazia

class Stack {
  // códigos anteriores ocultados aqui
  isEmpty() {
    return this.tail === -1;
  }
}

Sempre que uma pilha é criada, o valor de tail é definido à -1. Para verificarmos se a pilha está vazia só temos de comparar se o valor de tail é igual à -1.

Removendo elementos da Stack

class Stack {
  // códigos anteriores ocultados aqui
  pop() {
    if (this.isEmpty()) {
      return "Pilha vazia, a sua operação não foi efectuada";
    } else {
      let elemento = this.stack[this.tail];
      this.stack[this.tail] = undefined;
      this.tail--;
      return `O valor ${elemento} foi removido da pilha`;
    }
  }
}

pilha.pop(); // O valor 300 foi removido da pilha

pilha.peek();

Depois efectuarmos a operação de remoção do último elemento da pilha e imprirmos o valor do último elemento actualizado, nos é retornado o número 200 pois o 300 foi removido.