How to remove a stack item which is not on the top of the stack in C#

Question

Unfortunately an item can only be removed from the stack by "pop". The stack has no "remove" method or something similar, but I have a stack (yes I need a stack!) from which I need to remove some elements between.

Is there a trick to do this?

Answer 1

This still processes the whole stack, but it is an alternative to remove an entry. The way this is written though, if the same entry is in the stack multiple times, it will remove them all.

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

Answer 2

I used a list and added some extension methods, eg,

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

Answer 3

I came across this question. In my code I created my own extension method:

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

And I call my method like this:

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

selectedReportNumbersInSession.Remove(removedReportNumbers);

Answer 4

You could use a LinkedList

List based removal will likely be less efficient. In removal by reference List based stacks will have O(N) search and O(N) resizing. LinkedList search is O(N) and removal is O(1). For removal by index, LinkedList should have O(N) traversal and O(1) removal, while List will have O(1) traversal (because it is indexing) and O(N) removal due to resizing.

Besides efficiency, a LinkedList implementation will keep you in the standard library, opening your code to more flexibility and have you writing less.

This should be able to handle Pop, Push, and 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 5

A trick I use in hairy situations is adding a 'deprecated' flag to the items in the stack. When I want to 'remove' an item, I simply raise that flag (and clean up any resources that are taken by the object). Then when Pop()ing items I simply check if the flag is raised, and pop again in a loop until a non-deprecated item is found.

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

You can manage your own item-count to know how many 'real' items are still in the queue, and obviously locking should be employed if this is required for multi-threaded solution.

I found that for queues that have constant flow through them - items pushed and popped - it's much more efficient to hanle it this way, its the fastest you can get (paying O(1) for removing an item from the middle) and memory wise if the object that is retained is small, it's mostly irrelevant if the items flow in a reasonable pace.

Answer 6

If you need to remove items that aren't on the top, then you need something other than a stack.

Try making your own implementation of a stack from a List. Then you get to implement your own push and pop functions (add & remove on the list), and your own special PopFromTheMiddle function.

For example

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 7

The constructor of a Stack<> takes IEnumerable<> as a parameter. So it would be possible to perform the following:

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

This is non performant in a number of ways.

Answer 8

Perhaps an extension method would work, although, I suspect that a different data structure entirely is really needed.

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 9

Consider using different container. Maybe a LinkedList. Then you can use

AddFirst
AddLast
RemoveLast
RemoveFirst

just like pop/push from stack and you can use

Remove

to remove any node from the middle of the list

Answer 10

In a true stack, this can only be done one way -

Pop all of the items until you remove the one you want, then push them back onto the stack in the appropriate order.

This is not very efficient, though.

If you truly want to remove from any location, I'd recommend building a pseudo-stack from a List, LinkedList or some other collection. This would give you the control to do this easily.

Answer 11

hmmmm...... I agree with the previous two answers but if you are looking to hack your way just pop and save all elements until you get to the one you want, and the re-push them all

Yes is ugly, badly performing, probably weird code that will need a long comment explaining why, but you could do it....

Answer 12

   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 13

Then it is not a stack right? Stack is LAST in FIRST out. You will have to write a custom one or choose something else.