큐(Queue)

큐(Queue)

• 데이터를 일시적으로 쌓아 두기 위한 자료구조 
• 선입선출(First In First Out) 구조 
• 인큐(enqueue) - 데이터를 넣는 작업
• 디큐(dequeue) - 데이터를 꺼내는 작업 
• 프런트(front) - 데이터를 꺼내는 쪽 
• 리어(rear) - 데이터를 넣는 쪽 
• offer() - 값 넣기 
• poll() - 값 꺼내기 

 

큐 선언 

 

ex) 

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

Queue<Integer> queue = new LinkedList<>();
queue.offer(1); // 1넣기
queue.offer(2); // 2넣기 

int num = queue.poll(); //queue의 맨 앞 값 꺼내기 
queue.peek();  //맨 앞의 값 확인하기

 

배열로 큐 만들기 

 

public class IntQueue {

    private int max;    // 큐의 용량
    private int front;  // 첫 번째 요소 커서
    private int rear;   // 마지막 요소 커서
    private int num;    // 현재 데이터 수
    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;
        }
    }
}