[자료구조] 큐 (Queue)

큐 (Queue)

큐는 데이터를 순서대로 처리는 자료구조이다. 임시 데이터를 다루고 제약이 있는 배열이라는 점에서 스택과 비슷한데, 데이터 처리의 순서가 다르다. 큐에는 세 가지 제약이 있다.

• 데이터는 스택의 끝에만 삽입할 수 있다.
• 데이터는 스택의 앞에서만 읽을 수 있다.
• 데이터는 스택의 앞에서만 삭제할 수 있다.

버블티 빨대 속 버블이 빨려 오는 흐름이나, 극장 앞에 줄을 서서 입장하는 모습에 비유할 수 있다. 큐 자료구조의 특징은 다음과 같다.

• FIFO(First In First Out)/선입선출

		queue.add(1);
        queue.add(2);
        queue.add(3);
        ---순서대로 1, 2, 3 입력---
        System.out.println(queue.show()); // [1, 2, 3, 4, 5]
        ---현재 상태---
		queue.pull(); // 1 꺼내기
        queue.pull(); // 2 꺼내기
        ---꺼내기 후 데이터 상태---
        System.out.println(queue.show()); // [3, 4, 5];

큐는 먼저 들어간 데이터가 먼저 나온다.

• 데이터는 하나씩 넣고 뺄 수 있다.
  데이터는 하나씩만 넣고 뺄 수 있다. 한 번에 여러 개씩 넣고 뺄 수는 없다.

• 두 개의 입출력 방향을 가지고 있다.
  큐는 데이터의 입력과 출력의 방향이 다르기 때문에, 같은 입출력 방향을 가진 자료구조는 큐라고 볼 수 없다.

큐 클래스의 대표적인 메서드는 다음과 같다.

메서드	설명
add()	큐에 데이터 추가
offer()	큐에 데이터 추가
poll()	가장 먼저 추가된 데이터를 스택에서 삭제, 삭제한 데이터 리턴 (큐가 비어있으면 1 반환)
size()	큐에 추가된 데이터의 크기 리턴
peek()	가장 먼저 추가된 데이터 리턴
clear()	현재 큐에 포함된 모든 데이터 삭제
empty()	스택이 비어있는지 확인 (비었으면 true)
contains(int value)	스택에 값이 있는지 확인 (있다면 true)

✨ 큐 구현

class QueueE {
    private ArrayList<Integer> listQueue = new ArrayList<>();

    public void add(Integer num){
        listQueue.add(num);
    }
    public Integer pull() {
        if(listQueue.size() == 0) return null;
        return listQueue.remove(0);
    }
    public int size() {
        return listQueue.size();
    }
    public Integer peek() {
        return listQueue.get(0);
    }
    public String show() {
        return listQueue.toString();
    }
    public void clear() {
        listQueue.clear();
    }

}
public class QueuePractice {
    public static void main(String[] args) {
        QueueE queue = new QueueE();

        queue.add(1);
        queue.add(2);
        queue.add(3);
        queue.add(4);
        queue.add(5);

        System.out.println(queue.show()); // [1, 2, 3, 4, 5]

        queue.pull(); // 1 꺼내기
        queue.pull(); // 2 꺼내기

        System.out.println(queue.show()); // [3, 4, 5];

    }
}

참고 자료
『 누구나 자료 구조와 알고리즘』