Pilhas (stacks): o que são, como funcionam e exemplos práticos

Texto de: Marlliton Souza

Pilha

Uma pilha, no contexto da ciência da computação, é uma estrutura de dados que segue o princípio de Last In, First Out (LIFO), o que significa que o último elemento adicionado é o primeiro a ser removido.

Em uma pilha da realidade, como uma pilha de pratos ou de livros, o conceito básico é semelhante ao de uma pilha na computação. Cada novo prato ou livro adicionado à pilha permanece no topo e, quando você remove um item, o último item adicionado é removido primeiro.

As pilhas são amplamente utilizadas em programação para organizar e gerenciar dados de maneira eficiente, sendo essenciais em muitos algoritmos e estruturas de dados. Implementaremos nossa própria pilha usando JavaScript mais adiante.

A figura acima ilustra o funcionamento de uma pilha. Nesse contexto, a operação de adição de um novo elemento no topo da pilha, conhecida como "push", é visualmente representada pelo bloco amarelo, destacando a inserção do elemento mais recente sobre os demais. Da mesma forma, a operação de remoção de um elemento, denominada "pop", é enfatizada no topo da pilha pelo mesmo bloco amarelo, dessa forma, fica claro que o último elemento adicionado é o primeiro a ser removido.

Criando nossa classe stack

Usaremos um array para armazenar os dados da nossa pilha, mas limitaremos os métodos de modo a 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 expressões matemáticas 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:

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

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.

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

• Pilhas – wikipedia
• Como fazer o efeito de máquina de escrever com React.JS