computer science Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...

, peek is an operation on certain

abstract data type In computer science, an abstract data type (ADT) is a mathematical model for data types. An abstract data type is defined by its behavior (Semantics (computer science), semantics) from the point of view of a ''User (computing), user'', of the dat ...

s, specifically sequential

collections Collection or Collections may refer to: * Cash collection, the function of an accounts receivable department * Collection (church), money donated by the congregation during a church service * Collection agency, agency to collect cash * Collection ...

such as stacks and queues, which returns the value of the top ("front") of the collection without removing the element from the collection. It thus returns the same value as operations such as "pop" or "dequeue", but does not modify the data. The name "peek" is similar to the basic "push" and "pop" operations on a stack, but the name for this operation varies depending on data type and language. Peek is generally considered an inessential operation, compared with the more basic operations of adding and removing data, and as such is not included in the basic definition of these data types. However, since it is a useful operation and generally easily implemented, it is frequently included in practices, and in some definitions peek is included as basic, with pop (or analog) defined in terms of peek; see

abstract definition Abstract may refer to: * ''Abstract'' (album), 1962 album by Joe Harriott * Abstract of title a summary of the documents affecting title to parcel of land * Abstract (law), a summary of a legal document * Abstract (summary), in academic publishi ...

Data types

Sequential types for which peek is often implemented include: *

Stack Stack may refer to: Places * Stack Island, an island game reserve in Bass Strait, south-eastern Australia, in Tasmania’s Hunter Island Group * Blue Stack Mountains, in Co. Donegal, Ireland People * Stack (surname) (including a list of people ...

Queue __NOTOC__ Queue () may refer to: * Queue area, or queue, a line or area where people wait for goods or services Arts, entertainment, and media *''ACM Queue'', a computer magazine * The Queue (Sorokin novel), ''The Queue'' (Sorokin novel), a 198 ...

Priority queue In computer science, a priority queue is an abstract data-type similar to a regular queue or stack data structure in which each element additionally has a ''priority'' associated with it. In a priority queue, an element with high priority is se ...

(such as a

heap Heap or HEAP may refer to: Computing and mathematics * Heap (data structure), a data structure commonly used to implement a priority queue * Heap (mathematics), a generalization of a group * Heap (programming) (or free store), an area of memory f ...

) *

Double-ended queue In computer science, a double-ended queue (abbreviated to deque, pronounced ''deck'', like "cheque") is an abstract data type that generalizes a queue, for which elements can be added to or removed from either the front (head) or back (tail). I ...

(deque) *

Double-ended priority queue In computer science, a double-ended priority queue (DEPQ)Operations on deques have varied names, often "front" and "back" or "first" and "last". The name "peak" is also occasionally found, in the sense of "top, summit", though this also occurs as a spelling error for the verb "peek".

Abstract definition

Intuitively, peek returns the same value as pop, but does not change the data. Behavior when the collection is empty varies – most often this yields an underflow error, identically to a pop on an empty collection, but some implementations provide a function which instead simply returns (without error), essentially implementing if isempty then return, else peek. This behavior can be axiomatized in various ways. For example, a common VDM (''

Vienna Development Method The Vienna Development Method (VDM) is one of the longest-established formal methods for the development of computer-based systems. Originating in work done at the IBM Laboratory Vienna in the 1970s, it has grown to include a group of techniques ...

'') description of a stack defines ''top'' (peek) and ''remove'' as atomic, where ''top'' returns the top value (without modifying the stack), and ''remove'' modifies the stack (without returning a value).Jones: "Systematic Software Development Using VDM" In this case ''pop'' is defined in terms of ''top'' and ''remove.'' Alternatively, given ''pop,'' the operation ''peek'' can be axiomatized as: :''peek''(''D'') = ''pop''(''D'') :''peek''(''D''), ''D'' = ''D'' meaning "returns the same value as ''pop''", and "does not change the underlying data" (value of data after peek same as before peek).

Implementation

Peek can generally be implemented very easily in simple routine taking O(1) time and no added space, by a simple variant of the pop operation. Most sequential data types are implemented by a data structure containing a

reference Reference is a relationship between objects in which one object designates, or acts as a means by which to connect to or link to, another object. The first object in this relation is said to ''refer to'' the second object. It is called a ''name'' ...

to the end, and thus peek is simply implemented by

dereferencing In computer programming, the dereference operator or indirection operator, sometimes denoted by "*" (i.e. an asterisk), is a unary operator (i.e. one with a single operand) found in List of C-family programming languages, C-like languages that in ...

this. In some cases it is more complicated, however. For some data types, such as stacks, this can be replicated in terms of more basic operations, but for other data types, such as queues, it cannot. Even if peek can be replicated in terms of other operations, it is almost always more efficient to implement it separately, as this avoids modifying the data, and it is easy to implement, as this simply consists of returning the same value as the "pop" (or analogous operation), but then not modifying the data. For the stack, priority queue, deque, and DEPQ types, peek can be implemented in terms of pop and push (if done at same end). For stacks and deques this is generally efficient, as these operations are O(1) in most implementations, and do not require memory allocation (as they decrease the size of the data) – the two ends of a deque each functioning as a stack. For priority queues and DEPQs, however, dequeuing and enqueuing often take O(log ''n'') time (for example if implemented as a

binary heap A binary heap is a heap data structure that takes the form of a binary tree. Binary heaps are a common way of implementing priority queues. The binary heap was introduced by J. W. J. Williams in 1964, as a data structure for heapsort. A bin ...

), while O(1) performance of "peek" (here generally called "find-min" or "find-max") is a key desired characteristic of priority queues, and thus peek is almost invariably implemented separately. For queue, because enqueuing and dequeuing occur at opposite ends, peek cannot be implemented in terms of basic operations, and thus is often implemented separately. One case in which peek is not trivial is in an ordered list type (i.e., elements accessible in order) implemented by a

self-balancing binary search tree In computer science, a self-balancing binary search tree (BST) is any node-based binary search tree that automatically keeps its height (maximal number of levels below the root) small in the face of arbitrary item insertions and deletions.Donald ...

. In this case find-min or find-max take O(log ''n'') time, as does access to any other element. Making find-min or find-max take O(1) time can be done by caching the min or max values, but this adds overhead to the data structure and to the operations of adding or removing elements.

References

* Horowitz, Ellis: "Fundamentals of Data Structures in Pascal", Computer Science Press, 1984, p. 67 {{Data structures Abstract data types