Stack / Stack with priority in C #?

4

My teacher passed 2 exercises, the first was to create a simple stack ( Stack ) 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 wrote for the following purposes:

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

  

Important: Since this class is already used in its original form, it should be ensured that normal operation is not modified by add

Features to add:

  • PrioritaireIsEmpty() : Returns a true bool if the stack does not contain priority elements.
  • PushPrioritaire() : Stacks 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 in 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 resulted in an error.

    
asked by anonymous 06.09.2017 / 07:05

1 answer

3

I start by saying that in your code Pop is not updating the top element, so a Peek after Pop does not return the correct element. You can correct 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();
}

As for the priority elements I see two solutions:

  • Building a second built-in list for priority elements only.
  • Or by creating an auxiliary class for each element with the element and priority, like this:

    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 look at the ones that look different, starting with 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;
}

By separating the insertion logic into an auxiliary method that starts to receive the list, so that it can be called with different lists.

The PrioritaireIsEmpty would be super simple simply querying if the priority list has elements:

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

In% w_th of% it would only be necessary to clean up the priority list:

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

What would lead to the most changes would be Clear which is now with the responsibility to remove first from the priority list, and if it does not have remove elements 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 it working on .net Fiddle

    
06.09.2017 / 13:37