4

Meu professor passou 2 exercícios, o primeiro era criar uma pilha (Stack) simples para executar testes unitários nesta classe:

    using System;
    using System.Collections.Generic;
    using System.Linq;
    using System.Text;
    using System.Threading.Tasks;


   namespace Collections
   {
public class Stack<T>
{
    private List<T> stack = new List<T>();
    private bool isEmpty = true;
    private int count = 0;
    private object top = null;


    public bool IsEmpty
    { get { return isEmpty; } }

    public int Count
    { get { return count; } }


    public void Push(T obj)
    {
        stack.Add(obj);
        count++;
        top = obj;
        if (isEmpty)
            isEmpty = false;
    }


    public T Pop()
    {
        if (!isEmpty)
        {
            T element = stack.Last();
            stack.RemoveAt(stack.Count -1);
            count--;
            if (count == 0)
                isEmpty = true;
            return element;
        }
        else
            throw new InvalidOperationException();
    }


    public object Peek()


    {
        if (top == null)
            throw new InvalidOperationException();
        else
            return top;

    }


    public void Clear()
    {
        stack.Clear();
        isEmpty = true;
        count = 0;
    }
}
  }

A classe foi criada, a classe de testes e uma classe cliente também.

A segunda questão é que o professor pediu para modificar a classe Stack que escrevemos com os seguintes propósitos:

Modificações a realizar: Você deve modificar a pilha para que ela seja possível empilhar elementos prioritários. O méthodo PushPrioritaire() empilha um elemento com alta prioridade. No método pop, os elementos prioritários são desempilhados primeiramente.

Importante: Uma vez que essa classe já é usada em sua forma original, deve-se assegurar que o funcionamento habitual não seja modificado pelo add de funcionalidades.

Funcionalidades a acrescentar:

  • PrioritaireIsEmpty(): Retorna um bool verdadeiro se a pilha não contiver elementos prioritários.
  • PushPrioritaire(): Empilha um elemento prioritário.

E não tenho ideia de como escrever estas novas funções. A única coisa que consegui pensar era implementar um IComparable nos obj e retornar:

// obj 1 > obj 2 return > 0 (1)
// obj 1 < obj 2 return < 0 (-1)
// obj 1 == obj 2 return 0   

Mas tudo que escrevi pensando nisso resultou em erro.

2
  • Poderia deixar aqui o código do método PushPrioritaire()? Commented 6/09/2017 às 6:29
  • @CypherPotato esse código nao escrevi ... Tudo q cheguei a escrever tem erros em todo lugar Commented 6/09/2017 às 10:21

1 Resposta 1

3

Começo por indicar que no seu código o Pop não está a atualizar o elemento de topo, logo um Peek apos Pop não devolve o elemento correto. Pode corrigir este problema da seguinte forma:

public T Pop()
{
    if (!isEmpty)
    {
        T element = stack.Last();
        stack.RemoveAt(stack.Count - 1);
        count--;

        if (count == 0)
        {
            isEmpty = true;
            top = null; //linha adicionada
        }
        else //linha adicionada
            top = stack[stack.Count - 1]; //linha adicionada, para atualizar para o ultimo

        return element;
    }
    else
        throw new InvalidOperationException();
}

Quanto aos elementos prioritarios vejo duas soluções:

  • Construindo uma segunda lista interna só para os elementos prioritários.
  • Ou criando uma classe auxiliar para cada elemento com o elemento e a prioridade, desta forma:

    private class Elemento
    {
        T elem;
        bool prioritario;
    }
    

    E trocar a lista para private List<Elemento> stack = new List<Elemento>(); e o resto da implementação nesse sentido.

Exemplificando a solução com duas listas ficaria assim:

public class Stack<T>
{

    private List<T> stack = new List<T>(); 
    private List<T> stackP = new List<T>(); //a lista prioritaria
    ...

Alguns dos métodos seriam iguais. Vejamos os que ficam diferentes, começando pelos pushes:

public void PushPrioritaire(T obj)
{
    PushAuxiliar(stackP, obj);
}

public void Push(T obj)
{
    PushAuxiliar(stack, obj);
}

private void PushAuxiliar(List<T> st, T obj) //agora recebe a lista a inserir
{
    st.Add(obj);
    count++;
    top = obj;
    if (isEmpty)
        isEmpty = false;
}

Separando aqui a lógica de inserção num método auxiliar que passa a receber a lista, para poder ser chamado com listas diferentes.

O PrioritaireIsEmpty ficaria super simples consultando apenas se a lista prioritária tem elementos:

public bool PrioritaireIsEmpty()
{
    return stackP.Count == 0;
}

No Clear seria apenas necessário limpar também a lista prioritária:

public void Clear()
{
    stack.Clear();
    stackP.Clear(); //limpa a prioritária também
    top = null;
    isEmpty = true;
    count = 0;
}

O que levaria mais alterações seria o Pop que fica agora com a responsabilidade de remover primeiro da lista prioritária, e se essa não tiver elementos remover da normal:

public T Pop()
{
    if (!isEmpty)
    {
        //escolhe a lista que vai remover com base no tamanho da prioritária
        List<T> st = stackP.Count == 0 ? stack : stackP;

        T element = st.Last();
        st.RemoveAt(st.Count - 1);
        count--;

        if (count == 0)
        {
            isEmpty = true;
            top = null;
        }
        else { 
            //ajusta o top para a prioritária se tiver elementos ou normal caso contrario
            top = stackP.Count > 0 ? stackP[stackP.Count - 1] : stack[stack.Count - 1];
        }

        return element;
    }
    else
        throw new InvalidOperationException();
}

Veja a funcionar no .net Fiddle

2
  • Muito obrigado pela ajuda @Isac! Commented 6/09/2017 às 17:06
  • @MarceloMedeirosdosSantos De nada, resto de boa programação
    – Isac
    Commented 6/09/2017 às 17:12

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 .