[알유] 큐

큐(Queue)

큐는 스택과 마찬가지로 데이터를 일시적으로 쌓아 두기 위한 자료구조이다. 큐는 선입선출(FIFO, First In First Out)의 구조로 되어있으며, 큐에 데이터를 저장하는 작업을 인큐(enqueue)라 하고, 데이터를 꺼내는 작업을 디큐(dequeue)라고 한다. 또 데이터를 꺼내는 쪽을 프런트(front)라 하고, 데이터를 넣는 쪽을 리어(rear)라고 한다.

큐를 배열을 사용하여 구현할 수 있긴하지만 디큐할 시 배열의 요소들을 재정렬해야하므로 시간 복잡도가 O(n)이라 비효율적이다.

링 버퍼(ring buffer)

링 버퍼는 배열의 처음과 끝이 연결되어있는 자료구조이다. 논리적으로 어떤 요소가 첫 번째 요소이고 어떤 요소가 마지막 요소인지 확인하기 위한 변수가 프런트(front)와 리어(rear)이다. 링 버퍼를 이용해 큐를 구현하면 디큐의 처리 복잡도도 O(1)이 된다.

링 버퍼로 큐 구현해보기

여러 메소드들이 있지만 간단하게 구현해보기 위해 필수적으로 있어야 할 enque, deque, peek 메소드 세 개를 구현해보자.

public class Queue {
	private int size; // 사이즈
	private int front; // 맨 앞 요소 커서
	private int rear; // 맨 뒤 요소 커서
	private int num; // 현재 데이터 수 
	private int[] que; // 큐 본체
	
	
	// 생성자
	public Queue(int size) {
		num = front = rear = 0;
		this.size = size;
		que = new int[size];
	}
	
	public int enque(int x) {
		if(num >= size) System.out.println("큐가 가득 찼습니다.");
		que[rear++] = x;
		num++;
		if(rear == size) rear = 0;
		System.out.println(x + " 인큐 성공!");
		return x;
	}
	
	public void deque() {
		if(num <= 0) System.out.println("큐가 비어있습니다.");
		int x = que[front++];
		num--;
		if(front == size) front = 0;
		System.out.println(x + " 디큐 성공!");
	}
	
	public int peek() {
		if(num <= 0) System.out.println("큐가 비어있습니다.");
		return que[front];
	}
	
	public static void main(String[] args) {
		Queue que = new Queue(5);
		que.enque(30);
		que.enque(40);
		System.out.println("peek() : " + que.peek());
		que.enque(50);
		que.deque();
	}
}

위의 코드를 실행하면 다음과 같이 출력된다.

---

java에서 제공하는 Queue 클래스

자바에서 큐는 Deque 인터페이스를 구현한 LinkedList를 활용하여 생성한다. 따라서 스택과는 다르게 import 구문이 두 개가 추가로 필요하다.

import java.util.LinkedList;
import java.util.Queue;

그리고 다음과 같이 큐를 선언한다.

Queue<Integer> queue = new LinkedList<>();

• 메소드 종류
  • add() : 큐의 맨 뒤에 전달된 요소를 삽입한다. 만약 삽입에 성공하면 true를 반환하고, 실패하면 IllegalStateException을 발생시킨다.
  • element() : peek()와 같은 기능으로 해당 큐의 맨 뒤에 있는 요소를 반환한다.
  • offer() : 해당 큐의 맨 뒤에 전달된 요소를 삽입한다.
  • peek() : 해당 큐의 맨 앞에 있는 요소를 반환한다. 만약 큐가 비어있다면 null을 반환한다.
  • poll() : 해당 큐의 맨 앞에 있는 요소를 반환하고, 해당 요소를 큐에서 제거한다. 만약 큐가 비어있으면 null을 반환한다.
  • remove() : 해당 큐의 맨 앞에 있는 요소를 제거한다.
    
    
    

import java.util.LinkedList;
import java.util.Queue;

public class que {
	public static void main(String[] args) {
		Queue<Integer> que = new LinkedList<>();
		
		System.out.println("add() : " + que.add(10));
		System.out.println("add() : " + que.add(20));
		System.out.println("offer() : " + que.offer(30));
		System.out.println("offer() : " + que.offer(40));
		System.out.println("peek() : " + que.peek());
		System.out.println("element() : " + que.element());
		System.out.println("poll() : " + que.poll());
		System.out.println("remove() : " + que.remove());
		
		
		System.out.print(que);
	}
}

위의 코드를 실행하면 다음과 같이 출력된다.

---

• 참고 : Do it 자료구조와 함께 배우는 알고리즘 입문 자바 편
• 참고 : TCP SCHOOL