ADT contract

스택과 큐는 저장 공간보다 꺼내는 순서가 다르다

같은 값 1, 2, 3을 넣어도 pop/dequeue가 바라보는 끝이 달라 DFS와 BFS의 탐색 순서까지 갈라진다.

공통 입력

1

2

3

Stack

마지막 입력부터 pop

3top, 먼저 나온다

2두 번째

1바닥

31st pop

22nd pop

13rd pop

Queue

첫 입력부터 dequeue

1
front

2

3
rear

11st dequeue

22nd dequeue

33rd dequeue

구분	계약	알고리즘 영향
스택	top 하나만 보고 넣고 뺀다.	깊은 후보를 먼저 따라가므로 DFS가 된다.
큐	front에서 빼고 rear에 넣는다.	먼저 발견한 후보부터 처리하므로 BFS가 된다.
검증	같은 입력에서 결과 순서를 비교한다.	구현체를 바꿔도 외부 결과가 같아야 ADT가 지켜진다.