Uma pilha é uma estrutura de dados linear simples que funciona como uma pilha de placas ?️. Segue o princípio Last In, First Out (LIFO). Pense nisso como uma pilha de pratos: você só pode adicionar ou remover pratos do topo da pilha.

Para uma melhor compreensão da pilha, vamos embarcar em uma curta jornada de imaginação?.
Imagine que você está em um restaurante chique ?️, e o pessoal da cozinha está se preparando para uma noite movimentada ?‍?. Na área dos pratos, há uma pilha alta de pratos esperando para serem usados. À medida que os clientes chegam e os pedidos chegam, a equipe pega os pratos do topo da pilha. Quando placas limpas são adicionadas, elas vão direto para cima. Este sistema simples garante que as placas na parte inferior da pilha que estão lá há mais tempo sejam usadas por último, enquanto as placas recém-limpas no topo sejam usadas primeiro ✨.

É assim, em essência, como funciona uma estrutura de dados Stack. Uma pilha é uma estrutura de dados linear que segue o princípio Last In First Out (LIFO). Assim como acontece com nossa pilha de pratos, o último item adicionado a uma pilha é o primeiro a ser removido.

Índice

Neste tutorial abrangente sobre a estrutura de dados da pilha, exploraremos os seguintes tópicos com uma abordagem simples e amigável para iniciantes:

1. O que é uma pilha?
2. Prós e contras do uso do Stack
3. Aplicações de pilhas no mundo real
4. Operações principais em uma pilha
5. Implementação de pilha em JavaScript
6. Conclusão

Você está pronto? Vamos mergulhar

O que é uma pilha?

Uma pilha é uma estrutura de dados linear que segue o princípio Last In, First Out (LIFO). Isso significa que o último elemento adicionado à pilha será o primeiro a ser removido. Pense nisso como uma pilha de livros: você só pode adicionar ou remover livros do topo da pilha.

Prós e contras do uso do Stack

Antes de continuarmos com o fluxo e escrevermos alguns códigos, é ótimo entender onde e onde não usar o Stack. A tabela abaixo fornece detalhes explícitos dos prós e contras do Stack.

Principais operações em uma pilha

As operações fundamentais que podem ser realizadas em uma pilha são:

1. push(): Adiciona um elemento ao topo da pilha.
2. pop(): Remove o elemento superior da pilha.
3. peek(): Retorna o elemento superior da pilha sem removê-lo.
4. isEmpty(): Verifica se a pilha está vazia.
5. size(): Retorna o número de elementos na pilha.

Aplicações de pilhas no mundo real

As pilhas estão por toda parte na ciência da computação e no desenvolvimento de software. Aqui estão algumas aplicações comuns:

1. Funcionalidade de desfazer: Em editores de texto ou software de design gráfico, cada ação é colocada em uma pilha. Quando você clica em "desfazer", a ação mais recente é retirada da pilha e revertida.

2. Histórico do navegador: quando você visita uma nova página, ela é colocada em uma pilha. O botão "voltar" retira a página atual da pilha, revelando a anterior.

3. Pilha de chamadas de função: Em linguagens de programação, as chamadas de função são gerenciadas usando uma pilha. Quando uma função é chamada, ela é colocada na pilha de chamadas. Quando ele retorna, ele se solta.

4. Avaliação de expressão: Pilhas são usadas para avaliar expressões aritméticas, especialmente aquelas em notação pós-fixada.

5. Algoritmos de retrocesso: Em problemas como resolução de labirintos ou quebra-cabeças, as pilhas podem acompanhar o caminho percorrido, permitindo fácil retrocesso quando necessário.

Implementação de pilha em JavaScript

Agora, vamos implementar uma pilha em JavaScript. É importante saber que existem diferentes maneiras de implementar uma pilha em JavaScript. Uma das maneiras comuns de implementar uma pilha é usando array, outra maneira é usar lista vinculada. Neste artigo, implementaremos uma pilha usando lista vinculada (lista vinculada individualmente).

Implementar pilha usando lista vinculada

Espero que você ainda se lembre de como funciona a lista vinculada. Talvez seja necessário verificar a implementação da lista vinculada em um de nossos artigos anteriores desta mesma série.

Como implementar uma lista vinculada individualmente em JavaScript

A grande solução? ・ 4 de outubro

#javascript #iniciantes #programação #dsa

Agora, vamos começar a implementar nossa pilha usando uma lista vinculada individualmente. Devemos nós?

Primeiro, criaremos uma classe Node para representar nosso item individual da pilha.

class Node {
  constructor(data) {
    this.data = data;
    this.next = null;
  }
}

Em seguida, criaremos uma classe Stack para representar nossa pilha.

class Stack {
  constructor() {
    this.top = null;
    this.size = 0;
  }

  // Stack Operations will be implemented here ?
}

Operação push

A operação push adiciona um novo elemento ao topo da pilha. Ele cria um novo StackNode, define seu próximo ponteiro para o topo atual e, em seguida, atualiza top para apontar para esse novo nó. Finalmente, aumenta o tamanho.

  // Push element to the top of the stack
  push(element) {
    const newNode = new Node(element);
    newNode.next = this.top;
    this.top = newNode;
    this.size  ;
  }

Operação pop

A operação pop remove o elemento mais alto da pilha. Primeiro verifica se a pilha está vazia. Se for, ele retorna uma mensagem de erro. Caso contrário, remove o elemento superior, atualiza o ponteiro superior para o próximo nó e diminui o tamanho. Finalmente, ele retorna o elemento removido.

  // Remove and return the top element
  pop() {
    if (this.isEmpty()) {
      return "Stack is empty";
    }
    const poppedElement = this.top.data;
    this.top = this.top.next;
    this.size--;
    return poppedElement;
  }

Operação de espiada

A operação peek retorna o elemento superior sem removê-lo. Primeiro verifica se a pilha está vazia. Se for, ele retorna uma mensagem de erro. Caso contrário, ele retorna os dados do elemento superior.

  // Return the top element without removing it
  peek() {
    if (this.isEmpty()) {
      return "Stack is empty";
    }
    return this.top.data;
  }

Operação isEmpty

A operação isEmpty verifica se a pilha está vazia. Ele retorna verdadeiro se a pilha estiver vazia e falso caso contrário.

  // Check if the stack is empty
  isEmpty() {
    return this.size === 0;
  }

Operação getSize

A operação getSize retorna o tamanho da pilha. Ele retorna o número de elementos na pilha.

  // Return the size of the stack
  getSize() {
    return this.size;
  }

Operação de impressão

A operação de impressão imprime a pilha. Ele retorna os dados do elemento superior.

  // Print the stack
  print() {
    let current = this.top;
    let result = "";
    while (current) {
      result  = current.data   " ";
      current = current.next;
    }
    console.log(result.trim());
  }

Exemplo de uso

// Usage example
const customStack = new CustomStack();
customStack.push(10);
customStack.push(20);
customStack.push(30);
console.log(customStack.pop()); // 30
console.log(customStack.peek()); // 20
console.log(customStack.getSize()); // 2
console.log(customStack.isEmpty()); // false
customStack.print(); // 20 10

Nesta implementação, usamos uma estrutura de lista vinculada (lista vinculada individualmente) para representar nossa pilha. Cada elemento é um Nó com um valor de dados e uma referência para o próximo Nó. O topo da pilha é sempre o nó adicionado mais recentemente.

Conclusão

As pilhas são uma estrutura de dados fundamental na ciência da computação que segue o princípio Last In, First Out (LIFO). Eles são usados ​​em vários aplicativos, incluindo gerenciamento de chamadas de função, implementação de funcionalidade de desfazer e avaliação de expressões aritméticas.

Neste tutorial, cobrimos os fundamentos das pilhas, os prós e os contras de usá-las e sua implementação em JavaScript (usando lista vinculada). Compreender as pilhas não é apenas saber como implementá-las, mas também reconhecer quando elas são a ferramenta certa para resolver um problema.

Ao continuar sua jornada no desenvolvimento de software, você descobrirá que as pilhas são uma ferramenta indispensável em seu kit de ferramentas de solução de problemas. Eles são simples, mas poderosos, e dominá-los aumentará significativamente sua capacidade de projetar algoritmos e estruturas de dados eficientes.

Fique atualizado e conectado

Para garantir que você não perca nenhuma parte desta série e se conectar comigo para discussões mais aprofundadas sobre desenvolvimento de software (Web, servidor, móvel ou scraping/automação), estruturas de dados e algoritmos e outras tecnologias interessantes tópicos, siga-me em:

• GitHub
• Linkedin
• X (Twitter)

Fique ligado e boa programação ?‍??