스택과 큐: 저장소가 아니라 순서 계약

입력 고정

1, 2, 3을 같은 순서로 넣어 자료구조 차이만 비교한다.

실험 조건 통일

push 1, push 2, push 3 뒤 pop 두 번은 3, 2를 돌려준다.

LIFO

enqueue 1, 2, 3 뒤 dequeue 두 번은 1, 2를 돌려준다.

FIFO

같은 그래프라도 스택은 깊이 우선, 큐는 레벨 순서 탐색으로 이어진다.

DFS/BFS 분기

연산 이름

push/pop과 enqueue/dequeue를 분리 이름이 비슷해도 꺼내는 위치가 다르므로 테스트 기대값도 달라진다.

pop: top, dequeue: front

빈 구조

underflow 정책을 명시 예외, null/None, -1 중 하나를 문제 조건에 맞춰 끝까지 유지한다.

정책 미정은 런타임 버그

구현 비용

큐 앞 삭제 비용을 확인 배열 pop(0)은 O(N)이 될 수 있어 head index나 deque를 선택한다.

계약은 같아도 비용은 다름

용량 제한

overflow 정책을 추가 계약으로 둠 drop-oldest, drop-newest, block 중 서비스 의미와 데이터 손실 허용도를 맞춘다.

무한 큐 가정 금지

정상 순서 1,2,3 삽입 후 두 번 꺼낸 결과가 스택 3,2 / 큐 1,2인지 본다.

빈 구조 모두 꺼낸 뒤 한 번 더 꺼낼 때 약속한 예외나 특수값이 나오는지 확인한다.

교체 구현 배열, 연결 리스트, deque로 바꿔도 외부 API 결과가 같아야 ADT가 지켜진다.