Peek (операция типа данных) - Peek (data type operation)

В Информатика, заглядывать это операция на определенных абстрактные типы данных, в частности, последовательный коллекции Такие как стеки и очереди, который возвращает значение верхней части («передней части») коллекции без удаления элемента из коллекции. Таким образом, он возвращает то же значение, что и такие операции, как «pop» или «dequeue», но не изменяет данные.

Имя «peek» похоже на базовые операции «push» и «pop» в стеке, но имя для этой операции зависит от типа данных и языка. Просмотр обычно считается несущественной операцией по сравнению с более простыми операциями добавления и удаления данных и как таковой не включен в базовое определение этих типов данных. Однако, поскольку это полезная операция и, как правило, ее легко реализовать, она часто включается в практики, и в некоторых определениях peek включен как базовый, а pop (или аналог) определяется в терминах peek; видеть абстрактное определение.

Типы данных

Последовательные типы, для которых часто реализуется просмотр, включают:

Односторонние типы, такие как стек, обычно допускают только один просмотр в конце, который изменяется. Двусторонние типы, такие как deques, допускают два взгляда, по одному с каждого конца.

Имена для просмотра различаются. «Взгляд» или «верх» обычны для стопок, а для очередей - «впереди». Операции с дека имеют разные названия, часто «передний» и «задний» или «первый» и «последний». Название «пик» также иногда встречается в смысле «вершина, вершина», хотя это также происходит как орфографическая ошибка для глагола «peek».

Абстрактное определение

Интуитивно понятно, что peek возвращает то же значение, что и pop, но не изменяет данные. Поведение, когда коллекция пуста, меняется - чаще всего это приводит к ошибке недостаточного заполнения, идентично всплывающему запросу в пустой коллекции, но некоторые реализации предоставляют функцию, которая вместо этого просто возвращает (без ошибок), по существу реализуя если пусто, то вернитесь, иначе посмотрите.

Такое поведение можно аксиоматизировать по-разному. Например, обычный VDM (Венский метод развития ) описание стека определяет верх (заглянуть) и удалять как атомарный, где верх возвращает верхнее значение (без изменения стека) и удалять изменяет стек (без возврата значения).[1] В этом случае поп определяется в терминах верх и удалять.

В качестве альтернативы, учитывая поп операция заглядывать аксиоматизируется как:

заглядывать(D) = поп(D)
заглядывать(D), D = D

значение "возвращает то же значение, что и поп"и" не изменяют базовые данные "(значение данных после просмотра такое же, как и до просмотра).

Выполнение

Как правило, Peek может быть очень легко реализован в простой процедуре, занимающей время O (1) и без дополнительного места, с помощью простого варианта операции pop. Большинство последовательных типов данных реализованы структурой данных, содержащей ссылка до конца, и поэтому функция peek просто реализуется разыменование это. Однако в некоторых случаях все сложнее.

Для некоторых типов данных, таких как стеки, это можно реплицировать с точки зрения более простых операций, но для других типов данных, таких как очереди, это невозможно. Даже если peek может быть воспроизведен с точки зрения других операций, почти всегда более эффективно реализовать его отдельно, поскольку это позволяет избежать изменения данных и его легко реализовать, поскольку он просто состоит из возврата того же значения, что и "pop "(или аналогичная операция), но без изменения данных.

Для типов стека, очереди приоритетов, двухсторонней очереди и DEPQ просмотр может быть реализован в терминах pop и push (если выполняется на одном конце). Для стеков и двухсторонних очереди это обычно эффективно, поскольку эти операции являются O (1) в большинстве реализаций и не требуют выделения памяти (поскольку они уменьшают размер данных) - два конца двухсторонней очереди, каждый из которых функционирует как стек. Однако для очередей с приоритетом и DEPQ для удаления из очереди и постановки в очередь часто требуется O (log п) время (например, если реализовано как двоичная куча ), в то время как O (1) производительность «peek» (здесь обычно называется «find-min» или «find-max») является ключевой желаемой характеристикой очередей с приоритетом, и, таким образом, просмотр почти всегда реализуется отдельно.

Для очереди, поскольку постановка в очередь и удаление из очереди происходят на противоположных концах, просмотр не может быть реализован в терминах основных операций и поэтому часто реализуется отдельно.

Одним из случаев, когда просмотр не является тривиальным, является тип упорядоченного списка (то есть элементы, доступные по порядку), реализованный самобалансирующееся двоичное дерево поиска. В этом случае find-min или find-max принимают O (log п) время, как и доступ к любому другому элементу. Заставить find-min или find-max занять время O (1) можно путем кэширования минимальных или максимальных значений, но это увеличивает накладные расходы на структуру данных и операции добавления или удаления элементов.

Рекомендации

  1. ^ Джонс: «Систематическая разработка программного обеспечения с использованием VDM»
  • Горовиц, Эллис: "Основы структур данных в Паскале", Computer Science Press, 1984, стр. 67