[자료구조] Queue

Queue란?

먼저 들어간 자료가 먼저 나오는 FIFO(First In First Out) 형식의 자료구조

스케줄링, 탐색 알고리즘 등에 활용됨

 

• Put : 큐에 데이터를 넣음
• Get : 큐에서 데이터를 꺼냄
• Front : 큐의 가장 앞쪽. 즉, 데이터를 Get할 수 있는 위치를 의미함
• Rear : 큐의 가장 뒤쪽. 즉, 데이터를 Put할 수 있는 위치를 의미함
• 큐에도 Overflow, Underflow가 발생할 수 있음.

 

Queue의 종류

• 선형 : 막대 모양으로 된 큐
• 환형 : 선형 큐의 문제점을 보완한 큐*. Front가 큐 끝에 닿으면 큐 맨 앞으로 데이터를 보내 원형으로 연결함

* 배열로 데이터 추가/삭제를 반복하다보면 마지막 배열에 도달 후, 데이터 공간이 있어도 데이터를 넣을 수 없음. 즉, 스택오버플로우가 발생할 수 있음. Linked List를 이용할 경우 길이를 쉽게 늘릴 수 있어 스택오버플로우가 발생하지 않음.

 

 

Queue 구현방법

• 배열
  1. 큐 선언, Front와 Real를 0으로 설정
  2. 데이터를 추가할 땐 Real에 1을 더한 위치에 데이터를 넣어줌
  3. 데이터를 뺄 땐 Front에 1을 더해 앞에서 값이 빠진 것을 표현
• Linked List
  1. 데이터를 추가할 땐 추가할 노드를 리어가 가리키는 노드로 변경해줌
  2. 데이터를 뺄 땐 이전 프론트가 가리키던 다음 노드를 가리킴

 

 

 

참고 | Wikipedia, fast campus 컴퓨터공학 전공 필수