Войти
В информатике peek - это операция над определенным абстрактные типы данных, в частности последовательные коллекции, такие как стеки и очереди, которые возвращают значение вершины («переда») collection, не удаляя элемент из коллекции. Таким образом, он возвращает то же значение, что и такие операции, как «pop» или «dequeue», но не изменяет данные.
Имя «peek» похоже на базовые операции «push» и «pop» в стеке, но имя для этой операции различается в зависимости от типа данных и языка. Просмотр обычно считается несущественной операцией по сравнению с более простыми операциями добавления и удаления данных и как таковой не входит в базовое определение этих типов данных. Однако, поскольку это полезная операция и, как правило, ее легко реализовать, она часто включается в практики, и в некоторых определениях peek включен как базовый, а pop (или аналог) определяется в терминах peek; см. абстрактное определение.
Последовательные типы, для которых часто требуется просмотр реализовано:
Односторонние типы, такие как стек, обычно допускают только один просмотр на конце, который изменяется. Двусторонние типы, такие как deques, допускают два просмотра, по одному на каждом конце.
Имена для peek различаются. "Peek" или "top" являются общими для стеков, в то время как для очередей "front" - обычным явлением. Операции над deques имеют разные имена, часто "front" и "back" "или" первый "и" последний ". Название" пик "также иногда встречается в смысле" вершина, вершина ", хотя это также происходит как орфографическая ошибка для глагола" peek ".
Интуитивно peek возвращает то же значение, что и pop, но не изменяет данные. Поведение, когда коллекция пуста v aries - чаще всего это приводит к ошибке недостаточного заполнения, как и всплывающее окно для пустой коллекции, но некоторые реализации предоставляют функцию, которая вместо этого просто возвращает (без ошибок), по существу реализуя if isempty then return, else peek.
Такое поведение можно аксиоматизировать по-разному. Например, в общем описании стека в VDM (Венский метод разработки ) вершина (peek) и remove определяется как атомарная, где top возвращает верхнее значение (без изменения стека), а remove изменяет стек ( без возврата значения). В этом случае pop определяется как верхний и нижний.
В качестве альтернативы, для заданного pop, операция peek может быть аксиоматизирована как:
означает " возвращает то же значение, что и pop ", и" не изменяет базовые данные "(значение данных после просмотра такое же, как перед просмотром).
Peek, как правило, может быть очень легко реализован в простой программе, занимающей время O (1) и без дополнительного места, с помощью простого варианта операции pop. Большинство последовательных типов данных реализуются структурой данных, содержащей ссылку до конца, и, таким образом, peek просто реализуется посредством разыменования this. Однако в некоторых случаях все сложнее.
Для некоторых типов данных, таких как стеки, это можно воспроизвести с точки зрения более простых операций, но для других типов данных, таких как очереди, это невозможно. Даже если peek может быть воспроизведен с точки зрения других операций, почти всегда более эффективно реализовать его отдельно, поскольку это позволяет избежать изменения данных и его легко реализовать, поскольку он просто состоит из возврата того же значения, что и "pop "(или аналогичная операция), но без изменения данных.
Для типов стека, очереди с приоритетом, двухсторонней очереди и DEPQ просмотр может быть реализован в терминах pop и push (если выполняется на одном конце). Для стеков и двухсторонних очереди это обычно эффективно, поскольку эти операции являются O (1) в большинстве реализаций и не требуют выделения памяти (поскольку они уменьшают размер данных) - два конца двухсторонней очереди, каждый из которых функционирует как стек. Для очередей с приоритетом и DEPQ, однако, удаление из очереди и постановка в очередь часто занимают время O (log n) (например, если реализовано как двоичная куча ), в то время как производительность O (1) "peek" (здесь обычно называется «find-min» или «find-max») является ключевой желаемой характеристикой очередей с приоритетом, и, таким образом, просмотр почти всегда реализуется отдельно.
Для очереди, поскольку постановка и снятие с очереди происходят на противоположных концах, просмотр не может быть реализован в терминах базовых операций, и поэтому часто реализуется отдельно.
Одним из случаев, когда просмотр не является тривиальным, является тип упорядоченного списка (то есть элементы, доступные по порядку), реализованный самобалансирующимся двоичным деревом поиска. В этом случае find-min или find-max занимают время O (log n), как и доступ к любому другому элементу. Заставить find-min или find-max занять время O (1) можно путем кэширования минимальных или максимальных значений, но это увеличивает накладные расходы на структуру данных и операции добавления или удаления элементов.
