23

Eu cheguei a uma parte do meu programa em que tenho de aplicar uma stack (pilha) e queria que alguém me desse uma explicação simples e um exemplo.

O programa que estou a realizar neste momento é um bloco de notas em que se cria vários "papéis" para afixar algo importante, com uma base de dados para guardar o que foi escrito; mas após isso o meu professor pediu uma stack...

2
  • 1
    Olá. Veja se isso ajuda, por favor: dotnetperls.com/stack 11/03/2014 às 22:12
  • 1
    Alguma resposta lhe ajudou mais? Você pode aceitar uma delas com a mais correta (sinal de check verde abaixo da pontuação/ setas de votação da resposta). Isto lhe dá reputação.
    – Maniero
    20/05/2014 às 17:26

2 Respostas 2

18

Não vou repetir o que o Miguel Angelo bem disse.

Uma pilha é chamada assim por em conceito abstrato. Evidente que fisicamente na memória não há dados sendo empilhados em lugar nenhum.

Uma pilha ou stack é uma estrutura de dados muito eficiente justamente porque é bastante limitada. Mas essa limitação que se encaixa muito bem em vários problemas.

É comum você precisar adicionar elementos seguidos a uma lista e retirá-los da lista na ordem inversa a colocada. Desta forma é muito fácil manipular a inserção e a remoção de elementos.

Isto se torna especialmente favorável se você tem um tamanho definido da pilha que sempre caiba todos os elementos que precisam ser colocados. Mas nada impede de ter uma pilha que varia em tamanho. Claro que todas as vezes que o espaço disponível para os elementos precisar ser aumentado ou reduzido, um processamento extra é necessário. Mas isso ocorre em blocos (em geral dobra de tamanho toda vez que a pilha estiver cheia e a redução só é feita por requisição manual). Quando há tamanho definido uma adição "custa" apenas uma mudança de ponteiro e verificação se não estourou o limite da pilha.

Pilha

Um exemplo bastante típico de pilha é a organização dos dados em memória em uma aplicação. Conforme blocos de código vão sendo executados, cada dado necessário vai sendo colocado na pilha. E quando a execução do bloco termina e não é mais necessário guardar esse dado para outros usos, basta deslocar o ponteiro para baixo (dependendo de como você está vendo a pilha pode ser para cima).

A solução de um problema de Torre de Hanoi também usa pilha.

Compiladores e softwares que façam análises de expressões também usam pilhas.

Problemas mais triviais também podem usar pilhas. Sempre que tenha essa característica de UEPS (último a entrar, primeiro a sair), a pilha deve ser usada. Um exemplo trivial é para funcionalidade de undo.

Exemplo:

using System;
using System.Collections.Generic;

class Program {
    static Stack<int> MontaPilha() {
        var pilha = new Stack<int>(); //Cria a pilha que vai guardar ints
        pilha.Push(3261); //manda o primeiro elemento para a pilha
        pilha.Push(1352); //vai mais um elemento ficando do seu topo
        pilha.Push(723); //sucessivamente
        pilha.Push(1234);
        return pilha;
    }

    static void Main() {
        var pilha = MontaPilha();
        foreach (int i in pilha) {
            Console.WriteLine(i); //acesa cada inteiro varrendo toda a pilha
        }

        Console.WriteLine(pilha.Pop()); //retira o elemento mais recente colocado na pilha. no exemplo passará ter apenas 3 elementos. Vai imprimir 1234

        Console.WriteLine(pilha.Peek()); //pega o elemento mais recente/topo sem retirá-lo. Vai imprimir 123

        pilha.Clear(); //limpa todos os elementos da pilha

        Console.WriteLine(pilha.Count); //vai imprimir 0
    }
}

Veja funcionando no ideone. E no .NET Fiddle. Também coloquei no GitHub para referência futura.

13

Stack nada mais é que uma pilha, em que os objetos que vão entrando acabam por bloquear os que já estão na pilha, de forma que somente aquele que não tiver nenhum outro bloqueando pode ser retirado da pilha.

Exemplos de pilhas:

  • uma pilha de pratos, se tirar o do fundo, provavelmente todos vão cair

  • uma pilha de papel, se tentar tirar uma do meio, pode rasgar

Como estrutura de dados, uma pilha representa esta situação, em que vários itens podem ser inseridos, e só podem ser retirados da pilha, na ordem inversa ao das inserções, ou seja, o último a ser inserido sai primeiro, e o primeiro a ser inserido sai por último. A isso se dá o nome de LIFO (Last-in first-out), que em português fica último-a-entrar primeiro-a-sair.

Usando em um programa

O .Net já possui uma classe para pilha: Stack<T>.

Ela possui dois métodos importantes, que equivalem às ações de adicionar um objeto ao topo da pilha Push, e outro de retirar um objeto do topo da pilha Pop. Além disso possui uma propriedade muito útil, para indicar quantos objetos existem na pilha Count.

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .