World Library  
Flag as Inappropriate
Email this Article

Peek (data type operation)

Article Id: WHEBN0037875328
Reproduction Date:

Title: Peek (data type operation)  
Author: World Heritage Encyclopedia
Language: English
Subject: Priority queue, Double-ended queue, Heap (data structure)
Collection:
Publisher: World Heritage Encyclopedia
Publication
Date:
 

Peek (data type operation)

In computer science, peek is an operation on certain abstract data types, specifically sequential collections such as stacks and queues, which returns the value of the top of the collection without removing the value from the data. 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 practice.

Data types

Sequential types for which peek is often implemented include:

Single-ended types, such as stack, generally only admit a single peek, at the end that is modified. Double-ended types, such as deques, admit two peeks, one at each end.

Names for peek vary. "Peek" or "top" are common for stacks, while for queues "front" is common. 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) 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).[1] 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 to the end, and thus peek is simply implemented by dereferencing 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 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), 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 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

  1. ^ Jones: "Systematic Software Development Using VDM"
  • Horowitz, Ellis: "Fundamentals of Data Structures in Pascal", Computer Science Press, 1984, p. 67
This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and USA.gov, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for USA.gov and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.
 
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
 
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.
 



Copyright © World Library Foundation. All rights reserved. eBooks from World eBook Library are sponsored by the World Library Foundation,
a 501c(4) Member's Support Non-Profit Organization, and is NOT affiliated with any governmental agency or department.