Data Structure, Queue

지난 시간에는 Stack 자료 구조에 대해 알아봤습니다!

https://songye.tistory.com/18

Data Structure, Stack

Stack을 이해하면 Queue는 식은 죽 먹기

 

1. Queue란?

Queue의 영단어 뜻을 찾아보면 대기열이란 의미를 갖고 있습니다.

 

사진을 보고 한 번 이야기 해봅시다.

대기열

음식점, 병원, 어떠 특정 목적을 위해 줄을 서면

 

먼저 도착한 사람이 먼저 들어가 목적을 수행하는 경우를 많이 봅니다 (음식점에선 2명이 앞선 4명보다 먼저 들어가던데)

 

이처럼 FIFO(First In First OUT) 데이터구조를 Queue라고 합니다.

 

2. Operations

Stack과 마찬가지로 동일한 operations 구조를 갖지만 지칭하는 이름이 조금씩 다릅니다!

 

(1) Add -> Enqueue

(2) Remove -> Dequeue

(3) Test if empty -> IsEmpty (이건 똑같잖아요)

 

이때 일반적인 프로그래밍 언어에서 Queue를 Implementation하기 위해 2가지 방법을 사용할 수 있습니다.

 

(1) Linked List

(2) Array

 

코드를 보며 살펴봅시다.

 

3. Code

(1) Linked List

import java.util.NoSuchElementException;

public class Queue {
    private Node first = null;
    private Node last = null;

    public static class Node {
        String item;
        Node next;
    }

    public void Enqueue(String item) {
        Node x = new Node();
        x.item = item;
        x.next = null;
        if (IsEmpty())
            first = x;
        else
            last.next = x;
        last = x;

    }

    public String Dequeue() {
        if (IsEmpty())
            throw new NoSuchElementException("큐가 비어있습니다.");
        String item = first.item;
        first = first.next;
        return item;
    }

    public boolean IsEmpty() {
        return first == null;
    }
}

 

public class Main {
    public static void main(String[] args) {
        Queue queue = new Queue();
        queue.Enqueue("Hello!");
        queue.Enqueue("my");
        queue.Enqueue("name");
        queue.Enqueue("is");
        queue.Enqueue("Songye!");
        while (!queue.IsEmpty()) {
            System.out.println(queue.Dequeue());
        }
        queue.Dequeue();
    }
}

위에서 Operaiotns들이 그대로 구현된 것을 확인할 수 있습니다.

 

*주의*

 

Stack과 구조가 비슷하지만 다른 점이 두 가지 있습니다.

 

(1) last라는 변수가 하나 추가되어 입구와 출구를 하나씩 만들어줬다는 것입니다 (Stack은 입출구가 하나)

 

(2) 처음 빈 Queue에서 시작할 때 first와 last가 같은 곳을 가리키기 때문에 Enqueue에 예외 처리가 필요합니다.

실행 결과

생각해보니 try catch를 안했네요 귀찮으니 넘어가곘습니다,,

 

먼저 Enqueue한 자료들이 순서대로 Dequeue되는 것을 확인 가능합니다.

 

(예외 처리 안한 Dequeue 에러도 확인가능 ㅎ,,)

 

(1) Array

import java.util.NoSuchElementException;

public class Queue {
    String [] arr;
    int head = 0;
    int tail = 0;
    int capacity;

    public Queue(int capacity) {
        this.capacity = capacity;
        this.arr = new String[capacity]; // capacity 크기의 배열을 생성합니다.
    }
    public void Enqueue(String item) {
        arr[tail] = item;
        tail = (tail + 1) % capacity;
    }

    public String Dequeue() {
        if (IsEmpty())
            throw new NoSuchElementException("큐가 비어있습니다.");
        String item = arr[head];
        arr[head] = null;
        head = (head + 1) % capacity;
        return item;
    }

    public boolean IsEmpty() {
        return arr[head] == null;
    }

}

import java.util.NoSuchElementException;

public class Main {
    public static void main(String[] args) {
        try {
            Queue queue = new Queue(10);
            queue.Enqueue("Hello!");
            queue.Enqueue("my");
            queue.Enqueue("name");
            queue.Enqueue("is");
            queue.Enqueue("Songye!");
            queue.Enqueue("Hello!");
            queue.Enqueue("my");
            queue.Enqueue("name");
            queue.Enqueue("is");
            queue.Enqueue("Songye!");
            queue.Enqueue("Hello!");
            queue.Enqueue("my");
            queue.Enqueue("name");
            queue.Enqueue("is");
            while (!queue.IsEmpty()) {
                System.out.println(queue.Dequeue());
            }
        } catch (NoSuchElementException var6) {
            System.out.println("큐가 비어있습니다. 에러 메시지: " + var6.getMessage());
        }
    }
}

 

Arr를 구현한 Queue는 Arr로 구현한 Stack과 다른 점있습니다.

 

Stack에서는 arr를 Resize하여 데이터가 추가 되거나 줄어들 때 메모리 사용을 최소로 했다면

 

이번 Queue는 Resize가 아니라 Capacity를 정하여 정해진 용량만큼만 사용하는 Queue를 작성했습니다.

 

*특징*

 

1. Head와 Tail이라는 변수로 Queue의 first와 last (Linked List에서 구현)를 구현했습니다.

 

2. arr 특성상 index가 index size를 벗어나면 안되기 때문에 modulo 연산을 통해 Head와 Tail을 0번 인덱스부터 돌게하였습니다.

 

4. 장단점

Stack과 비슷합니다 참고 바람! ㅎ

 

Queue라는 데이터 구조의 특성을 잘 사용하고 맞는 데이터 structure를 유동적으로 사용하는 것이 필요합니다!