[Computer Science] 큐(Queue), 덱(Deck)

큐(Queue)

• 선입선출 (FIFO - First In First Out)
• Rear : 가장 뒤 ( 데이터가 들어오는 위치)
• Front : 가장 앞 ( 데이터가 나가는 위치)
• ex) 버스를 기다리는 줄, 은행에서 업무를 보기위해 기다리는 줄 등등
  • Enqueue : 큐 맨 뒤에 어떠한 요소를 추가, 마지막으로 온 손님에게 번호표 발부
  • Dequeue : 큐 맨 앞쪽의 요소를 삭제, 창구에서 서비스를 받은 손님의 번호표를 대기목록에서 삭제
  • Peek : front에 위치한 데이터를 읽음, 다음 서비스를 받을 손님이 누구인지 확인
  • front : 큐의 맨 앞의 위치(인덱스), 다음 서비스를 받을 손님의 번호
  • rear : 큐의 맨 뒤의 위치(인덱스), 마지막에 온 손님의 번호

선형큐

• 1차원 배열을 이용
• 인덱스를 값으로 가지는 front, rear라는 두개의 변수와 큐 사이즈를 나타내는 n이라는 변수 사용
• front, rear 가 -1 일 때 , front==rear → 큐가 비어있는 상태(empty)
• rear==n-1 일 때 → 큐가 꽉 찬 상태 (full)

---

선형큐의 문제점

• 큐에 삽입이 되면 rear가 증가하게 된다. 그러다 결국 full상태(rear==n-1)가 된다.
• 하지만 이 때 큐에 원소가 꽉 차있지 않을 수 있다. 만약 front에서 삭제가 일어났다면 그만큼 공간이 남기 때문이다.생각하기 때문이다.
• →→이렇게 되면 앞에 남아있는 공간을 활용할 수 없다. 공간이 비어있는데도 불구하고 full상태라고

이를 해결하기 위해서는 원형큐를 사용하거나 큐에 저장된 모든 데이터를 큐의 앞쪽으로 옮기는 shifting연산이 필요하다. 하지만 큐의 크기가 1,000,000라면 최대 999,999번의 자료를 이동시켜야 하기 때문에 매우 비효율적이다.

원형큐(Circualr Queue)

• 원형큐는 선형큐에서 Dequeue 연산이 반복될 수록 큐에 저장할 수 있는 공간이 감소하는 문제점을 극복하기위해 고안
• front가 위치한곳은 절대로 데이터가 들어올 수 없다- (rear+1) % size == front 를 이용하기 때문이다.
• 삽입 → (rear+1)%Size == front 배열 포화상태
• 삭제 → front == rear 배열 비어있는 상태

• (rear+1)%4 == front 검사

• (rear+1)%4 == front 검사 → 더이상 못넣음

우선순위큐

• Dequeue를 할 때 들어온 순서가 아닌 우선순위에따라 Dequeue를 한다.
• 일반 Queue라면 1 → 4 → 3 → 7 순으로 큐에 삽입을 했다면 들어간 순서대로 Dequeue가 된다. 하지만 큐의 우선순위가 높은숫자가 먼저라면 7→ 4 → 3 → 1 순으로 Dequeue가 된다.
• 보통 힙을 이용하여 만든다.(최대 힙 → 최댓값우선, 최소 힙 → 최소값 우선)

큐의 쓰임

• 너비 우선 탐색
• 우선순위가 같은 작업 예약
• cpu 스케쥴링 : multitasking 환경에서 프로세스들은 큐에서 cpu가 할당되기를 기다린다

덱

• 큐의 앞쪽과 뒤쪽에서 삽입과 삭제가 모두 가능한 자료구조이다.
• 그러나 실제로 양쪽의 입력과 출력을 모두 사용하는 경우는 별로 없다.
• 큐를 구현했는데 나는 양쪽에서 출력하고싶다!!!! 하거나 스택에서 양쪽에서 입력하고싶다!!! 할때 사용
• push_front() : 덱의 앞에 자료를 넣는 연산
• pop_front() : 덱의 앞에서 자료를 빼는 연산
• push_back() : 덱의 뒤에 자료를 넣는 연산
• pop_back() : 덱의 뒤에서 자료를 빼는 연산
• front() : 덱의 가장 앞에 있는 자료를 보는 연산
• back() : 덱의 가장 뒤에 있는 자료를 보는 연산