[자료구조][큐] 코딩테스트, 정보처리기사를 위한 기초 3

 

 

 

 

[이전 글]

2023.07.15 - [코딩테스트] - [자료구조][List] 코딩테스트, 정보처리기사를 위한 기초 2

[자료구조][List] 코딩테스트, 정보처리기사를 위한 기초 2

 

 

 

• Queue 란?
  • 줄을 서는 행위와 유사하다.
  • 데이터를 일시적으로 (버퍼) 저장하는 자료구조 중 하나이다.
  • 가장 먼저 넣은 데이터를 가정 먼저 꺼내는 구조
  • 버스를 탈때 줄을 서서 타는 이치
  • FIFO(First-In, First-Out) 또는 LILO(Last-In, Last-Out) 방식

 

• 큐의 주요 연산
  • 자바는 java.util 패키지에 Queue 클레스 를 제공한다.
  • Enqueue(인큐) : 큐에 데이터를 추가하는 연산이다. 새로운 데이터를 큐의 뒤쪽에 추가한다.
    1. add(value) : 데이터 추가시 공간이 없으면 IllegalStateException 예외 발생 
    2. offer(value) : 데이터 추가시 공간이 없으면 false을 리턴하고 예외는 발생하지 않는다.
  • Dequeue(디큐) : 큐에서 데이터를 제거하는 연산이다. 가장 앞쪽에 있는 데이터가 제거되고 반환 된다.
    • poll(), remove() 메서드 제공
  • Front(프론트) : 큐의 가장 앞쪽에 있는 데이터를 확인하는 연산이다. 제거하지 않고 값을 확인 하는 용도로만 사용된다.
  • IsEmpty : 큐가 비어있는지 확인 하는 연산
  • IsFull : 큐가 가득 차 있는지 확인 하는 연산이다. 크기가 정해져 있는 큐일 경우 사용된다.

 

---

 

 

• 자바 큐 예제
  • 자바는 LinkedList 클래스를 이용하여 Queue 를 사용 한다.

 

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

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

        Queue<Integer> q = new LinkedList<>();
        q.add(0);
        q.add(1);
        q.offer(2);
        q.offer(3);
        q.offer(4);

        //Front 연산
        System.out.println("첫 번째 요소 : " + q.peek());

        //Dequeue 연산
        Integer removeItem = q.poll();
        System.out.println("첫 번째 아이템 사용 : " + removeItem);

        //IsEmpty 연산
        System.out.println("빈 공간 여부 : " + q.isEmpty());

        // Queue 출력
        System.out.println("큐 출력 : " + q);
    }
}

/**
 첫 번째 요소 : 0
 첫 번째 아이템 사용 : 0
 빈 공간 여부 : false
 큐 출력 : [1, 2, 3, 4]
 */

 

 

 

• ArrayList로 큐 구현 간단 예제

 

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Queue;
import java.util.LinkedList;

public class QueueTest {
    //ArrayList 로 구현
    public static class ArrayListQueue<T> {
        private ArrayList<T> q = new ArrayList<>();

        public void add(T value) {
            q.add(value);
        }

        public T peek() {
            return q.get(0);
        }

        public T poll() {
            return isEmpty() ? null : q.remove(0);
        }

        public boolean isEmpty() {
            return q.isEmpty();
        }

        @Override
        public String toString() {
            return Arrays.toString(q.toArray());
        }
    }

    public static void main(String[] args) {
        ArrayListQueue<Integer> q = new ArrayListQueue();
        q.add(0);
        q.add(1);
        q.add(2);
        q.add(3);
        q.add(4);

        //Front 연산
        System.out.println("첫 번째 요소 : " + q.peek());

        //Dequeue 연산
        Integer removeItem = q.poll();
        System.out.println("첫 번째 아이템 사용 : " + removeItem);

        //IsEmpty 연산
        System.out.println("빈 공간 여부 : " + q.isEmpty());

        // Queue 출력
        System.out.println("큐 출력 : " + q);
    }
}

/**
 * 첫 번째 요소 : 0
 * 첫 번째 아이템 사용 : 0
 * 빈 공간 여부 : false
 * 큐 출력 : [1, 2, 3, 4]
 */

 

 

---

 

[다음 글]

2024.01.25 - [코딩테스트] - [자료구조][스택] 코딩테스트, 정보처리기사를 위한 기초 4

[자료구조][스택] 코딩테스트, 정보처리기사를 위한 기초 4