1. 큐 ADT

큐란?

선입선출(FIFO : First-In First-Out)

: 스택의 경우, 나중에 들어온 데이터가 먼저 나가는 구조인데 반하여 큐는 먼저 들어온 데이터가 먼저 나가는 구조

큐의 예로는 매표소에 표를 사기 위해 늘어선 줄을 들 수 있다

줄에 있는 사람들 중 가장 앞에 있는 사람이 가장 먼저 표를 사게 될 것이다. 그리고 나중에 온 사람들은 줄의 맨 뒤에 서야 할 것이다

 

 

큐는 뒤에서 새로운 데이터가 추가되고 앞에서 데이터가 하나씩 삭제되는 구조를 가지고 있다.

구조상으로 큐가 스택과 다른 점은 스택의 경우, 삽입과 삭제가 같은 쪽에서 일어나지만 큐에서는 삽입과 삭제가 다른 쪽에서 일어난다는 것이다.

후단 (rear)

:큐에서 삽입이 일어나는 곳

 

전단 (front)

: 큐에서 삭제가 일어나는 곳

---

큐의 추상 자료형

추상 자료형 큐의 연산들은 추상 자료형 스택과 아주 유사하다

• is_empty : 큐가 비어 있으면 TRUE를 반환하고 그렇지 않으면 FLASE를 반환
• is_full : 큐가 가득 찼으면 TRUE를, 그렇지 않으면 FALSE를 반환
• enqueue : 삽입 연산, 큐의 맨 뒤에 새로운 요소를 추가
• dequeue : 삭제 연산, 큐의 맨 앞에 있는 요소를 꺼내서 외부로 반환

---

큐의 활용

컴퓨터를 이용하여 현실 세계의 실제상황을 시뮬레이션 하는 곳

ex) 은행에서 기다리는 사람들의 대기열, 공항에서 이륙하는 비행기들, 인터넷에서 전송되는 데이터 패킷들을 모델링하는데 큐가 이용