37

不幸的是，一个项目只能通过“pop”从堆栈中删除。堆栈没有“删除”方法或类似的东西，但我有一个堆栈（是的，我需要一个堆栈！），我需要从中删除一些元素。

这样做有诀窍吗？

4

13 回答 13

59

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

尝试从列表中实现自己的堆栈。然后您可以实现自己的推送和弹出功能（在列表中添加和删除），以及您自己的特殊 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);
    }
}
于 2009-04-14T16:35:07.773 回答
13

考虑使用不同的容器。也许是一个链表。然后你可以使用

添加优先
最后添加
删除最后一个
删除优先

就像从堆栈中弹出/推送一样，您可以使用

消除

从列表中间删除任何节点

于 2009-04-14T16:35:18.257 回答
9

您可以使用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
   }
于 2012-11-10T04:35:59.067 回答
8

也许扩展方法会起作用，但我怀疑确实需要完全不同的数据结构。

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;
     }
}
于 2009-04-14T16:45:22.583 回答
4

在真正的堆栈中，这只能通过一种方式完成 -

弹出所有项目，直到删除您想要的项目，然后以适当的顺序将它们推回堆栈。

但是，这不是很有效。

如果你真的想从任何位置删除，我建议从 List、LinkedList 或其他集合构建一个伪堆栈。这将使您可以轻松地执行此操作。

于 2009-04-14T16:38:01.400 回答
3

那么它不是堆栈吗？堆栈是LAST in FIRST out. 您将不得不编写一个自定义的或选择其他的。

于 2009-04-14T16:36:45.397 回答
3 
   Stack temp = new Stack();
   object x, y;
   While ((x = myStack.Pop()) != ObjectImSearchingFor)
       temp.Push(x);
   object found = x;
   While ((y = temp.Pop()) != null)
      myStack.Push(y);
于 2009-04-14T16:37:52.603 回答
3

我在多毛情况下使用的一个技巧是在堆栈中的项目中添加一个“不推荐使用”标志。当我想“删除”一个项目时，我只需升起该标志（并清理该对象占用的任何资源）。然后，当 Pop() 处理项目时，我只需检查标志是否被提升，然后在循环中再次弹出，直到找到未弃用的项目。

do 
{  
   obj = mQueue.Pop();  
} while (obj.deprecated);

您可以管理自己的项目计数以了解队列中仍有多少“真实”项目，如果多线程解决方案需要，显然应该使用锁定。

我发现对于不断流经它们的队列 - 推送和弹出的项目 - 以这种方式处理它会更有效，它是你可以获得的最快的（支付 O(1) 从中间删除一个项目）和内存明智如果保留的对象很小，那么项目是否以合理的速度流动几乎是无关紧要的。

于 2012-05-03T17:15:18.183 回答
2

Stack<> 的构造函数将 IEnumerable<> 作为参数。因此可以执行以下操作：

myStack = new Stack<item>( myStack.Where(i => i != objectToRemove).Reverse() );

这在许多方面都是非性能的。

于 2012-02-02T10:30:44.027 回答
0

嗯......我同意前两个答案，但如果你想破解你的方式，只需弹出并保存所有元素，直到你找到你想要的，然后重新推送它们

是的，是丑陋的，性能不佳的，可能是奇怪的代码，需要很长的注释来解释原因，但你可以做到......

于 2009-04-14T16:38:00.433 回答
0

我遇到了这个问题。在我的代码中，我创建了自己的扩展方法：

public static class StackExtensions
{
    public static void Remove<T>(this Stack<T> myStack, ICollection<T> elementsToRemove)
    {
        var reversedStack = new Stack<T>();

        while(myStack.Count > 0)
        {
            var topItem = myStack.Pop();
            if (!elementsToRemove.Contains(topItem))
            {
                reversedStack.Push(topItem);
            }
        }

        while(reversedStack.Count > 0)
        {
            myStack.Push(reversedStack.Pop());
        }           
    }
}

我这样称呼我的方法：

var removedReportNumbers = 
selectedReportNumbersInSession.Except(selectedReportNumbersList).ToList();

selectedReportNumbersInSession.Remove(removedReportNumbers);
于 2018-03-06T19:00:09.407 回答
0

我使用了一个列表并添加了一些扩展方法，例如，

public static IThing Pop(this List<IThing> list)
{
  if (list == null || list.Count == 0) return default(IThing);

  // get last item to return
  var thing = list[list.Count - 1];
  // remove last item
  list.RemoveAt(list.Count-1);

  return thing;
}

public static IThing Peek(this List<IThing> list)
{
  if (list == null || list.Count == 0) return default(IThing);

  // get last item to return
  return list[list.Count - 1];
}

public static void Remove(this List<IThing> list, IThing thing)
{
  if (list == null || list.Count == 0) return;
  if (!list.Contains(thing)) return;

  list.Remove(thing); // only removes the first it finds
}

public static void Insert(this List<IThing> list, int index, IThing thing)
{
  if (list == null || index > list.Count || index < 0) return;

  list.Insert(index, thing);
}
于 2018-08-05T01:59:19.663 回答
0

这仍然处理整个堆栈，但它是删除条目的替代方法。但是，按照这种方式编写，如果同一条目在堆栈中多次出现，它将全部删除。

using System.Collections.Generic;

namespace StackTest
{
    class Program
    {
        static void Main(string[] args)
        {
            Stack<string> stackOne = new Stack<string>();

            stackOne.Push("Five");
            stackOne.Push("Four");
            stackOne.Push("Three");
            stackOne.Push("Two");
            stackOne.Push("One");
        
            deleteStackEntry(stackOne, @"Three");
            deleteStackEntry(stackOne, @"Five");
        }
        static void deleteStackEntry(Stack<string> st, string EntryToDelete)
        {
            // If stack is empty
            if (st.Count == 0) return;

            // Remove current item 
            string currEntry = st.Pop();

            // Remove other items with recursive call
            deleteStackEntry(st, EntryToDelete);

            // Put all items back except the one we want to delete 
            if (currEntry != EntryToDelete)
                st.Push(currEntry);
        }
    }
}
于 2021-04-01T15:44:32.820 回答