Как удалить элемент стека, который не находится на вершине стека в C #

Question

К сожалению, предмет может быть удален только из стека "pop". В стеке нет метода «удалить» или чего-то подобного, но у меня есть стек (да, мне нужен стек!), Из которого мне нужно удалить некоторые элементы между ними.

Есть ли уловка, чтобы сделать это?

Answer 1

Если вам нужно удалить предметы, которые не находятся сверху, то вам нужно что-то, кроме стека.

Попробуйте создать собственную реализацию стека из списка. Затем вы можете реализовать свои собственные функции push и pop (добавлять и удалять в списке) и собственную специальную функцию 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

точно так же как pop / push из стека

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

Answer 5

В истинном стеке это можно сделать только одним способом -

Сдвигайте все предметы до тех пор, пока вы не удалите тот, который вам нужен, а затем поместите их обратно в стек в соответствующем порядке.

Хотя это не очень эффективно.

Если вы действительно хотите удалить из любого места, я бы порекомендовал создать псевдостек из List, LinkedList или какой-либо другой коллекции. Это даст вам возможность легко это сделать.

Answer 6

Уловка, которую я использую в сложных ситуациях, - добавление флага «не рекомендуется» к элементам в стеке. Когда я хочу «удалить» элемент, я просто поднимаю этот флаг (и очищаю все ресурсы, которые получает объект). Затем при всплывающих элементах я просто проверяю, установлен ли флаг, и снова всплываю в цикле, пока не будет найден объект, не подлежащий устареванию.

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

Вы можете управлять своим собственным количеством элементов, чтобы узнать, сколько «реальных» элементов все еще находится в очереди, и, очевидно, следует использовать блокировку, если это требуется для многопоточного решения.

Я обнаружил, что для очередей, которые имеют постоянный поток через них - элементы перемещаются и выталкиваются - гораздо эффективнее обрабатывать его таким образом, это самое быстрое, что вы можете получить (заплатив O (1) за удаление элемента из середины) и память, если объект, который сохраняется, маленький, это в основном не имеет значения, если элементы текут в разумном темпе.

Answer 7

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

Answer 8

Тогда это не стек, верно? Стек составляет LAST in FIRST out. Вам придется написать свой или выбрать что-то другое.

Answer 9

Конструктор стека <> принимает IEnumerable <> в качестве параметра. Так что можно было бы выполнить следующее:

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

Это неэффективно во многих отношениях.

Answer 10

Я использовал список и добавил несколько методов расширения, например,

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