알고리즘 정리 - 큐

큐란?

- 큐(queue)는 먼저 삽입된 데이터가 먼저 추출되는 자료구조 (* 롤할때 말하는 '큐' 도 여기서 나온 뜻 같다!)

- 큐를 연결 리스트로 구현하면, 삽입과 삭제에 있어서 O(1) 을 보장할 수 있다.

- 연결 리스트로 구현할 때는 머리(head)와 꼬리(tail) 두 개의 포인터를 가진다.

 

1) 머리(head): 남아있는 원소 중 가장 먼저 들어 온 데이터를 가리키는 포인터

2) 꼬리(tail): 남아있는 원소 중 가장 마지막에 들어 온 데이터를 가리키는 포인터

 

삽입할 때는 꼬리(tail) 위치에 데이터를 넣는다

삭제할 때는 머리(head) 위치에서 데이터를 꺼낸다

---

예제)

전체 연산: 삽입 3 – 삽입 5 – 삭제 – 삽입 7 – 삭제 – 삽입 8 – 삭제 – 삽입 2 – 삽입 9

 

한쪽에선 삽입, 다른 한쪽에선 삭제를 진행한다

3

3 5

5

5 7

7

7 8

8

8 2

8 2 9

순서다