Necesito una estructura de datos que tenga un capacity, pero también que permita adding an item from either the front or the back. Cada vez que se agrega un artículo, se debe quitar uno del extremo opuesto. Lo primero que pensé fue que esto suena muy similar a un Deque.

¿Existe una estructura de datos existente que proporcione esta funcionalidad o tengo que crearla yo mismo? Si existe, does the .Net library have an implementation?

Gracias

-2
user3096803 11 feb. 2015 a las 18:21

3 respuestas

La mejor respuesta

Le sugiero que utilice una LinkedList , que le brinda toda la funcionalidad que necesita. Hay métodos AddFirst y AddLast que le permiten agregar elementos en la parte delantera o trasera, y los métodos RemoveFirst y RemoveLast que le permiten eliminar desde la parte delantera y trasera.

Y, por supuesto, hay una propiedad Count que le indica cuántos elementos hay en la lista, para que pueda hacer cumplir su requisito de capacidad.

2
Jim Mischel 11 feb. 2015 a las 16:03

He decidido que la mejor opción es usar un array of T for the backing structure y tener un reference Front and a reference Back para representar el inicio y el final virtual de la estructura. También almacenaré una enumeración de dirección que indicará efectivamente a qué dirección se enfrenta la estructura (si la última operación de agregar fue en el frente o en la parte posterior o por defecto si no se han realizado operaciones de adición). This way, I can also implement an indexer with O(1) complexity, en lugar de iterar la colección.

Gracias por todas las respuestas. Por alguna razón, pensé que necesitaría mover los datos en la estructura de respaldo. No me di cuenta de que esta opción es posible en C #.

1
user3096803user3096803 11 feb. 2015 a las 16:20

No probado, pero creo que algo como esto funcionaría

public class Stack<T>
{
    private T[] arr;
    readonly int m_Size;
    int m_StackPointer = 0;
    public T this[int i]
    {
        get
        {
            if (i >= m_Size)
                throw new IndexOutOfRangeException();
            int pointer = i + m_StackPointer;
            if (pointer >= (m_Size)) pointer -= m_Size;
            return arr[pointer];
        }
    }
    public void AddStart(T addItem)
    {
        m_StackPointer--;
        if (m_StackPointer < 0) m_StackPointer = m_Size - 1;
        arr[m_StackPointer] = addItem;
    }
    public void AddEnd(T addItem)
    {
        arr[m_StackPointer] = addItem;
        m_StackPointer++;
        if (m_StackPointer >= m_Size) m_StackPointer = 0;
    }
    public Stack()
        : this(100)
    { }
    public Stack(int size)
    {
        m_Size = size;
        arr = new T[size];
    }
}
2
paparazzo 11 feb. 2015 a las 16:26