Queue e Stack – Trabalhando com os modelos FIFO e LIFO em .NET

Introdução ao Queue e Stack

Na computação, duas das estruturas de dados mais conhecidas e comumente utilizadas são a FILA e a PILHA. Muitas vezes, é necessário desenvolver classes específicas para se trabalhar com essas estruturas, mas no .NET Framework já estão presentes nativamente as classes Queue e Stack cujo funcionamento é baseado no conceito de fila e pilha, respectivamente.

Neste artigo, conheceremos de forma detalhada essas duas classes. Serão apresentados seus principais métodos e propriedades, bem como exemplos práticos de uso. Porém, antes vamos entender melhor o funcionamento dessas estruturas.

Fila (First-in, First-out)

A fila implementa o conceito “First-in, First-out”, ou “Primeiro a entrar, Primeiro a sair”. Ou seja, o primeiro elemento inserido na lista é também o primeiro a ser removido. Podemos pensar, por exemplo, em uma fila de banco. A primeira pessoa a entrar na fila será a primeira a ser atendida, logo, a primeira a sair da fila.

Também é muito comum se usar a expressão FIFO (abreviação de first-in, first-out) para definir a pilha.

Pilha (Last-in, First-out)

O conceito implementado pela pilha é o de “Last-in, First-out” (também chamado LIFO ou FILO, de first-in, last-out, que tem o mesmo sentido prático) ou “Último a entrar, Primeiro a sair”.

Imagine, por exemplo, que você esteja organizando vários pratos. Inicialmente você organiza todos uns sobre os outros, formando uma pilha de pratos. Logo após, você irá retirar um a um para organizar no seu devido local. Perceba que o primeiro prato removido foi o último a ser inserido na pilha, aquele que ficou na parte superior. Enquanto isso, o primeiro prato inserido na pilha, aquele que está abaixo de todos, será o último removido.

Agora que os conceitos teóricos já foram apresentados, vejamos na prática como aplicá-los no .NET Framework.

Queue

A classe Queue encontra-se no namespace System.Collections e implementa o conceito de FIFO.

A única propriedade relevante dessa classe nesse contexto é o Count que retorna a quantidade de elementos atualmente existente na lista.

Por outro lado, mais de um método merece destaque, principalmente o Enqueue e o Dequeue, como veremos abaixo.

• Enqueue: recebe como parâmetro um objeto a ser inserido na lista, nesse caso, no final da fila.
• Dequeue: este método não recebe parâmetros, mas retorna o primeiro objeto da fila, aquele que, pela ordem, é o próximo a ser removido. Após a chamada desse método, o objeto retornado é também removido da fila.
• Peek: semelhante ao Dequeue, retorna o primeiro objeto da lista, mas não o remove. Pode ser usado quando se deseja apenas conhecer o valor do primeiro elemento.
• TrimToSize: altera a capacidade da lista para a quantidade atual de elementos. Com isso, memória é poupada, pois a classe Queue reserva memória para armazenar uma quantidade de elementos, se nem todos forem usados, parte da memória reservada fica sem uso. Usando o TrimToSize essa memória é liberada.
• Construtor: a classe Queue possui três sobrecargas do construtor original, que não recebe nenhum parâmetro. A primeira delas recebe um valor inteiro que define capacidade inicial da lista. A segunda recebe uma coleção (ICollection) da qual os itens são copiados para a lista. A terceira recebe um valor inteiro para a capacidade inicial e um fator de expansão do tipo float. Esse fator de expansão é utilizado para aumentar a capacidade da fila quando for necessário. Originalmente esse valor é pequeno para que não seja utilizada memória desnecessariamente.

Caso se conheça previamente o número de elementos a ser inserido da lista, é interessante definir a capacidade inicial (no constructor), evitando que memória extra seja reservada. Caso a quantidade de itens ultrapasse a capacidade inicialmente definida, esta é automaticamente expandida.

Stack

Também contida no namespace Sytem.Collections, a classe Stack implementa o conceito de LIFO, onde o último elemento inserido é o primeiro a ser removido.

A propriedade Count, também nesse caso, é a única com relevância nesse contexto e também retorna a quantidade de elementos contidos na lista.

Os métodos que merecem destaque são:

• Push: insere um objeto (recebido como parâmetro) no fim da lista.
• Pop: retorna e remove o elemento do topo da pilha, ou seja, o último que foi inserido.
• Peek: retorna o elemento do topo da pilha, porém sem que este seja removido.
• Construtor: além do construtor original, sem parâmetros, existem duas sobrecargas. A primeira recebe uma coleção do tipo ICollection da qual os itens são copiados para a pilha. A segunda recebe um valor inteiro que define a capacidade inicial da lista. Sobre a capacidade inicial, valem os mesmos comentários feitos a respeito da outra classe.

Métodos em comum

As duas classes possuem métodos em comum que vale a pena citar aqui:

• Clear: remove todos os itens da lista, não sendo possível recuperá-los.
• Contains: recebe como parâmetro um objeto a ser localizado na lista. Caso esse objeto esteja contido na fila, o retorno desse método é true, caso contrário, o retorno é false.

Exemplos práticos

Para os exemplos a seguir, foi utilizada uma aplicação console.

No exemplo a seguir, são inseridos três elementos em uma fila e, em seguida, todos são removidos e exibidos na ordem.

  Queue q = new Queue();
              
  //Inserindo três elementos
  q.Enqueue(1);
  q.Enqueue(2);
  q.Enqueue(3);
  
  Console.WriteLine("Listando elementos da fila:");
  
  //Enquanto houver elementos na lista, exibir e remover o primeiro
  while (q.Count > 0)
  {
      Console.WriteLine(q.Dequeue());
  }
  
  //Exibe a quantidade de elementos restantes, ou seja, zero
  Console.WriteLine("A lista agora possui " + q.Count.ToString() + " elementos.");
  Console.Read();

  Dim q As System.Collections.Queue = New System.Collections.Queue()
  
  'Inserindo três elementos
  q.Enqueue(1)
  q.Enqueue(2)
  q.Enqueue(3)
  
  Console.WriteLine("Listando elementos da lista:")
  
  'Enquanto houver elementos na lista, exibir e remover o primeiro
  While q.Count > 0
  Console.WriteLine(q.Dequeue())
  End While
  
  'Exibe a quantidade de elementos restantes, ou seja, zero
  Console.WriteLine("A lista possui agora " + q.Count.ToString() + " elementos.")
  
  Console.Read()

O resultado desse código é mostrado na Figura 1.

Note que os itens foram removidos na mesma ordem em que foram inseridos. O elemento 1 foi o primeiro a ser adicionado e também o primeiro a ser retirado da fila. Ao fim, não resta nenhum item.

A seguir temos um exemplo semelhante, mas utilizando a classe Stack. Nesse caso, os itens devem ser exibidos na ordem inversa da adição.

  Stack s = new Stack();
  
  //Inserindo três elementos
  s.Push(1);
  s.Push(2);
  s.Push(3);
  
  Console.WriteLine("Listando elementos da lista:");
  
  //Enquanto houver elementos na lista, exibir e remover o primeiro
  while (s.Count > 0)
  {
      Console.WriteLine(s.Pop());
  }
  
  //Exibe a quantidade de elementos restantes, ou seja, zero
  Console.WriteLine("A lista agora possui " + s.Count.ToString() + " elementos.");
  Console.Read();

  Dim s As System.Collections.Stack = New System.Collections.Stack()
  
  'Inserindo três elementos
  s.Push(1)
  s.Push(2)
  s.Push(3)
  
  Console.WriteLine("Listando elementos da lista:")
  
  'Enquanto houver elementos na lista, exibir e remover o primeiro
  While s.Count > 0
  Console.WriteLine(s.Pop())
  End While
  
  'Exibe a quantidade de elementos restantes, ou seja, zero
  Console.WriteLine("A lista possui agora " + s.Count.ToString() + " elementos.")
  
  Console.Read()

O resultado é exibido na Figura 2.

Como era esperado, os itens foram exibidos na ordem contrária a da inserção. O elemento 3 foi o último a ser inserido, mas foi o primeiro listado. Novamente, ao final do código não restam itens da pilha.

Conclusão

Na informática, são muitas as aplicações dos modelos FIFO e LIFO e, como vimos, o .NET Framework facilita bastante o trabalho com estruturas desse tipo, oferecendo duas classes eficientes e de fácil manipulação.

Sugiro que o leitor busque conhecer os demais métodos e propriedades dessas classes que, em geral, são comuns às classes que representam coleções nesse namespace.

Finalizo então este artigo e espero que o conteúdo aqui apresentado possa ser útil a quem dele possa precisar. Até a próxima.