如何在C#中删除不在堆栈顶部的堆栈项

Question

不幸的是,只能通过"pop"从堆栈中删除项目.堆栈没有"删除"方法或类似的东西,但我有一个堆栈(是的,我需要一个堆栈!),我需要从中删除一些元素.

有这个诀窍吗？

Answer 1

如果您需要删除不在顶部的项目,那么您需要的不是堆栈.

尝试从List中创建自己的堆栈实现.然后,您可以实现自己的推送和弹出功能(在列表中添加和删除),以及您自己的特殊PopFromTheMiddle功能.

例如

public class ItsAlmostAStack<T>
{
    private List<T> items = new List<T>();

    public void Push(T item)
    {
        items.Add(item);
    }
    public T Pop()
    {
        if (items.Count > 0)
        {
            T temp = items[items.Count - 1];
            items.RemoveAt(items.Count - 1);
            return temp;
        }
        else
            return default(T);
    }
    public void Remove(int itemAtPosition)
    {
        items.RemoveAt(itemAtPosition);
    }
}

Answer 2

考虑使用不同的容器.也许是LinkedList.然后你可以使用

AddFirst
AddLast
RemoveLast
RemoveFirst

就像从堆栈弹出/推送一样,你可以使用

Remove

从列表中间删除任何节点

Answer 3

您可以使用LinkedList

基于列表的删除可能效率较低.在通过引用移除基于列表的堆栈将具有O(N)搜索和O(N)调整大小.LinkedList搜索是O(N),删除是O(1).对于按索引删除,LinkedList应该有O(N)遍历和O(1)删除,而List将有O(1)遍历(因为它是索引)和O(N)删除由于调整大小.

除了效率之外,LinkedList实现还可以让您进入标准库,打开代码以获得更大的灵活性并让您减少编写.

这应该能够处理Pop,Push和Remove

    public class FIFOStack<T> : LinkedList<T>
    {
        public T Pop()
        {
            T first = First();
            RemoveFirst();
            return first;
        }

        public void Push(T object)
        {
            AddFirst(object);
        }

        //Remove(T object) implemented in LinkedList
   }

Answer 4

也许扩展方法可行,但我怀疑完全需要完全不同的数据结构.

public static T Remove<T>( this Stack<T> stack, T element )
{
     T obj = stack.Pop();
     if (obj.Equals(element))
     {
         return obj;
     }
     else
     {
        T toReturn = stack.Remove( element );
        stack.Push(obj);
        return toReturn;
     }
}