코딩 테스트 합격자 되기 - 4주차

큐

• 줄을 서다라는 뜻으로 FIFO 형식이다.

큐의 ADT

• 연산
  • boolean isFull()
  • boolean isEnpty()
  • void push(item Type item)
• 상태
  • int fromt
  • init rear : 최근에 푸쉬한 데이터의 위치를 기록합니다
  • itemType data(maxsize) : 큐의 데이터를 관리하는 배열, maxsize개의 데이터를 관리
• 큐의 세부동작

1. isFull() 연산으로 현재 큐가 가득 찼는지 확인

• 가득차지 않았으므로 rear+1한 다음 rear가 가리키는 위치에 푸쉬함

1. 이 상태로 팝을 한다면?

• isEmpty() 연산을 내부에서 수행
• 비어 있지 않다면 front +1 수행 -> 1번은 이미 진행한 상황이면 rear, front 모두 0으로 같아진다
• 이 경우 isEmpty() 연산을 다시 하면 큐가 민것으로 처리되며 실제 배열의 데이터를 삭제하지 않고도 데이터를 삭제한 것처럼 관리 가능

1. 큐의 끝까지 푸시 진행
2. 이제 큐가 가득 찼을 때 푸시하면 어떻게 될까?

• rear가 maxsize-1일 때와 같다. isFull() 상태와 같다

• front 이전 기준으로 큐의 사용할 수 있는 부분과 사용할 수 없는 부분으로 나뉘어져 있다

• 큐는 값이 들어간 순서대로 처리하는 경우에 사용된다.

  • 명절 기차표 예매
  • 예매 사이트에 먼저 접손한 인원부터 예매를 할 수 이씨게 됨
  • BFS도 큐를 사용한다.

문제