Peek(데이터 유형 작업)

컴퓨터 과학에서 peek는 특정 추상 데이터 유형, 특히 스택과 큐와 같은 순차적 수집에 대한 작업으로, 수집에서 요소를 제거하지 않고 수집의 상단("전면") 값을 반환한다. 따라서 "팝"이나 "디큐어"와 같은 운영과 동일한 값을 반환하지만, 데이터를 수정하지는 않는다.

"peek"라는 이름은 스택의 기본 "push" 및 "pop" 작업과 유사하지만, 이 작업의 이름은 데이터 유형과 언어에 따라 다르다. Peek은 일반적으로 데이터를 추가하고 제거하는 보다 기본적인 작업에 비해 필수적이지 않은 작업으로 간주되며, 따라서 이러한 데이터 유형의 기본 정의에는 포함되지 않는다. 그러나 유용한 작업이고 일반적으로 쉽게 구현되기 때문에 자주 연습에 포함되며, 일부 정의에서 peek는 pop(또는 아날로그)이 peek로 정의되어 기본으로 포함된다. 추상적 정의를 참조한다.

데이터 유형

자주 피크가 구현되는 순차적 유형:

• 쌓다
• 큐
• 우선 순위 대기열(예: 힙)
• 더블 엔드 큐(디큐)
• 이중 엔드 우선 순위 대기열(DEPQ)

스택과 같은 단일 엔드 유형은 일반적으로 수정된 끝에서 한 번만 엿볼 수 있다. 데키와 같은 더블 엔드 유형은 양쪽 끝에 하나씩, 두 개의 피크를 허용한다.

엿보기 위한 이름은 다양하다. 스택의 경우 "픽" 또는 "탑"이 일반적인 반면, 대기열의 경우 "전면"이 일반적이다. 디키에 대한 운영은 다양한 명칭을 가지고 있는데, 종종 "앞면"과 "뒤면" 또는 "첫 번째"와 "마지막"으로 불린다. "정점, 정상"이라는 뜻에서 "피크"라는 명칭도 가끔 발견되지만, 이는 동사 "피크"의 철자 오류로도 발생한다.

추상적 정의

직관적으로 peek은 pop과 같은 값을 반환하지만 데이터는 변경하지 않는다. 수집이 비어 있을 때의 동작은 다양하다 – 대부분의 경우 이는 빈 수집의 팝과 동일하게 언더플로 오류를 발생시키지만, 일부 구현은 대신 단순히 반환(오류 없이)하는 기능을 제공하며, 기본적으로 구현된다. if isempty then return, else peek.

이 행동은 여러 가지 방법으로 공리화될 수 있다. 예를 들어 스택에 대한 일반적인 VDM(Vienna Development Method) 설명은 top(pek)을 정의하고 ematic으로 제거하는데, 여기서 top은 top 값을 반환하지 않고(stack을 수정하지 않고), stack을 수정한다(값을 반환하지 않음).^[1] 이 경우 팝은 상단 및 제거 측면에서 정의된다.

또는 pop이 주어진 경우 연산 peek는 다음과 같이 공리화할 수 있다.

peek(D) = pop(D)

Peek(D), D = D

"팝과 동일한 값" 및 "기본 데이터를 변경하지 않음"(피크 전과 동일하게 피크한 후 데이터 값)을 의미한다.

실행

Peek은 일반적으로 O(1) 시간이 걸리고 추가 공간이 없는 간단한 루틴에서 팝 연산의 단순한 변형에 의해 매우 쉽게 구현될 수 있다. 대부분의 순차적 데이터 유형은 종단에 대한 참조를 포함하는 데이터 구조에 의해 구현되며, 따라서 피크는 단순히 이것을 무시함으로써 구현된다. 그러나 어떤 경우에는 그것이 더 복잡하다.

스택과 같은 일부 데이터 유형의 경우, 더 많은 기본 작업 측면에서 복제할 수 있지만, 대기열과 같은 다른 데이터 유형의 경우 복제할 수 없다. 피크를 다른 조작의 관점에서 복제할 수 있다 하더라도, 이것은 데이터 수정을 피하고, 단순히 "팝"(또는 유사 연산)과 같은 값을 반환하지만, 그 다음에는 데이터를 수정하지 않는 것으로 구성되어 있기 때문에, 그것을 별도로 구현하는 것이 거의 항상 더 효율적이다.

스택, 우선 순위 큐, 디큐 및 DEPQ 유형의 경우 peek를 pop 및 push 측면에서 구현할 수 있다(동일 엔드에서 수행되는 경우). 스택과 디키의 경우, 이러한 작업은 대부분의 구현에서 O(1)이고 메모리 할당(데이터 크기를 줄임으로써)이 필요 없기 때문에 일반적으로 효율적이다. 디큐의 양 끝은 각각 스택으로 기능한다. 그러나 우선순위 대기열과 DEPQ의 경우, 디큐링과 인큐레이션은 종종 O(log n)시간(예를 들어 바이너리 힙으로 구현되는 경우)이 걸리는 반면, O(1)의 성능은 우선순위 대기열의 주요 원하는 특성(여기서 일반적으로 "find-min" 또는 "find-max"라고 함)이므로 피크는 거의 변함없이 별도로 구현된다.

큐의 경우, 엔큐링과 디큐어링이 반대쪽 끝에서 발생하기 때문에, 피크는 기본 조작의 관점에서 구현될 수 없으므로, 별도로 구현되는 경우가 많다.

피크가 사소한 것이 아닌 경우 중 하나는 자체 균형 이진 검색 트리에 의해 구현된 순서 목록 유형(즉, 순서대로 액세스할 수 있는 요소)에 있다. 이 경우 find-min 또는 find-max는 다른 요소에 대한 액세스와 마찬가지로 O(log n) 시간이 걸린다. find-min 또는 find-max take O(1) 시간은 최소값 또는 최대값을 캐싱하여 수행할 수 있지만, 이는 데이터 구조와 요소 추가 또는 제거 작업에 오버헤드를 추가한다.

참조