Básicamente todos los métodos de búsqueda van a estar implementados (en su vertiente de más bajo nivel) por un array. No sé mucho de c++, y seguro que meto la pata, pero la idea es que la implementación sea algo como (te lo hago en java para que tengas una idea, porque en c++ seguro que meto la pata):
Código:
public class Metodo<T>{
private T[] lista;
public void addToEnd(T element);
public void addTo(T element, int i);
public void set(T element, int i);
public T get(int i);
}
Lo que te tiene que quedar claro es que vas a tener un array por debajo de tu implementación al que se va a acceder con los método que tú pongas. Típicamente el array empezará con una capacidad por defecto (para 10 elementos), y podrá tener un índice para saber cuál es el último elemento (que tenga una capacidad para 10 elementos no implica que todo el array esté ocupado). En el caso de se quiera añadir más elementos de los inicialmente previstos, lo que se hace es copiar el array en uno nuevo con mayor capacidad (típicamente el doble), y seguir manejando desde el nuevo array.
Lo que va a diferenciar son los métodos de acceso. Para un stack, por ejemplo, una vez que has sacado un elemento no puedes recuperarlo. Esto no implica que el elemento se borre de tu array, o tengas que hacer una copia para eliminar ese elemento. Lo que necesitarías sería tener un puntero (o índice) adicional que te marque el elemento que debe ser devuelto en caso que se haga un "get". Al hacer un "get" tan sólo devolverías el objeto asociado a dicha posición y avanzarías el puntero al siguiente elemento.
De todas formas, cómo lo tengas por debajo no es importante siempre y cuando tengas claro cómo debe funcionar. Por ejemplo, implementar una cola con un array puede ser un poco ineficiente (deberías copiar el array de vez en cuando para limpiar elementos no usados, cosas que no es necesario para un stack), entonces se podría implementar mediante listas enlazadas (o punteros). La forma de acceso debe ser la misma, pero implementarlo mediante un array requiere operaciones necesarias pero que perjudican el rendimiento (al menos eso creo, aunque habría que ver si sale o no rentable).
