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

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

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

Типы данных

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

• Куча
• Очередь
• Приоритетная очередь (например, куча )
• Двусторонняя очередь (deque)
• Двусторонняя приоритетная очередь (DEPQ)

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

Названия для пика могут быть разными. «Пик» или «верх» являются общими для стеков, а для очередей — «перед». Операции над деками имеют разные названия, часто «передние» и «задние» или «первые» и «последние». Название «пик» также иногда встречается в смысле «вершина, вершина», хотя это также происходит как орфографическая ошибка глагола «заглянуть».

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

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

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

В качестве альтернативы, учитывая pop, операцию peek можно аксиоматизировать как:

пик ( D ) = поп ( D )

заглянуть ( D ), D = D

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

Выполнение

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

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

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

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

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

Ссылки

• Горовиц, Эллис: «Основы структур данных в Паскале», Computer Science Press, 1984, стр. 67