큐 (Queue)
- 가장 먼저 들어간 자료가 가장 먼저 나오는 자료구조
- 먼저 들어온 데이터가 먼저 나가는 선입선출(FIFO: First-In First-Out)의 특성을 갖는 자료구조
후단 (rear) vs 전단 (front)
- 후단: 삽입이 일어나는 곳
- 전단: 삭제가 일어나는 곳
큐의 사용 예제
- 컴퓨터의 빠른 CPU와 속도가 상대적으로 느린 주변장치(프린터)들 사이의 시간이나 속도 차이를 극복하기 위한 임시 기억 장치로 사용된다.
큐의 연산
- enqueue(e): 새로운 요소 e를 큐의 맨 뒤에 추가; 포화 상태인 경우 오버플로 발생.
- dequeue(): 큐의 맨 앞에 있는 요소를 꺼내서 반환; 공백 상태인 경우 언더플로 발생.
- isEmpty(): 큐가 비어있는지 검사
- isFull(): 큐가 가득 차있는지 검사
- peek(): 큐의 맨 앞에 있는 요소를 삭제하지 않고 반환
- size(): 큐에 들어있는 전체 요소의 수를 반환
선형 큐
- 용령이 5인 큐에 A~E까지 가득차있고 2번의 삭제를 순서대로 수행헀다.
- 여기서 더 삽입하려면, 큐의 앞부분에 공간이 있는데로 rear인 후단을 증가시킬 수 없으므로 삽입 불가능.
- 따라서, 큐의 요소들을 모두 최대한 앞으로 옮겨, 후단에 공간을 확보한 다음 삽입해야된다.
- 동작을 이해하기에는 쉬우나, 요소들의 이동이 필요하므로 효율적이지 않다.
원형 큐
- 인덱스인 rear 후단과 front 전단을 원형으로 회전시키는 개념
- 이를 테면, enqueue([요소])가 호출되면 rear 후단을 시계 방향으로 1칸 회전시키고 그 위치에 [요소]를 저장하는 것.
- 시계방향의 회전 구현: front나 rear가 계속 증가하다가 용량이 같아지면 인덱스 0으로 만들기
- 전단 회전: front ← (front+1) % capacity
- 후단 회전: rear ← (rear+1) % capacity
링 버퍼(ring buffer)
- 오래된 자료를 버리고 항상 최근의 자료를 유지하는 용도로 사용.
- 이를 테면, 최대 7개의 요소를 저장할 수 있는 원형 큐에 7개 이상의 자료들이 연속적으로 입력되었을 때,
가장 최근에 들어온 7개만 저장되도록 하고 오래된 데이터는 버리는 것.
- 기존의 원형인 큐에서는 포화상태일시, 산입연산을 추가로 수행하면 오버플로가 발생하나
링 버퍼에서는 원형 큐의 enqueue 함수 작동방식을 약간 수정하여 포화 상태와 상관없이 항상 삽입 가능.
- 즉, 가장 오래된 데이터를 삭제해서 큐를 계속 포화 상태로 유지.
- 프로세스
- 공백 상태 (capacity=8)
- 공백 상태에서 7개의 요소를 삽입하면 포화 상태가 됨
- 포화 상태에서 새로운 데이터 7을 삽입하면 가장 오래된 요소 0이 삭제됨
- 같은 방법으로 8을 삽입하게 된다면, 가장 오래된 요소 1이 삭제됨
덱 (Deque)
- double-ended queue
- 전단과 후단에서 모두 삽입과 삭제 가능한 큐
- 그러나 여전히 중간에 삽입하거나 삭제하는 것은 허용하지 않음
덱의 연산
- addFront(e): 새로운 요소 e를 전단에 추가
- addRear(e): 새로운 요소 e를 후단에 추가
- deleteFront(): 덱의 전단 요소를 꺼내서 반환
- deleteRear(): 덱의 후단 요소를 꺼내서 반환
- getFront(): 덱의 전단 요소를 삭제하지 않고 반환
- getRear(): 덱의 후단 요소를 삭제하지 않고 반환
- isEmpty(): 덱이 비어있는지 검사
- isFull(): 덱이 가득 차있는지 검사
- size(): 덱에 들어있는 전체 요소의 수를 반환
덱의 연산 vs 스택의 연산
- 덱의 addRear, deleteFront, getFront 연산은 각각 큐의 enqueue, dequeue, peek 연산과 동일하다
- 덱의 후단(rear)을 스택의 상단(top)으로 사용한다면,
덱의 addRear, deleteRear, getRear 연산은 스택의 push, pop, peek 연산과 정확히 동일하다.
덱의 deleteRear, addFront 연산
- 원형 큐의 enqueue나 dequeue 연산과는 달리 인덱스를 하나씩 줄여야하는데,
이것은 반시계 방향 회전을 의미한다.
- 이를 위한 인덱스 처리는 나머지 연산을 이용해 간결히 가능
- 전단 회전(반시계 방향): front ← (front-1+capacity) % capacity
- 후단 회전(반시계 방향): rear ← (rear-1+capacity) % capacity