[Data Structure] 큐(Queue)란?

큐(Queue) 란?

 

Queue는 차례를 기다리는 사람이나 승용차의 열 이라는 의미도 가지고 있는데, 이런 대기열은 줄을 선 순서대로 앞에서 부터 빠져나가게 된다. 

 

이처럼 큐는 나중에 집어넣은 데이터가 먼저나오는 스택과는 반대되는 개념으로, 가장 먼저 들어온 데이터가 가장 먼저 나가게 되는 구조이다.

 

따라서 큐는 '선입선출 방식의 자료구조', 또는 'FIFO(First in First Out)의 자료구조 라고 한다.

 

데이터를 넣는 것은 Enqueue, 반대로 데이터를 꺼내는 것을 Dequeue 라고 하며

새로운 데이터가 들어가는 위치는 가장 뒤인 Back에 들어가게되고, 데이터 나가는 위치는 가장 앞인 Front에서 꺼낸다.

 

 

큐 연산

- enqueue : 큐에 데이터를 저장함

- dequeue : 큐의 가장 앞 데이터를 꺼냄 (삭제)

- peek : 큐의 가장 앞 데이터를 꺼내되(반환), 삭제하지 않음

- isEmpty : 큐가 빈 경우 TRUE(1)을, 그렇지 않은 경우 FALSE(0)을 반환

 

 

큐의 종류

선형 큐

- 크기가 제한되어 있음

- 빈 공간을 사용하려면 모든 자료를 꺼내거나 데이터를 한 칸 씩 옮겨야함

- 마지막 배열에 도달 했을 때, 실제로는 데이터 공간이 남아있지만 오버플로우가 발생함.

 

원형 큐(환형 큐)

- 선형 큐의 문제점을 보완한 것

- front가 큐의 끝에 닿으면(배열의 맨 마지막 부분을 쓰게되면) 큐의 맨 앞으로 자료를 보내어(다시 배열의 제일 처음부터 큐를 채우는 식) 원형으로 연결하는 방식.

 

링크드 큐(연결리스트로 구현한 큐)

- 큐의 길이를 쉽게 늘릴 수 있음

- 오버플로우가 발생하지 않음

- 삽입과 삭제가 제한되지 않음

 

 

 

자바(java)에서 큐 클래스 사용.

 

가장먼저 큐의 클래스 인스턴스를 생성하기 위해서 LinkedList() 생성자를 호출해준다.

Queue q = new LinkedList();

 

위에서 만든 큐에 접근하기 위한 메소드들은 아래와 같다.

 

- boolean offer() : - enqueue 역할. 큐에 객체를 넣는다.

- poll() : dequeue 역할. 큐에서 데이터를 꺼내온다. 없을 시 null 반환

- peek() : 큐의 가장 앞 데이터를 꺼내되(반환), 삭제하지 않음.