Estrutura de dados — Pilha (Stack)

Dando continuidade ao tema de estrutura de dados, vamos falar da pilha.
A Pilha, ou em inglês Stack, é uma das mais básicas e mais utilizadas estrutura de dados.

No mundo do desenvolvimento, podemos citar e observar a sua utilização na execução de um programa:
À medida que o Program Counter vai realizando as instruções contidas em um programa, os dados de algumas variáveis e funções são armazenadas (empilhadas) na pilha. Quando se há uma chamada de função, esta é empilhada e ao final da execução do bloco, é feito o desempilhamento. Após os dados serem desempilhados, o Program Counter retorna para a próxima instrução depois da chamada da função.

Depois dessa breve e sucinta explicação, já conseguimos extrair duas operações que são realizadas pela pilha, o empilhar (push) e o desempilhar (pop). Estas operações são responsáveis por adicionar e retirar elementos da pilha, observe a imagem abaixo que demonstra essas operações.

Basicamente o controle das operações em uma pilha é realizado através do topo. Sua concepção é baseada no princípio LIFO (Last In, First Out), que significa último a entrar e primeiro a sair. Dadas estas informações, vamos a implementação.

Implementação

public class Stack<T>
{
  public int Top { get; private set; }
  public int Length { get => _items.Length; }
  private readonly T[] _items;
  private const int InitialTopEmptyStack = -1;
  public Stack(int size)
  {
     _items = new T[size];
     Top = InitialTopEmptyStack;
  }
  public void Push(T item)
  {
    if (Top < _items.Length - 1)
    {
      _items[++Top] = item;
    }
    else
    {
    throw new IndexOutOfRangeException("It's not possible push items     out of length stack range");
    }
  }
  public void Pop()
  {
    if (!IsEmpty())
    {
      _items[Top] = default(T);
      Top--;
    }
  }
  public void PrintElements()
  {
     for (int i = 0; i < _items.Length; i++)
     {
       Console.WriteLine($"items[{i}] = {_items[i]}");
     }
  }
  public bool IsEmpty()
  {
    return Top.Equals(InitialTopEmptyStack);
  }
  public bool Contains(T item)
  {
    return _items.Contains(item);
  }
}

Acima temos a classe Stack que foi implementada com as operações de Push e Pop que mencionei, além de outras que achei interessante implementar. Também podemos observar que nesses métodos de Pop e Push, fazemos o controle do que entra e do que sai através da propriedade Top. Esta propriedade é responsável por armazenar em qual índice está o topo da pilha.

Para a implementação desta classe, eu utilizei o recurso de Generics do C#. Ele permite com que a nossa classe Stack armazene qualquer tipo de dado, basta especifica-lo em sua instanciação, por exemplo:

int size = 10;
var stack = new Stack<string>(size);
var stack = new Stack<int>(size);

Conclusão

A pilha é uma estrutura de dados bem importante para o nosso conhecimento e para nossa formação profissional, pois está entre os alicerces que julgo serem importantes para qualquer desenvolvedor.
Conhecendo e tendo domínio destas estruturas, conseguimos enxergar mais claramente o "por quê" das coisas no mundo da computação / desenvolvimento.

Espero que tenham gostado!!! \o/

Para ver o código e alguns testes que foram implementados, dê uma olhada no repositório deste código em meu Github.

guilhermerm-dev/data-structure-stack

Até a próxima!!!

In God I Trust!!!