필수 알고리즘 2 '큐' (정리 중)

큐(queue) 는 '줄을 서다'라는 뜻을 가지고 있다.
큐는 먼저 들어간 데이터가 먼저 나오는 자료 구조이다.
(맛집에서 먼저 줄을 서면 먼저 들어가는 것 같이!)

FIFO(First In First Out) 선입 선출
스택과 마찬가지로 큐도 삽입하는 연산을 push, 꺼내는 연산을 pop이라고 한다.

큐의 특성을 활용하는 분야

• 작업 대기열: 네트워크 통신을 할 때 다수의 클라이언트에서 서버에 작업을 요청하면 서버는 요청이 들어온 순서대로 처리한다. 이때 큐를 활용할 수 있다.
• 이벤트 처리: 어떤 애플리케이션이나 시스템에서 사용자의 이벤트, 예를 들어 키보드 입력이나 마우스 움직임을 처리할 큐를 활용할 수 있다.

큐 규현하기

1. shift() 메서드 사용하기

• push()메서드: 배열의 가장 마지막에 요소를 추가
• shift()메서드: 배열의 가장 첫 번째 요소를 삭제

위 두 메서드를 이용하면 큐의 선입선출(FIFO)를 흉내낼 수 있지만 shift()메서드의 시간 복잡도가 O(1)이 아니기 때문에 진짜 큐는 아니다.

2. 배열 이용하기

• 앞서 push()와 shift()메서드를 이용하여 큐를 흉내낼 수 있지만 아무리 최적화가 된다고 해도 진짜 큐의 성능을 따라갈 수는 없다.
• 만약 많은 요소를 다뤄야 하는 문제라면 shift()메서드를 사용하는 경우 문제가 될 수 있기 때문에 직접 큐를 구현하는 방식도 알아야 된다.
  먼저 배열을 이용하는 방식이다.

3. 연결 리스트 이용하기