Para que você entenda a estrutura de dados pilhas (stacks) é necessário que você já conheça a estrutura de dados array.

Essa, por sua vez, é amplamente utilizada e oferece uma grande flexibilidade. Os array nos permiti adicionar e remover elementos de qualquer posição.

Porém, às vezes, é importante termos total controle das inserções e remoções, e é aí que as pilhas (stacks) as filas (queues) começam a se destacar.

Pilha

Uma pilha é uma coleção ordenada de dados, e existem diversos exemplos de pilhas na vida real. Por exemplo, uma pilha de pratos em uma pia, ou uma pilha de livros.

Representação de uma pilha

Como visto na imagem acima, as pilhas obedecem ao princípio LIFO (Last In First Out), ou seja, o último a entrar é o primeiro a sair.

Além disso, a pilha realiza todas as inserções e remoções a partir do topo, mantendo os elementos da base inalterados.

Criando nossa classe stack

Usaremos um array para armazenar os dados da nossa pilha, mas limitaremos os métodos afim de respeitar o princípio LIFO, os métodos usados serão:

  • push: esse método adicionará um elemento a pilha.
  • pop: esse método removerá um elemento da pilha.
  • peek: esse método dará uma “olhadinha” no topo da pilha e nos devolverá o elemento que está lá.
  • isEmpty: esse método verifica se a pilha está vazia.
  • size: esse método devolve o tamanho da pilha.
export class Stack {
  constructor(private _items: Array<any> = []) {}

  push(item: any) {
    this._items.push(item)
  }

  pop() {
    this._items.pop()
  }

  peek() {
    return this._items[this._items.length - 1]
  }

  isEmpty() {
    return this._items.length === 0
  }

  size() {
    return this._items.length
  }
}

Usando a classe stack

De antemão, quero dizer que resolveremos um problema real relacionado a matemática usando essa classe mais adiante.

Por agora só veremos o funcionamento básico da classe. Então, chamaremos cada um dos métodos para conferir se estão funcionando como esperado:

Executando uma classe pilhas

Para ficar mais claro o funcionamento da pilha veja a imagem abaixo:

Funcionamento de uma pilha

Na imagem acima, podemos observar todas as operações de push que executamos, onde colocamos cada elemento adicionado no topo da pilha.

Da mesma maneira, sempre selecionamos o elemento do topo como o próximo a ser removido, até que não haja mais elementos restantes.

Resolvendo problemas com stack

O problema que vamos resolver é a verificação de parênteses balanceados em uma expressão matemática.

Suponha que você tenha uma expressão matemática que contém parênteses, como, por exemplo: 

((2 * 3) + 4) / (5 - 1)

Para avaliar essa expressão corretamente, é necessário que os parênteses estejam balanceados, ou seja, que para cada parêntese de abertura haja um parêntese de fechamento correspondente.

As pilhas são ótimas estruturas de dados para resolver esse problema, vamos pensar um pouco na lógica:

  1. Precisamos criar uma pilha vazia.
  2. Para cada caractere na expressão:
    • Se o caractere for um parêntese de abertura, empilharemos ele na pilha.
    • Se o caractere for um parêntese de fechamento:
      • Se a pilha estiver vazia, significa que a expressão não está balanceada, retornaremos false.
      • Caso contrário removeremos o caractere do topo da pilha.
      • Se o caractere desempilhado não for o parêntese correspondente ao fechamento, a expressão não está balanceada, retornaremos false.
  3. Se a pilha estiver vazia ao final da expressão, a expressão está balanceada, retornaremos true. Caso contrário, retornaremos false.

Vamos ao código

import { Stack } from "./stack/index.ts";

class CheckBalancedParentheses {
  private _stack: Stack;
  private _openingBrackets: string[];
  private _closingBrackets: string[];

  constructor(private _expression: string) {
    this._stack = new Stack();
    this._openingBrackets = ["(", "[", "{"];
    this._closingBrackets = [")", "]", "}"];
  }

  exec() {
    for (const char of this._expression) {

      if (this._openingBrackets.includes(char)) {
        this._stack.push(char);
      } else if (this._closingBrackets.includes(char)) {
        const indexCloseBracket = this._closingBrackets.indexOf(char);

        if (this._stack.isEmpty() || this._stack.pop() !== this._openingBrackets[indexCloseBracket]) {
          return false;
        }
      }
    }

    return this._stack.isEmpty();
  }
}

const result = new CheckBalancedParentheses("((2 * 3) + 4");
console.log(`A expressão ${result.exec() ? "está balanceada" : "não está balanceada"}`);

O código acima, analisa uma expressão matemática e se tiver balanceada ele retorna true, caso contrário false.

Testando a estrutura de dados pilhas

Entendendo os pontos mais importantes do código

  1. O construtor da classe CheckBalancedParentheses recebe uma expressão matemática como parâmetro e, em seguida, inicializa a pilha _stack e os arrays de parênteses _openingBrackets e _closingBrackets.
  2. O método exec() é responsável por executar a verificação. Ele itera por cada caractere da expressão.
  3. Durante a iteração, se o caractere atual for um parêntese de abertura, ele é adicionado à pilha _stack.
  4. Por outro lado, se o caractere atual for um parêntese de fechamento, o código realiza uma verificação. Ele verifica se a pilha está vazia ou se o parêntese de abertura correspondente ao parêntese de fechamento atual não está no topo da pilha. Se uma dessas condições for verdadeira, conclui-se que a expressão não está balanceada e o método retorna false.
  5. Após percorrer todos os caracteres da expressão, ocorre uma verificação final. Nesse momento, é verificado se a pilha está vazia. Se a pilha estiver vazia, concluímos que todos os parênteses foram devidamente balanceados na expressão, e o método retorna true. Caso contrário, ou seja, se a pilha não estiver vazia, concluímos que a expressão não está balanceada, e o método retorna false.

Conclusão

Neste artigo, entendemos em detalhes como a estrutura de dados pilha (stack) funciona.

Obrigado por chegar até aqui, um abraço e até a próxima. 👾

Saiba mais