큐(Queue)

GilLog·2020년 10월 13일
queue자료구조
0

자료구조

목록 보기
2/7

1. 큐(Queue)란?

큐(queue)는 컴퓨터의 기본적인 자료 구조의 한가지로, 먼저 집어 넣은 데이터가 먼저 나오는 FIFO (First In First Out)구조로 저장하는 형식을 말한다.
나중에 집어 넣은 데이터가 먼저 나오는 스택과는 반대되는 개념이다.

큐는 간단하게 식당에서 줄을 서는 것과 같다. 줄을 먼저 선 사람이 먼저 식당으로 들어가듯이, 먼저 넣은 데이터가 먼저 나간다.

큐의 가장 첫 원소를 front, 끝 원소를 rear이라고 부르는데
큐는 들어올 때 rear로 들어오지만, 나올 때는 front부터 빠지는 특성을 가진다.

큐를 사용하는 데이터의 접근방법은 가장 첫 원소(front)와 끝 원소(rear)로만 가능하다.
Rear(끝 원소)에서는 삽입 연산만 일어나고, Front(첫 원소)에서는 삭제 연산만 일어난다.

2. 큐 사용법

Queue 인터페이스는 클래스로 구현된 Stack과는 다르게 큐 메모리 구조를 별도의 인터페이스 형태로 제공한다.

Queue를 상속받는 하위 인터페이스 들은 아래와 같다.

  1. Deque<E>

  2. BlockingDeque<E>

  3. BlockingQueue<E>

  4. TransferQueue<E>

Queue는 대부분 위 하위 인터페이스들 중 Deque 인터페이스를 구현한 LinkedList 클래스를 이용하여 인스턴스화를 시킨다.

그래서 실제로 자바에서 사용할때는 Queue와LinkedList를 둘다 import 해주어야 한다.

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

그 후 아래와 같이 생성해주면 된다.

// E는 강제 형변환 문제를 해결해주는 제너릭 <E> 이다.
Queue<E> queue = new LinkedList<E>();

기본적으로 사용되는 메소드는 다음과 같다.

메소드반환 타입용도
add(E data)boolean큐에 data를 넣고 성공하면 true를 return 한다.
저장공간이 부족할 경우 IllegalStateException이 발생한다.
poll()E큐에서 제일 먼저 들어온 data를 제거하고 return 한다.
비어있으면 null을 return한다.
peek()E큐에서 제일 먼저 들어온 data를 제거없이 return 한다.
비어있으면 null을 return한다.
remove()E큐에서 제일 먼저 들어온 data를 제거하고 return 한다.
비어있으면 NoSuchElementException이 발생한다.
element()E큐에서 제일 먼저 들어온 data를 제거없이 return 한다.
비어있으면 NoSuchElementException이 발생한다.
offer(E data)boolean큐에 data를 넣고 성공하면 true를 return 한다.
실패하면 false를 return 한다.

3. 큐 Java 구현 코드

큐를 자바로 직접 구현하려면 아래와 같은 메소드를 정의 해주어야 한다.

  • enQueue() : 데이터 입력
  • deQueue() : 데이터 출력
  • isEmpty() : 큐가 비어있는지 확인
  • isFull() : 큐가 꽉차 있는지 확인

front와 rear가 초기값 -1을 가진 비어있는 상태를 시작으로, front = rear일 경우 큐가 비어있는 경우이다.

rear에서 삽입이 일어날때마다 rear가 점점 증가하여 큐의 크기가 size일때 rear==size-1인 경우 큐가 꽉차 있는 경우이다.

3.1 front, rear, size 초기값

private int size = 0; 
private int rear = -1; 
private int front = -1;

Queue(int size) { 
    this.size = size;
    this.queue = new Object[size];
}

3.2 enQueue()

// queue가 꽉차있지 않다면 rear를 증가시키고 o를 넣어준다.
// queue가 꽉차있는 경우 overflow가 발생한다.
public void enQueue(Object o) {
    
    if(isFull()) {
        return;
    }
    
    queue[++rear] = o;
}

3.3 deQueue()

// queue가 비어있는 경우 underflow가 발생한다.
// queue가 비어있지 않다면 front에 위치한 값을 o에 저장하고
// front위치의 queue를 비워준 후, front를 증가시킨다.
// 저장된 o를 return한다.

public Object deQueue(Object o) {
    
    if(isEmpty()) { 
        return null;
    }
    
    Object o = queue[front];
    queue[front++] = null;
    return o;
}

3.4 isEmpty()

//front와 rear가 같다면 ture를 리턴한다.
public boolean isEmpty() {
    return front == rear;
}

3.5 isFull()

// rear가 queue의 크기 -1 과 같다면 true를 return한다.
public boolean isFull() {
    return (rear == size-1);
}

4. 큐 구현 단점 극복

큐에 계속 삽입을 하다보면 rear가 증가하다 rear == size-1가 되면 queue가 full 상태가 된다.
하지만 이때 큐에 데이터가 꽉차있지 않을 수가 있는데, front에서 삭제 연산이 이루어지며 front가 증가하였지만, 그 자리들은 비어있기 때문이다.

이를 해결 하기 위해서는 순차 큐, 원형 큐, Linked List 이용 큐 3가지 방법이 있다.

  • 순차 큐
    - 배열로 큐를 구현한 것으로 크기가 제한되어 있고 빈 공간을 사용하려면 모든 자료를 꺼내거나 자료를 한 칸씩 옮겨야 한다는 매우 비효율적인 단점이 있다.
    아래 그림은 선형 큐의 작동 방식이다.

  • 원형 큐
    - front가 큐의 끝에 닿으면 큐의 맨 앞으로 자료를 보내어 원형으로 연결 하는 방식이다.
    아래 그림은 원형 큐의 작동 방식이다.

  • Linked List를 이용한 큐
    - 큐의 단점 극복을 위해 가장 많이 사용하는 방식으로, 연결 리스트를 사용한 것으로써, 큐의 길이를 쉽게 늘릴 수 있어 오버플로우가 발생하지 않는 것이 특징이다.
    필요에 따라 환형으로 만들 수도 있으며, 환형으로 만들지 않아도 삽입과 삭제가 제한되지 않아 편리하다.

4.1 원형 큐, Linked List를 이용한 큐 구현

4.1.1 원형 큐 구현

원형 큐로 구현은 논리적으로 배열의 처음과 끝을 연결시켜주어 일반 큐에서 빈 메모리가 있음에 가득찬 판단을 하는 경우를 해결해준다.

원형 큐로의 구현은 일반 큐와 다르게 front와 rear를 초기값 0 부터 시작하는데, 이는 공백, 포화 상태를 구분하기 위해 자리를 항상 하나 비워두기 때문이다.

그리고 (index + 1) % size로 순환시킨다.


// rear와 front의 초기값을 0부터 시작한다.
// 일반 큐는 초기값이 -1이다.
private int size = 0; 
private int rear = 0; 
private int front = 0;

Queue(int size) { 
    this.size = size;
    this.queue = new Object[size];
}

// 일반큐는  queue[++rear] = o; 이다.
public void enQueue(Object o) {
    
    if(isFull()) {
        return;
    }
    
    rear = (++rear) % size;
    queue[rear] = o;
}

// 일반 큐는 Object o = queue[front];
// queue[front++] = null; 이다.
// preIndex에 기존 front를 저장 한 후 위치를 1개 증가시킨후 % size를 해주고
// preIndex위치의 데이터를 반환한다.

 public Object deQueue(Object o) {
    
    if(isEmpty()) { 
        return null;
    }
    
    preIndex = front;
    front = (++front) % size;
    Object o = queue[preIndex];
    return o;
}

// 일반 큐와 같다.
public boolean isEmpty() {
    return front == rear;
}

// 일반 큐는 return (rear == size-1); 이다.
// rear에 1를 더한후 % size 연산한 것과 front를 비교 한다.
public boolean isFull() {
    return ((rear+1) % size == front);
}

원형 큐 역시 단점이 존재 하는데, 메모리 공간을 잘 활용하지만 아직도 배열로 구현되어 있기 때문에 큐 크기의 제약이 있다는 단점이 있다.

이를 개선한 것이 Linked List를 이용한 큐 이다.

4.1.2 Linked List를 이용한 큐 구현

Linked List 큐는 크기가 제한이 없고, 크기를 미리 지정할 필요가 없고, 삽입, 삭제가 편리하다는 장점이 있다.


// 데이터의 삽입은 tail(rear와 비슷)에 한다.
// 기존의 tail을 저장한 후, 새로운 tail을 생성한다.
// 만약 큐가 비었다면 head와 tail이 가르키는 노드는 같다.
// 큐가 비어있지 않다면, 아까 저장한 기존 tail.next에 새로 만든 tail을 가르키게 한다.
public void enqueue(E item) {
    Node oldlast = tail; // 기존의 tail 임시 저장
    tail = new Node; // 새로운 tail 생성
    tail.item = item;
    tail.next = null;
    if(isEmpty()) head = tail; // 큐가 비어있으면 head와 tail 모두 같은 노드 가리킴
    else oldlast.next = tail; // 비어있지 않으면 기존 tail의 next = 새로운 tail로 설정
}

// 데이터의 출력은 head(front와 비슷)에서 부터 한다.
// 기존 head의 데이터를 저장한다.
// 기존 head에 head.next를 덮어씌워서 head > 다음 head 노드를 저장하게 한다.
// 아까전 저장한 기존 head의 데이터를 return 해준다.
public T dequeue() {
    // 비어있으면
    if(isEmpty()) {
        tail = head;
        return null;
    }
    // 비어있지 않으면
    else {
        T item = head.item; // 빼낼 현재 front 값 저장
        head = head.next; // front를 다음 노드로 설정
        return item;
    }
}

🙆‍♂️ 참고사이트 🙇‍♂️

자료구조 - 큐(Queue)란?[galid1님]

[Java] 자바 Queue 클래스 사용법 & 예제 총정리[코딩팩토리님]

신입 개발자 전공 지식 & 기술 면접 백과사전[gyoogle님]

profile
GilLog
🚀 기록보단 길록을 20.10 ~ 22.02 ⭐ Move To : https://gil-log.github.io/
이전 포스트

스택(Stack)

다음 포스트

연결 리스트(Linked List)

0개의 댓글