큐(queue)

큐(queue)

먼저 삽입된 데이터가 먼저 추출되는 자료 구조

ex) 게임에서 대기 큐에서 먼저 대기한 유저가 먼저 매칭이 됩니다.

 

큐의 동작 원리

삽입3 삽입5

삭제(3번 삭제)

삽입7

삭제(5번 삭제)

삽입8

삭제(7번 삭제)

삽입2 삽입9

최종(8 2 9)

 

연결 리스트로 큐 구현

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

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

 

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

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

 

연결 리스트 삽입 연산

삽입할 떄는 꼬리(tail) 위치에 더이터를 넣는다.

 

연결리스트 삭제 연산

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