큐(Queue)_1

요즘에 학교를 개강해서 그런지 몸이 많이 바쁜 하루를 보내고 있네요 ㅎㅎ

그래서 그런지 굉장히 오랜만에 글을 쓰게 되는 것 같아요 :)

이제는 꾸준하게 자료구조 공부할때마다 글을 업로드할 예정인데 잘 읽어주셨으면 좋겠고

저한테 혹시나 배워갈게 있으면 배워가시는 좋은 시간이 되었으면 좋겠네요 ㅎ

---

저번 시간 스택(Stack)에 이어서 이번 시간에는 큐(Queue)에 대해서 알아보도록 하겠습니다

큐에도 종류가 여러가지가 있는데 1. 선형 큐 2. 원형 큐 3. 덱 이렇게 3가지로 나눌 수가 있고

오늘 알아볼 큐의 종류는 선형큐입니다.

큐라는 것은 스택과(스택은 FILO)는 다르게 FIFO(First in First out) 구조를 가지고 있고

FIFO에서 볼 수 있듯이 처음 들어온 것이 처음 나가는 구조로 되어있습니다

먼저 들어온 것이 늦게 나가는 스택과는 비슷하지만 다른 부분이 존재합니다

그리고 스택은 입력과 출력이 같은 곳에서 일어나지만 아래에 그림처럼

큐는 입력은 앞에서 출력은 뒤에서 이루어져서 총 2군데에서 일어나게 됩니다

---

코드로 구성하기에 앞서서 필요한 메서드와 프로퍼티들을 한번 알아보도록 하겠습니다

메서드

• is_empty(q) ->  큐가 비었는지 확인하고 비었다면 true 아니면 false를 반환한다
• is_full(q) -> 큐가 가득 찼는지 확인하고 가득 찼다면 true 아니면 false를 반환한다
• enqueue -> 큐의 끝부분으로 값을 집어넣는다
• dequeue -> 큐의 제일 앞단의 값을 제거해서 반환한다
• peek(q) -> 큐의 제일 앞단의 값을 반환하여 준다

프로퍼티

• front -> 큐의 첫 번째 요소를 가리킨다
• rear -> 큐의 마지막 요소를 가리킨다

---

이번에는 앞에서 얘기한 메서드와 프로퍼티를 가지고 코드로 구현해 보도록 하겠습니다

구현 언어 : 자바

int front, rear;
int data[];

public Queue(){
    this.front = -1;
    this.rear = -1;
    this.data = new int[5];
}

큐에 데이터를 저장할 배열과 변수들을 선언하고 초기화한다

boolean is_empty() {
    if(front == -1 && rear == -1){
       return true;
    }else{
       return false;
    }
}

boolean is_full(){
    if(data.length-1 == rear){
        return true;
    }else{
        return false;
    }
}

is_empty()와 is_full()을 통해서 가득 찼는지 비었는지 확인할 수 있다

void enqueue(int input) {
    if(is_full() == true){
        System.out.println("큐가 가득찼습니다");
        return;
    }
    data[++rear] = input;
}

enqueue() 메서드를 호출하면 rear값이 1만큼 커지고 그곳에 데이터를 삽입한다

int dequeue() {
    if(is_empty() == true){
        System.out.println("큐가 비었습니다");
    }
    int result = data[++front];
    data[front] = 0;
    return result;
}

dequeue() 메서드를 호출하면 데이터를 하나 반환하고 front의 값을 하나 늘리고 0으로 다시 채워 넣는다

int peek() {
    if(is_empty() == true){
        System.out.println("큐가 비었습니다");
    }
    return data[front+1];
}

peek() 메서드를 호출하면 front값에 +1을 하면 제일 앞에 저장된 데이터를 불러올 수 있다

---

<전체 코드 보기>

 

이번에는 가볍게 큐에 대한 원리와 필요한 프로퍼티와 메서드를 알아보았고 그것을 구현하는 단계까지 마쳐보았습니다

스택과 다르기는 하지만 메서드의 구성과 필요한 프로퍼티를 비교해 보았을 때

선형 큐는 많은 부분을 닮아 있기에 쉽게 읽으셨을 거라고 생각합니다! :)

다음에는 원형 큐에 대해서 알아보도록 하겠습니다!!