Operations and Semantics | Data Structure | Pusan National University

스택(stack)push(x)로 맨 위에 추가하고 pop()으로 맨 위 원소를 삭제해 반환한다.

큐(queue)enqueue(x)로 뒤쪽에 추가하고 dequeue()로 앞쪽 원소를 삭제해 반환한다.

덱(deque)앞쪽과 뒤쪽 모두에서 추가하고 삭제한다.

우선순위 큐(priority queue)접수 순서가 아니라 우선순위로 삭제할 원소를 고른다.

연산을 고르면 삭제될 원소와 다음 상태가 바뀐다

스택·큐·덱은 [4, "dog", True]에서, 우선순위 큐는 인쇄 작업 세 건에서 시작한다. 초록 칸은 지금 삭제 연산을 호출하면 나올 원소다.

ADT

연산

앞쪽

뒤쪽

4, dog, True를 차례로 추가한 같은 상태에서 첫 삭제 연산만 바꾼다.

스택 · pop()

[4, "dog", True] → [4, "dog"]

가장 최근에 추가한 True를 반환한다.

큐 · dequeue()

[4, "dog", True] → ["dog", True]

가장 먼저 추가한 4를 반환한다.

덱 · 같은 끝과 다른 끝

add_last + remove_last · add_last + remove_first

같은 끝에서 추가하고 삭제하면 스택, 서로 다른 끝을 쓰면 큐와 같은 삭제 순서가 된다.

최근 기록을 먼저 꺼내야 하면 스택, 먼저 접수한 값을 먼저 꺼내야 하면 큐의 연산 의미가 맞는다.