자료구조 - 큐(queue), 간단한 코드로 파악하기

개념

큐(queue), 역시 스택과 비슷하게 데이터를 일시적으로 쌓아놓기 위한 자료구조입니다. 다만 차이점은 가장 먼저 넣은 데이터를 가장 먼저 꺼내는 선입선출(FIFO, First In First Out) 구조입니다. 실 생활에서 예를 들자면 마트의 대기열이나, 은행 창구에서 차례를 기다리는 순서라고 이해하면 편합니다. 

 

• enqueue : 인큐 라고 불리며, 큐에 데이터를 삽입하는 작업을 뜻합니다.
• dequeue : 디큐 라고 불리며, 인큐의 반대로 데이터를 꺼내는 작업을 뜻합니다.
• front : 프런트는 데이터를 꺼내는 out 쪽을 뜻합니다.
• rear : 리어는 데이터를 넣는 쪽을 뜻하며 back이라고도 불립니다.

 

출처 : https://namu.wiki/jump/PzEnQ9B%2FGHFFDNFU2SH6GbJm1j%2BhSof0VQ6QaaEhc5ERJl4Usjvv8kdeNk8GgwMOmOVmqeqpGEp9b1HavbyEqHXoZRH1kyTqTF6VwA1vGoo%3D

 

큐를 구현하기 쉬운방법은 역시 배열입니다. 

public class IntQueue {
	
    private int max; 	//큐의 용량
    private int front;	//첫번째 요소의 커서위치
    private int rear;	//마지막 요소의 커서위치
    private int num;	//현재 데이터의 갯수
    private int[] que;	//큐 본체
    
    public IntQueue(int capacity) {
    	num = front = rear = 0;
        max = capacity;
        try {
        	que = new int[max];
        } catch (OutOfMemoryError e) {
        	max = 0;
        }
    }

 

역시 먼저 생성자를 준비합니다. 이전 글에서는 Exception까지 준비했지만 이번엔 생략하겠습니다.

que는 비어있기때문에 num, front, rear 를 모두 0으로 초기화합니다.

또 매개변수 capacity는 전달받은 큐의 용량을 필드 max에  복사하고 요솟수가 max인 배열 que를 생성합니다. 

 

public int enque(int x) {
	
    que[rear++] = x;
    num++;
    if(rear == max){
    	rear = 0;
    }
    return x;
}

위 코드는 큐에 데이터를 삽입(인큐)하는  메소드입니다. 인큐에 성공하면 인큐한 값을 그대로 반환하며, 실패할 경우는 큐가 가득찰 경우입니다. 그리고 rear 와 max가 같아지는 경우를 방지하기 위해 rear == max 일 경우 리어값을 0으로 초기화하여 그 경우를 방지합니다.

 

public int deque() {

    int x = que[front++];
    num--; 
    if(front == max){
    	front = 0;
    }
    return x;
}

이 메소드는 큐에서 데이터를 꺼내는 메소드인 디큐입니다. 그리고 큐가 비어있어서 더 이상 디큐를 할 수 없을 경우 에러가 발생하며 차례대로 꺼내며 디큐를 진행합니다. 역시나 front 와 max의 위치가 같아질 경우를 방지하기 위해 0으로 초기화합니다. 

 

그외 메소드들..

//큐에서 데이터를 피크(front 데이터를 들여다보는 메소드)하기
public int peek() {
	if(num <= 0){
		 //error 
    }
    return que[front];
}

//큐에서 x를 검색하여 인덱스(찾지못한다면 -1을 반환)를 반환
public int indexOf(int x){
	for(int i=0; i<num; i++){
    	int idx = (i + front) % max;
        if(que[idx] == x)
        	return idx;
    }
    return -1;
}

//큐를 비우는 메소드
public void clear(){
	num = front = rear = 0;
}

//큐의 용량을 반환
public int capacity(){
	return max;
}

//큐에 쌓여있는 데이터의 갯수를 반환
public int size(){
	return num;
}

//큐가 비어있는지?
public boolean. isEmpty(){
	return num <= 0;
}

//큐가 가득 찼는지?
public boolean isFull(){
	return num >= max;
}

//큐안의 모든 데이터를 프론트 리어 순으로 출력
public void dump(){
	if(num <= 0) {
    	//que null error
    } else {
    	for(int i=0; i<num;  i++){
	        que[(i + front) % max];
        }
    }
}

 

이상으로 자료구조의 기본 개념중 하나인  큐 queue 에 대해 알아보았습니다.

자료구조를 알아야 보다 복잡한 문제해결을 할때 수월하게 접근하고 논리적인 해결방법을 찾을 수 있을거같습니다.