Stack/Stack with priority in c#?

Question

My teacher passed 2 exercises, the first was to create a stack (Stack) simple to run unit tests in this class:

    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;
    }
}
  }

The class was created, the test class and a client class as well.

The second question is that the teacher asked to modify the class Stack that we write for the following purposes:

Modifications to be made: You must modify the stack so that it can be stacked priority elements. The method PushPrioritaire() stack an element with high priority. In the method pop, the priority elements are stacked first.

Important: Since this class is already used in its original form, it must be ensured that the usual operation is not modified by add feature.

Features to add:

• PrioritaireIsEmpty(): Returns a bool true if the battery does not contain priority elements.
• PushPrioritaire(): Stack a priority element.

And I have no idea how to write these new functions. The only thing I could think of was to implement a IComparable us obj and return:

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

But everything I wrote thinking about it was wrong.

Answer 1

I start by indicating that in your code the Pop is not updating the top widget, so a Peek after Pop does not return the correct element. You can fix this problem as follows:

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();
}

Regarding the priority elements I see two solutions:

• Building a second internal list only for priority elements.

• Or by creating an auxiliary class for each element with the element and the priority, in this way:

  private class Elemento
  {
      T elem;
      bool prioritario;
  }
  

  And change the list to private List<Elemento> stack = new List<Elemento>(); and the rest of the implementation accordingly.

Exemplifying the solution with two lists would look like this:

public class Stack<T>
{

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

Some of the methods would be the same. Let’s see which ones are different, starting with the 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;
}

Separating here the insertion logic in an auxiliary method that now receives the list, so it can be called with different lists.

The PrioritaireIsEmpty it would be super simple to consult only if the priority list has elements:

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

In the Clear it would only be necessary to also clear the priority list:

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

What would take more changes would be the Pop which is now under the responsibility of first removing from the priority list, and if that has no elements remove from the 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();
}

See how it works on . net Fiddle