[자료구조] Queue

❓ Queue 란?

---

• 선입 선출(FIFO) 프로토콜을 구현하는 자료 구조
• 원소의 삽입은 큐의 뒤에서 수행, 원소의 제거는 앞에서 수행

== 삽입과 삭제가 양 끝에서 각각 수행되는 자료구조

 

 

❓ Queue 연산

---

1) Add: 주어진 원소를 큐의 뒤에 삽입

2) First: 큐가 공백이 아니면, 큐의 앞에 있는 원소 return

3) Remove: 큐가 공백이 아니면, 큐의 앞에 있는 원소를 삭제해서 return

4) Size: 큐에 있는 원소의 수 return

 

 

❓ Queue구현

---

• 배열 기반 구현
  
  
• linkedlist 기반 구현
  -> 구현이 더 빠름 (삽입과 삭제를 위한 위치가 항상 동일하게 뒤와 앞이기 때문)
  -> 공간을 낭비하지 않는다. (제거된 노드가 자동 쓰레기 수집 프로세서에 의해서 삭제되기 때문)
  = Queue by Singly Linked List
  = Queue by Double Linked List

 

 

 

❓ Queue 응용

---

- 클라이언트/서버 시스템_톨게이트 구현