Cómo eliminar un elemento de pila que no está en la parte superior de la pila en C#

Question

Desafortunadamente, un elemento solo se puede eliminar de la pila mediante "pop". La pila no tiene un método de "quitar" o algo similar, pero tengo una pila (¡sí, necesito una pila!) De la cual necesito eliminar algunos elementos.

¿Hay un truco para hacer esto?

Answer 1

Si necesita eliminar elementos que no están en la parte superior, entonces necesita algo más que una pila.

Intente hacer su propia implementación de una pila desde una lista. Luego puede implementar sus propias funciones push y pop (agregue & eliminar en la lista) y su propia función especial PopFromTheMiddle.

Por ejemplo

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

considerar el uso de recipiente diferente. Tal vez una LinkedList. continuación, puede utilizar

AddFirst 
AddLast 
RemoveLast 
RemoveFirst

al igual que el pop/pulsador de la pila y se puede utilizar

Remove

eliminar cualquier nodo de la mitad de la lista

Answer 3

Entonces no es una pila ¿derecho? Stack es LAST in FIRST out. Tendrá que escribir uno personalizado o elegir algo más.

Answer 4

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 5

hmmmm ...... Estoy de acuerdo con las dos respuestas anteriores, pero si usted está buscando para abrirse paso sólo pop y guardar todos los elementos hasta llegar a la que usted desea, y la re-push todos ellos

Si es feo, mal desempeño, código probablemente raro que será necesario un largo comentario explicando por qué, pero que podría hacerlo ....

Answer 6

En una verdadera pila, esto sólo se puede hacer de una manera -

Aparece todos los elementos hasta que elimine el que desea, luego vuelva a empujarlos a la pila en el orden apropiado.

Esto no es muy eficiente, sin embargo.

Si realmente desea eliminar desde cualquier ubicación, le recomiendo que construya una pseudo-pila de una lista, LinkedList u otra colección. Esto le daría el control para hacer esto fácilmente.

Answer 7

Quizás un método de extensión funcionaría, aunque, sospecho que una estructura de datos diferente es realmente necesaria.

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 8

El constructor de una pila <> toma IEnumerable <> como parámetro. Por lo tanto, sería posible realizar lo siguiente:

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

Esto no funciona de varias maneras.

Answer 9

Un truco que uso en situaciones peludas es agregar una bandera 'en desuso' a los artículos en la pila. Cuando quiero 'eliminar' un elemento, simplemente levanto esa bandera (y elimino todos los recursos que haya tomado el objeto). Luego, al hacer pop() elementos, simplemente verifico si la bandera está levantada, y aparece de nuevo en un bucle hasta que se encuentra un elemento no desaprobado.

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

Puede gestionar su propio elemento de conteo para saber cuántos elementos 'reales' son todavía en la cola, y, obviamente, el bloqueo debe ser empleado si esto es necesario para la solución multi-hilo.

Descubrí que para las colas que tienen un flujo constante a través de ellas - elementos empujados y reventados - es mucho más eficiente manejar esto de la manera más rápida posible (pagando O (1) por quitar un artículo del medio) y en cuanto a la memoria, si el objeto retenido es pequeño, es casi irrelevante si los elementos fluyen a un ritmo razonable.

Answer 10

Se puede usar un retiro basado LinkedList

lista probablemente será menos eficiente. Eliminación por referencia Las pilas basadas en listas tendrán una búsqueda O (N) y un cambio de tamaño O (N). La búsqueda LinkedList es O (N) y la eliminación es O (1). Para eliminar por índice, LinkedList debe tener O (N) transversal y O (1) eliminación, mientras que List tendrá O (1) transversal (porque está indexando) y O (N) eliminación debido al cambio de tamaño.

Además de la eficiencia, una implementación de LinkedList lo mantendrá en la biblioteca estándar, abriendo su código para mayor flexibilidad y haciendo que escriba menos.

Esto debe ser capaz de manejar Pop, Push, y quitar

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 11

me encontré con esta pregunta. En mi código que he creado mi propio método de extensión:

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

Y llamo a mi método como este:

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

selectedReportNumbersInSession.Remove(removedReportNumbers);