✔ 1. 큐란?

삽입과 삭제가 각각 양 끝에서 수행되는 자료구조이다. 먼저 들어온 데이터가 먼저 나가는 선입선출(FIFO, First-In-First-Out) 구조이다.

만약 배열로 큐를 만들경우, 새 원소들은 계속해서 뒤에 삽입되고 삭제는 맨 앞에서 이루어지기 때문에 배열의 오른쪽으로 원소들이 편향되는 문제가 발생한다. 따라서 원형큐를 이용해 해결한다.

✔ 2. 큐의 기능

• 삽입 : 큐의 맨 뒤(rear)에서 이루어진다.
• 삭제 : 큐의 맨 앞(front)에서 이루어진다. 맨 앞의 요소를 삭제하고 반환한다.
• 반환 : 큐가 비어있지 않으면 맨 앞의 요소를 삭제하지 않고 반환한다.

✔ 3. 원형큐

원형큐는 배열의 앞뒤를 연결한 것이다.

✔ 4. 큐 수행시간

• 상각분석(각 연산의 평균 수행시간) : O(1)
• 삽입/ 삭제 : O(1)
• overflow/underflow : O(N)

✔ 5. 데크(deque)란?

데크는 양쪽 끝에서 모두 삽입/ 삭제가 가능한 자료구조이다. 스택과 큐를 혼합하였기 때문에 스택과 큐를 동시에 구현하는데 사용된다.

데크의 원소들은 서로 가리키고 있기 때문에 이준연결리스트로 구현하게 되면 삽입/삭제가 가능하다.

✔ 6. 데크의 기능

• 삽입 : rear or front 요소를 추가한다.
• 삭제 : rear or front 요소를 삭제하고 반환한다.
• 반환 : rear or front 요소를 삭제하지 않고 반환한다.