자료구조 - 큐(Queue), 배열로 큐 만들기

큐는 스택과 마찬가지로 데이터를 일시적으로 쌓아 놓은 자료구조입니다.

하지만 가장 먼저 넣은 데이터를 가장 먼저 꺼내는 선입선출(FIFO: First In First Out) 인 점이 스택과 다릅니다.

 

 

큐 란?

 

큐(Queue)는 스택과 마찬가지로 데이터를 일시적으로 쌓아 두기 위한 자료구조입니다.

가장 먼저 꺼내는 선입선출 구조로 되어 있습니다.

생활에서 볼 수 있는 큐의 예는 은행 창구에서 차례를 기다리는 대기열이나 마트에서 계산을 기다리는 대기열을 들 수 있습니다.

 

스택과 마찬기로 큐는 배열을 사용하여 구현할 수 있습니다.

 

처음이 끝과 연결되었다고 보는 자료구조입니다.

여기서 논리적으로 어떤 요소가 첫 번째 요소이고 어떤 요소가 마지막 요소인지 식별하기 위한 변수가 프런트(front) 와 리어(rear) 입니다.

 

• 프런트(front): 맨 처음 요소의 인덱스
• 리어(rear): 맨 끝 요소의 하나 뒤의 인덱스(다음 요소를 인큐할 위치를 미리 지정)

 

쉽게 말해서, 맨 처음에 들어왔던 것을 프런트 처음으로 나갈 데이터를 프런트라 하며, 리어는 맨뒤에 에서 하나를 더한 인덱스를 표시하는 것은 프런트와 리어가 같을 때 비어 있는지? 가득 찼는지 확인하기 위한 것이다.

 

 

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;
        }
    }
}

 

큐로 사용할 배열(que)

 

데이터를 저장하기 위한 큐 배열입니다.

 

큐의 최대 용량(max)

 

큐의 최대 용량을 저장하는 변수입니다.

 

프런트(front)

 

큐를 만드는데, 데이터 첫번째 인덱스을 넣은 변수입니다.

 

리어(rear)

 

큐를 만드는데, 데이터 마지막 인덱스에서 하나의 더한 값을 넣은 변수입니다.

 

현재 데이터 수(num)

 

큐에 쌓아 놓은 데이터 수를 나타내는 필드입니다. front와 rear 의 값이 같은 경우 큐가 비어 있는지, 가득 찼는지 구별할 수 없는 상황을 피하기 위해 이 변수가 필요합니다.

큐가 비어 있을 때, num은 0 이고, 가득 찼을 때는 num과 max의 값이 같습니다.

 

 

생성자 IntQueue

 

생성자는 큐 본체용 배열을 생성하는 등의 준비 작업을 수행합니다. 생성 시 큐는 비어 있기 때문에 num, front, rear 값을 모두 0 으로 합니다. 또, 매개변수 capacity 로 전달받은 '큐의 용량'을 필드 max에 복사하고, 요솟수가 max인 배열 que의 본체를 생성합니다.

 

 

public int add(int x) {
    if (num >= max)
       System.out.println("꽉 찼습니다.");
    que[rear++] = x;
    num++;

    if(rear == max)
       rear = 0;

    return x;
}

 

 

인큐 메서드 add

 

큐에 데이터를 넣는 메서드입니다. 인큐에 성공하면 인큐한 값을 그대로 반환합니다.

 

 

public int poll() {
   if (num <= 0)
        System.out.println("데이터가 없네요;;");
   int x = que[front++];
   num--;

   if (front == max)
       front = 0;
        
   return x;
}

 

 

디큐 메서드 poll

 

큐에서 데이터를 디큐하고 그 값을 반환하는 메서드입니다. 

 

// 큐에서 데이터를 피크(프런트 데이터를 들여다 봄)
public int peek() {
    if (num <= 0)
        System.out.println("데이터가 없습니다.");;
    return que[front];
}

// 큐를 비움
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)
       System.out.println("큐가 비어 있습니다.");
    else {
       for(int i = 0 ; i < num ; i++)
           System.out.print(que[(i + front) % max]);
       System.out.println();
    }
}

 

 

피크 메서드 peak

 

앞으로 꺼낼 값을 보여줍니다. 다른곳에는 영향 없습니다.

 

 

모든 데이터를 삭제하는 메서드 clear

 

현재 큐의 모든 데이터를 삭제하는 메서드입니다.

 

 

최대 용량을 확인하는 메서드 capacity

 

큐의 최대 용량을 반환하는 메서드입니다.

 

 

데이터 수를 확인하는 메서드 size

 

현재 큐의 데이터 수를 반환하는 메서드입니다.

 

 

큐가 비어 있는지 판단하는 메서드 IsEmpty

 

큐가 비어 있는지 판단하는 메서드입니다. 비어 있으면 true, 그렇지 않으면 false를 반환합니다.

 

 

큐가 가득찼는지 판단하는 메서드 IsFull

 

큐가 가득 찼는지 판단하는 메서드입니다 .가득 찼으면 true, 그렇지 않으면 flase를 반환합니다.

 

 

모든 데이터를 출력하는 메서드 dump

 

큐에 인큐된 모든 데이터를 프런트에서 리어 순으로 출력하는 메서드입니다.

 

public class IntQueue {

    private int max;    // 큐의 용량
    private int front;  // 첫 번째 요소 커서
    private int rear;   // 마지막 요소 커서
    private int num;    // 현재 데이터 수
    private int[] que;  // 큐 본체

    public int add(int x) {
       if (num >= max)
          System.out.println("꽉 찼습니다.");
       que[rear++] = x;
       num++;

       if(rear == max)
          rear = 0;

       return x;
    }

    public int poll() {
        if (num <= 0)
            System.out.println("데이터가 없네요;;");
        int x = que[front++];
        num--;

        if (front == max)
            front = 0;

        return x;
    }

    // 큐에서 데이터를 피크(프런트 데이터를 들여다 봄)
    public int peek() {
        if (num <= 0)
            System.out.println("데이터가 없네요;;");
        return que[front];
    }

    // 큐를 비움
    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)
            System.out.println("큐가 비어 있습니다.");
        else {
            for(int i = 0 ; i < num ; i++)
                System.out.print(que[(i + front) % max]);
            System.out.println();
        }
    }

    public IntQueue(int capacity) {
        num = front = rear = 0;
        max = capacity;
        try {
            que = new int[max];
        } catch (OutOfMemoryError e) {
            max = 0;
        }
    }
}

 

import java.util.Scanner;

public class IntQueueTester {
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        IntQueue queue = new IntQueue(10);

        while(true) {
            System.out.println("현재 데이터 수 : " + queue.size() + " / " + queue.capacity());
            System.out.println("(1) 인큐    (2) 디큐   (3)  피크   (4)  덤프   (0)  종료 ");

            int menu = sc.nextInt();
            if (menu == 0 ) break;

            int x;
            switch(menu) {
                case 1:
                    System.out.println("데이터:");
                    x = sc.nextInt();

                    queue.add(x);
                    break;

                case 2:
                    x = queue.poll();
                    System.out.println("뺀 데이터는 " + x + "입니다.");
                    break;


                case 3:
                    x = queue.peek();
                    System.out.println("큐에 빠질 데이터는 " + x + "입니다.");
                    break;

                case 4:
                    queue.dump();
                    break;
            }
        }

    }
}