C# Stack with deletable elements

Question

I need a stack structure that also allows the for the deleting of elements. I can't find anything like this in the .Net framework. Which structure provides the best basis for me to implement this?

Answer 1

System.Collections.Generic.List<T>

or

System.Collections.Generic.LinkedList<T>

depending on the circumstance.

Answer 2

Well, any list-like structure can be used as a stack. You just push and pop items off the end.

If you need to delete items in the middle of the stack, you can use the built-in generic List's RemoveAt().

Answer 3

Maybe a LinkedList<T>? you'd have to wrap it yourself to treat it as a Stack<T>, though. Of course, you could just use List<T> - but you'd have to absorb the cost of deleting from the middle...

Something like:

using System;
using System.Collections.Generic;
class MyStack<T> {
    private readonly LinkedList<T> list = new LinkedList<T>();
    public void Push(T value) {
        list.AddLast(value);
    }
    public int Count { get { return list.Count; } }
    public T Pop() {
        LinkedListNode<T> node = list.Last;
        if(node == null) throw new InvalidOperationException();
        list.RemoveLast();
        return node.Value;
    }
    public bool Remove(T item) {
        return list.Remove(item);
    }
}

with whatever other methods / synchronization / etc you need.

Answer 4

I would use a LinkedList as it has methods for AddFirst (Push) and RemoveFirst (Pop). But then it also has a simple Remove method that can be used to remove in middle.

Answer 5

By deleting of elements do you mean removing items that are not at the top of the stack?

One way you could do it is use a List and then use extension methods to implement the stack like behavior (coded in notepad, apologies for any minor errors). You can then also do special handling (maybe you want to return null or throw an exception if the list is empty, maybe you want to make sure that the item is not already in the list, etc.

public static void Push<T>(this IList<T> list, T item)
{
 list.InsertAt(0, item);
}

public static T Pop<T>(this IList<T> list)
{
 if(list.Count > 0)
 {
  T value = list[0];
  list.RemoveAt(0);
  return value;
 }
 // handle error
}