알고리즘] 자료구조, 큐(Queue)

개요

이직을 준비하면서 참 많은 경험과 생각을 했습니다.
그 중에 하나가 기초적인 자료구조와 알고리즘은 필수로 알아야겠다 라는 것입니다.
기본적인 Stack과 Queue의 LIFO, FIFO의 개념정도는 알았으나... 이것을 활용한 알고리즘 문제를 풀어보려고하니 머리 텅텅거리는 느낌이었습니다.. 그래서 공부한 것을 정리하고자 합니다.

---

본문

1. 큐 구조

큐를 비유하는 줄서는 모습.

• 큐 (Queue)의 자료구조는 FIFO (First-In, First-Out)의 방식이며, 한국말로는 선입선출이라 한다.
• 샤넬(명품매장)매장에 가장 먼저 줄을 선 사람이 샤넬백을 제일 먼저 살 수 있는 것이라고 생각하면 될까..?

 

출처 : http://www.stoimen.com/2012/06/05/computer-algorithms-stack-and-queue-data-structure/

알아야할 용어!
Enqueue : 큐에 데이터를 넣는 기능.
Dequeue : 큐에서 데이터를 꺼내는 기능.

 

2. JAVA에서 자료구조 큐를 구현해보자.

 

추가를 해보자.

class Item {
    public static void main(String[] args) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(1); // 1을 추가!
        queue.offer(2); // 2를 추가, 성공적으로 add를 하면 true로 리턴한다.
        System.out.println("queue = " +  queue);
    }
}

출력 결과는 ⬇️

queue = [1, 2]

 

삭제를 해보자.

class Item {
    public static void main(String[] args) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(1); // 1을 추가!
        queue.offer(2); // 2를 추가, 성공적으로 add를 하면 true로 리턴한다.

        queue.poll(); //poll은 dequeue에 해당하며, 꺼내는 기능을 한다. 첫번째 값인 1을 꺼낸다.

        System.out.println("queue = " +  queue);
    }
}

출력 결과는 ⬇️

queue = [2]

 

3. Queue를 이용한 자바 프로그래밍.

class AlgoQueueTest<T> {

    private ArrayList<T> queue = new ArrayList<>();

    public void enqueue(T item) {
        queue.add(item);
    }

    public T dequeue() {
        if(queue.isEmpty()) {
            return null;
        }
        return queue.remove(0);
    }

    public static void main(String[] args) {
        AlgoQueueTest algoQueueTest = new AlgoQueueTest();

        algoQueueTest.enqueue(1);
        algoQueueTest.enqueue(2);
        algoQueueTest.enqueue(3);
        algoQueueTest.dequeue();

        System.out.println("첫번째 큐 = " + algoQueueTest.dequeue());
        System.out.println("두번째 큐 = " + algoQueueTest.dequeue());
        System.out.println("세번째 큐 = " + algoQueueTest.dequeue());
    }
}

출력 결과는 ⬇️

첫번째 큐 = 2
두번째 큐 = 3
세번째 큐 = null