Java 자료구조(Data Structure) - 큐(Queue)

Queue 란?

큐(Queue)는 사전적인 의미로 줄을 서서 기다리다, 대기 행렬 이라는 뜻으로 볼 수 있다. 톨게이트를 나란히 지나가는 자동차들을 큐 자료구조의 데이터로 비유할 수 있다. 가장 먼저 진입한 자동차가 가장 먼저 톨게이트를 통과한다. 다시말해 가장 나중에 진입한 자동차는 먼저 도착한 자동차가 모두 빠져나가기 전까지 톨게이트를 빠져나갈 수 없다. 

 

Queue의 구조

자료구조 Queue는 Stack과 상반되는 개념으로 먼저 들어간 데이터가 먼저 나오는 FIFO(First IN First Out) 혹은 LILO(Last In Last Out) 특징을 가지고 있다. Queue에 데이터를 넣는 것은 enqueue, 꺼내는 것을 dequeue 라고 한다.

 

Queue의 특징

• FIFO(First In First Out)
  먼저 들어간 데이터가 제일 처음에 나오는 선입선출 구조를 가지고 있다.

예1) 1, 2, 3, 4를 큐에 차례대로 넣는다.

Queue<Integer> queue = new LinkedList<>(); //int형 queue 선언

queue.add(1);     // queue에 값 1 추가
queue.add(2);     // queue에 값 2 추가
queue.add(3);     // queue에 값 3 추가
queue.add(4);     // queue에 값 4 추가

						   queue.add(데이터)
출력 방향 <---------------------------< 입력 방향
				     1 <- 2 <- 3 <- 4
				<---------------------------<
들어간 순서대로, 1번이 제일 먼저 들어가고 4번이 마지막으로 들어가게 된다.

예2) 큐가 빌 때까지 데이터를 전부 빼낸다.

queue.poll();       // queue에 첫번째 값을 반환하고 제거
queue.poll();
queue.poll();
queue.poll();

						   queue.poll()
출력 방향 <---------------------------< 입력 방향

				<---------------------------<
1, 2, 3, 4
제일 첫 번째 있는 데이터부터 차례대로 나오게 된다.

• 데이터는 하나씩 넣고 뺄 수 있다.
• 두 개의 입출력 방향을 가지고 있다.

Queue 자료 구조의 장정 

1. 자료를 먼저 넣은 순서대로 데이터를 꺼내 처리할 수 있다. 이러한 자료 구조의 특징으로 처리해야 할 작업이 여러 개 있을 경우 효율적인 처리가 가능하다.
   Queue는 선입선출 원칙을 따르기 때문에 가장 먼저 삽입된 데이터가 가장 먼저 삭제되고, 가장 나중에 삽입된 데이터는 가장 나중에 삭제된다. 이러한 구조로 인해 처리해야 할 데이터나 작업을 차례로 처리할 수 있다.
   Queue의 가장 앞에는 가장 오래전에 삽입된 데이터가 위치하고 가장 뒤에는 가장 최근에 삽입된 데이터가 위치한다. 즉 Queue에 데이터를 삽입하는 순서와 삭제하는 순서가 동일하게 유지되어야 한다.
   이러한 구조는 데이터 처리나 작업 처리에서 순서가 중요한 경우 유용하다. 예를 들어 프린터에서 인쇄 요청이 들어온 순서대로 처리해야 하는 경우, 은행에서 대기중인 고객 순서를 결정하는 경우, 채팅 시스템에서 메시지를 보내는 순서를 결정하는 경우 등에 Queue 자료 구조가 적용된다.
   
   
2. Queue는 삽입과 삭제가 각각 양 끝에서 이루어지며 원소를 삭제하는 연산이 없으므로 다른 자료 구조에 비해 빠른 속도를 보인다.
   Queue의 삽입과 삭제는 각각 Queue의 끝단에서 이루어지기 때문에, 중간에 있는 원소를 삭제하는 연산이 없다. 
   배열의 경우 중간에 있는 원소를 삭제하려면 삭제한 원소 이후의 모든 원소를 한칸씩 이동해야한다. 이 때문에 중간의 원소를 삭제한다면 이후의 배열을 복사하고 다시 순회하며 데이터를 삽입하는 과정을 거쳐야 한다. 삭제한 원소 뒤에 새로운 원소를 삽입하려면 빈자리를  만들기 위해 이후의 원소들을 한칸씩 뒤로 밀어야 하므로 삽입 연산에서도 전체 배열을 순회해야 한다.
   반면 Queue에서는 삽입 연산은 Queue 끝단에서 새로운 원소를 추가하는 것으로 끝나며, 삭제연산은 Queue의 첫 번째 원소를 삭제하는 것으로 끝난다. 따라서 Queue에서의 삽입과 삭제 연산은 단 한 번의 실행만으로 처리할 수 있다.
   이러한 이유로 Queue는 삽입과 삭제가 빈번하게 일어나는 상황에서 상대적으로 빠른 속도를 보이며 데이터나 작업을 차례대로 처리해야 하는 상황에서 효과적으로 사용될 수 있다.
   
   
3. 자바에서는 Queue를 기본 자료구조로 제공하기에 별도의 라이브러리나 모듈을 설치할 필요가 없다.
   자바에서는 따로 큐를 구현하지 않아도 이미 클래스가 구현되어있다. 자료구조의 특징과 메서드를 활용할 수 있다면 구현된 Queue 클래스를 바로 사용할 수 있다.
   
   

Queue<Integer> queue = new LinkedList<>(); //Integer형 queue 선언

queue.offer(1); // 큐에 새로운 데이터를 추가할 때는 add 메서드를 사용합니다.
---------------------------
queue -> [1]
---------------------------
queue.offer(2);
---------------------------
queue -> [1, 2]
---------------------------
queue.offer(3);
---------------------------
queue -> [1, 2, 3]
---------------------------

queue.poll(); // 큐에서 가장 처음에 들어온 데이터를 제거할 때는 poll 메서드를 사용합니다.
---------------------------
queue -> [2, 3]
---------------------------
queue.poll();
---------------------------
queue -> [3]
---------------------------

반응형

Queue 자료 구조의 단점

1. Queue는 자료 구조의 가장 앞에서 데이터를 꺼내는 연산과 가장 뒤에서 데이터를 추가하는 연산만 가능하기 때문에 중간에 있는 데이터를 조회하거나 수정하는 연산에는 적합하지 않다.
   Queue는 데이터를 가장 먼저 추가한 위치에서부터 차례로 데이터를 처리하며 가장 나중에 추가된 위치에서 새로운 데이터를 추가한다. 이러한 구조 때문에 Queue는 특정 위치의 데이터를 조회하거나 수정하는 연산에 적합하지 않다. 즉 Queue에서는 가장 앞에서 dequeue연산 으로 데이터를 삭제하거나 가장 뒤에서 enqueue연산 으로 데이터를 추가하는 것만 가능하다.Queue는 다른 위치의 데이터에 직접 접근하여 데이터를 변경하는 연산이 불가능하며 중간에 있는 데이터 조회도 불가능하다. 따라서 Queue는 데이터를 순차적으로 처리하는 데 적합한 자료 구조이다.
   
   
2. 크기제한이 없어서 메모리 낭비가 발생할 수 있다.
   Queue 인터페이스는 크기 제한이 없는 큐를 구현할 수 있도록 설계되어 있다. 이는 메모리 낭비의 가능성을 높이며 크기제한이 있는 큐를 구현할 때는 이를 직접 구현하거나 기존의 Queue 인터페이스를 상속받아 크기 제한을 추가한 클래스를 구현해야 한다.
   
   
3. iterator() 메서드가 지원되지 않는다.
   Queue 인터페이스는 iterator() 메서드를 지원하지 않는다. 이는 Queue 인터페이스가 FIFO(First In First Out) 구조를 갖기 때문이다. 따라서 큐의 데이터를 순회할 때는 peek() 메서드와 poll() 메서드를 사용하여 각각의 데이터를 차례대로 가져와야 한다.
   
   
4. remove(Object o) 메서드의 동작이 불명확하다.
   Queue 인터페이스에서 제공하는 remove(Object o) 메서드는 해당 객체를 큐에서 삭제한다. 그러나 이 메서드는 큐가 중복된 객체를 허용하는 경우 어떤 객체가 삭제되는지 명확하지 않다. 따라서 이 메서드를 사용할 때는 주의해야한다.
   
   

Queue의 실사용 예제

자료구조 Queue는 컴퓨터에서도 광법위하게 활용된다. 프린터에서 여러 문서를 순서대로 인쇄하려면 어떻게 해야할까?

우리가 문서를 작성하고 출력 버튼을 누르면 해당 먼서는 인쇄작업 Queue에 들어간다. 프린터는 인쇄작업 Queue에 들어온 문서를 순서대로 인쇄한다.

만약 Queue에 들어온 순서대로 출력하지 않는다면 인쇄물은 뒤죽박죽 일 것이다.

이 예시처럼 컴퓨터 장치들 사이에 데이터를 주고받을 때 각 장치 사이에 존재하는 속도의 차이나 시간 차이를 극복하기 위해 임시 기억장치의 자료구조로 Queue를 사용한다. 이것을 통틀어 버퍼(buffer)라고 한다.