스택과 큐의 가장 큰 차이는 무엇인가?

데이터가 나가는 순서의 차이다. 스택은 마지막에 들어온 것이 먼저 나가고, 큐는 먼저 들어온 것이 먼저 나간다.

스택은 되돌리기(Undo)나 함수 호출 스택처럼 가장 최근의 상태를 기억해야 할 때 쓴다. 반면 큐는 프로세스 스케줄링이나 프린터 대기열처럼 순서대로 처리해야 할 때 적합하다.

두 구조 모두 삽입과 삭제의 시간 복잡도가 O(1)이다. 하지만 큐를 배열로 구현할 때 앞쪽 데이터를 지우면 나머지 데이터를 당겨야 하는 비용이 발생한다. 이를 위해 원형 큐를 주로 사용한다.