En informática , peek es una operación sobre ciertos tipos de datos abstractos , en concreto colecciones secuenciales como pilas y colas , que devuelve el valor de la parte superior ("front") de la colección sin eliminar el elemento de la colección. Por tanto, devuelve el mismo valor que operaciones como "pop" o "dequeue", pero no modifica los datos.
El nombre "peek" es similar a las operaciones básicas "push" y "pop" en una pila, pero el nombre de esta operación varía según el tipo de datos y el lenguaje. Peek generalmente se considera una operación no esencial, en comparación con las operaciones más básicas de agregar y quitar datos, y como tal no se incluye en la definición básica de estos tipos de datos. Sin embargo, dado que es una operación útil y generalmente fácil de implementar, se incluye con frecuencia en las prácticas y en algunas definiciones peek se incluye como básica, con pop (o análogo) definido en términos de peek; consulte la definición abstracta.
Los tipos secuenciales para los que se suele implementar peek incluyen:
Los tipos de un solo extremo, como stack, generalmente solo admiten un único vistazo, en el extremo que se modifica. Los tipos de doble extremo, como deques, admiten dos vistazos, uno en cada extremo.
Los nombres de peek varían. "Peek" o "top" son comunes para las pilas, mientras que para las colas es común "front". Las operaciones en deques tienen nombres variados, a menudo "front" y "back" o "first" y "last". El nombre "peak" también se encuentra ocasionalmente, en el sentido de "top, summit", aunque esto también ocurre como un error ortográfico para el verbo "peek".
Intuitivamente, peek devuelve el mismo valor que pop, pero no cambia los datos. El comportamiento cuando la colección está vacía varía: la mayoría de las veces, esto produce un error de desbordamiento, de manera idéntica a un pop en una colección vacía, pero algunas implementaciones proporcionan una función que, en cambio, simplemente devuelve (sin error), implementando esencialmenteif isempty then return, else peek.
Este comportamiento se puede axiomatizar de varias maneras. Por ejemplo, una descripción VDM ( Vienna Development Method ) común de una pila define top (peek) y remove como atómicos, donde top devuelve el valor superior (sin modificar la pila) y remove modifica la pila (sin devolver un valor). [1] En este caso, pop se define en términos de top y remove.
Alternativamente, dado pop, la operación peek se puede axiomatizar como:
que significa "devuelve el mismo valor que pop " y "no cambia los datos subyacentes" (el valor de los datos después del peek es el mismo que antes del peek).
En general, Peek se puede implementar muy fácilmente en una rutina simple que requiere tiempo O (1) y no agrega espacio, mediante una variante simple de la operación pop. La mayoría de los tipos de datos secuenciales se implementan mediante una estructura de datos que contiene una referencia al final y, por lo tanto, Peek se implementa simplemente desreferenciando esta. Sin embargo, en algunos casos es más complicado.
Para algunos tipos de datos, como las pilas, esto se puede replicar en términos de operaciones más básicas, pero para otros tipos de datos, como las colas, no se puede. Incluso si peek se puede replicar en términos de otras operaciones, casi siempre es más eficiente implementarlo por separado, ya que esto evita modificar los datos, y es fácil de implementar, ya que simplemente consiste en devolver el mismo valor que el "pop" (u operación análoga), pero luego no modifica los datos.
Para los tipos de pila, cola de prioridad, deque y DEPQ, la exploración puede implementarse en términos de extracción y inserción (si se realiza en el mismo extremo). Para las pilas y deques, esto es generalmente eficiente, ya que estas operaciones son O (1) en la mayoría de las implementaciones y no requieren asignación de memoria (ya que disminuyen el tamaño de los datos): los dos extremos de un deque funcionan como una pila. Sin embargo, para las colas de prioridad y los DEPQ, la extracción y la incorporación de datos a menudo requieren un tiempo O (log n ) (por ejemplo, si se implementan como un montón binario ), mientras que el rendimiento O (1) de "exploración" (aquí generalmente llamado "find-min" o "find-max") es una característica clave deseada de las colas de prioridad y, por lo tanto, la exploración casi invariablemente se implementa por separado.
En el caso de las colas, debido a que la incorporación y la salida de cola se producen en extremos opuestos, la vista previa no se puede implementar en términos de operaciones básicas y, por lo tanto, a menudo se implementa por separado.
Un caso en el que peek no es trivial es en un tipo de lista ordenada (es decir, elementos accesibles en orden) implementado por un árbol binario de búsqueda autoequilibrado . En este caso find-min o find-max toman O (log n ) tiempo, al igual que el acceso a cualquier otro elemento. Hacer que find-min o find-max tomen O (1) tiempo se puede hacer almacenando en caché los valores min o max, pero esto agrega sobrecarga a la estructura de datos y a las operaciones de agregar o eliminar elementos.