[자료구조] 선형 큐의 기능 및 구현

안녕하세요. PEACE- 입니다.

자료구조 스터디 [다섯 번째] 글입니다.

배열을 이용한 선형큐에 대해 알아보겠습니다. 

원형 큐 포스팅 주소 http://mailmail.tistory.com/41

1. 큐

선입선출(First In First Out)이라 불리는 데이터 구조입니다. 먼저 들어온 데이터가 먼저 나가며, 핵심 키로는 front 와 rear이 있습니다.

큐의 핵심 기능으로는 데이터를 넣어주는 enqueue, 데이터를 내보내는 dequeue가 있습니다.

2. enqueue

데이터를 넣어주는 기능을 수행합니다. 마지막 데이터의 위치가 변하므로 rear이 -1만큼 이동합니다.

3. dequeue

데이터를 내보내는 기능을 수행합니다. 맨 앞에 있는 데이터가 바뀌므로 front가 +1만큼 이동합니다.

4. 문제점

큐 배열에 데이터가 가득 차거나 rear이 마지막 인덱스까지 이동해 버렸다면 어떻게 될까?

1) 큐가 가득찼다. 

- 더이상 데이터를 넣을 수 없다. 공간의 제한이 생김.

2) 가득 찬 건 아니지만 rear이 마지막 인덱스를 가리키고 있으며, 앞의 공간이 비어있다.

- 데이터를 넣을 공간을 마련하기 위해 데이터를 전체적으로 앞으로 이동시켜야한다. 비효율적인 작업이 생김.

5. 해결점

원형 큐의 개념을 이용해 이용해 머리와 꼬리가 연결된 형태의 큐를 구현한다. (다음 포스팅)

6. 소스코드

Queue.class

/* 선형 큐 - 배열 이용
 * front : int - 초기 값1, 처음 데이터의 바로 전 인덱스
 * rear : int - 초기 값 1, 마지막 데이터의 인덱스
 * isEmpty() : boolean, isFull() : boolean
 * enqueue() : void, dequeue() : data type
 * */
public class Queue {

    private final int MAX_SIZE = 5;
    private int front, rear;
    private int[] queue;

    public Queue() {
        front = rear = -1;
        queue = new int[MAX_SIZE];
    }

    private boolean isEmpty() {
        return front == rear ? true : false;
    }

    private boolean isFull() {
        return rear == MAX_SIZE-1 ? true : false;
    }

    public void enqueue(int data) {
        if (isFull())
            return;
        else
            queue[++rear] = data; //현재 rear 다음 공간에 데이터를 넣는다.
    }

    public int dequeue() {
        if (isEmpty())
            return -1; //데이터가 없어서 dequeue에 실패하면 -1리턴하도록 로직 구현.(임시)
        else
            return queue[++front]; //맨 앞의 데이터를 리턴하고 front를 1증가 시킨다.

    }

    public void display() {
        System.out.print("Queue : ");
        for (int idx = front + 1; idx <= rear; idx++)
            System.out.print(queue[idx] + " ");
    }

}