[자료구조] 1. 큐(Queue) 구현하기 (Java)

시작하며

삼성전자 SW 역량테스트 B형은 라이브러리를 사용할 수 없는 대신 Reference Code를 제공합니다. 제가 구현한 자료구조들은 기본적으로 Reference Code를 바탕으로 하며 이해하는 과정에서 주석을 달며 정리했습니다. 구현 코드는 실제 시험에서 사용할 때는 달라질 수 있으며 각자에게 맞는 방식으로 구현하시는 것을 추천합니다.

 

큐(Queue)

①

큐(Queue)는 먼저 집어넣은 데이터가 먼저 나오는 FIFO(First In First Out) 구조를 가지고 있습니다. 아래 소스코드에서 1차원 배열로 큐를 구현하였고 큐 관련 함수들은 다음과 같습니다.

queueIsEmpty(): 큐 안이 비어있는지 판단하는 함수

queueIsFull(): 1차원 배열의 최대 크기를 벗어나면 안 되기에 큐에 더 이상 들어갈 공간이 없는지 판단하는 함수

size(): queue에 현재 들어가 있는 데이터의 개수를 return 하는 함수

push(int value): 큐 안에 데이터를 집어넣는 함수

peek(): 큐 안의 데이터들 중 가장 먼저 나올 수 있는 데이터를 return 하는 함수

pop(): 큐 안의 데이터들 중 가장 먼저 나올 수 있는 데이터를 return 하고 삭제하는 함수

 

②

아래 소스코드의 맨 아래 주석 부분을 보면 Input과 Output을 알 수 있습니다. 테스트 케이스의 개수는 2이고 첫번째 테스트 케이스에서 5개의 숫자가 들어옵니다. 1 2 3 4 5가 들어오면 순차적으로 큐에 저장합니다. 큐에 들어있는 데이터들을 꺼내 출력하면 먼저 들어온 순서대로 1 2 3 4 5이 결과값으로 나옵니다.

소스 코드

package algo;
 
import java.util.Scanner;
 
class ArrayQueue{
    int MAX_N = 10000;
    int front, rear; //front: 머리(queue에서 pop할 위치의 index)
    int queue[]; //rear: 꼬리(queue에 push할 위치의 index)
    
    public ArrayQueue() {
        front = rear = 0; //front와 rear의 초기값은 0
        queue = new int[MAX_N]; //배열 생성
    }
    
    boolean queueIsEmpty() { //queueIsEmpty(): queue에 아무것도 들어있지 않은지 판단하는 함수
        return (front == rear);
    }
    
    boolean queueIsFull() { //queueIsFull(): queue에 더이상 들어갈 공간이 없는지 판단하는 함수
        //front와 rear가 같으면 queue에 데이터가 존재하지 않는 경우임.
        //LinkedList 구조로 구성되어 있기 때문에 (rear+1) % MAX_N == front 로 판단함.
        if ((rear + 1) % MAX_N == front) return true;
        else return false;
    }
    
    int size() { //size(): queue에 현재 들어가있는 데이터의 개수를 return하는 함수
        return rear-front;
    }
    
    void push(int value) { //push(int value): value값을 queue에 넣음
        if(queueIsFull()) System.out.println("queue is full!");
        else {
            queue[rear++] = value;
            if(rear == MAX_N) rear = 0; //queue 배열의 Max값인 MAX_N-1을 넘어서면 다음 index인 0으로 바꿔줌.
        }
    }
    
    Integer peek() { //peek(): queue내에 있고 가장 먼저 들어간 값을 return하는 함수
        if(queueIsEmpty()) {
            System.out.println("queue is empty!");
            return null;
        }
        Integer value = new Integer(queue[front]);
        return value;
    }
    
    Integer pop() { //pop(): queue내에 있고 가장 먼저 들어간 값을 return하고 삭제하는 함수
        if(queueIsEmpty()) {
            System.out.println("queue is empty!");
            return null;
        }
        Integer value = new Integer(queue[front++]);
        if(front==MAX_N) front = 0;
        return value;
    }
}
 
class STL_Queue {
    public static void main(String arg[]) throws Exception {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        for (int test_case = 1; test_case <= T; test_case++) {
            int N = sc.nextInt();
            ArrayQueue q = new ArrayQueue();
            for (int i = 0; i < N; i++) {
                int value = sc.nextInt();
                q.push(value);
            }
            System.out.print("#" + test_case + " ");
            while (!q.queueIsEmpty())
            {
                Integer value = q.pop();
                if (value != null) {
                    System.out.print(value.intValue() + " ");
                }
            }
            System.out.println();
        }
        sc.close();
    }
}
/*
input
2
5
1 2 3 4 5
5
5 4 2 3 1
output
#1 1 2 3 4 5
#2 5 4 2 3 1
*/