[자료구조] Queue(큐)

# Queue (큐)

First In First Out (FIFO)형태의 자료구조로, BFS탐색이나 버퍼 등에 사용된다.

기본적으로 rear와 front라는 포인터로 삽입할 곳과 뺄 곳을 가리키고 있음

(rear : enQueue (삽입)할 위치, front : deQueue(데이터 빼기)할 위치)

1. 기본적인 구현

front와 rear은 모두 초기에 -1로 시작한다.

public Queue {
    int[] queue;
    int rear = -1;
    int front = -1;
    public Queue(){
        queue = new int[50];
    }
    public void enQueue(int v) {
        if(isFull())
                return;
        queue[++rear] = v;
    }
    public int deQueue() {
        if(isEmpty())
                return null;
        int value = queue[front];
        queue[front++] = null;
        return value;
    }
    public boolean isFull(){
        return rear + 1 == queue.length();
    }
    public boolean isEmpty(){
        return front == rear;
    }
}

-> 하지만 이 방법은 실제 큐가 꽉차있지 않더라도 꽉 차 있는 것으로 판단해 큐에 더이상 넣지 못하는 경우가 생긴다. (이를 위한 것이 원형 큐)

2. 원형 큐 

위에 방법은 deQueue를 하면서 front가 비게 되고 앞에 공간은 활용하지 못해 생기는것을 앞과 뒤를 이은 원형 큐로 해결하는 방법이다.

공백과 포화상태를 쉽게 구분하기 위해 한칸을 비워 놓고 구현한다. (만약 한칸을 비우지 않는 다면, 비워진 상태일 때 쓰는 front == rearrk 포화상태일 때도 true가 되므로 한칸을 비우는 것이다. 물론, 또 다른 flag변수를 생성해 활용해도 된다)

front, rear 모두 0으로 시작

public Queue {
    Object[] queue;
    int rear = -1;
    int front = -1;
    public Queue(){
        queue = new Object[50];
    }
    public void enQueue(Object o) {
        if(isFull()) {
            return;
        }
    
        //rear를 하나 올리고 삽입
        rear = (++rear) % size;
        queue[rear] = o;
    }
    public Object deQueue(Object o) {
           if(isEmpty()) { 
               return null;
          }
    
        //front가 가르키는 다음 위치를 삭제해줌
        front = (front+1) % size;
        Object o = queue[front];
        return o;
    }
    public boolean isEmpty() {
        return front == rear;
    }
    public boolean isFull() {
        return ((rear+1) % size == front);
    }
}

 

3. 연결리스트를 이용한 구현

크기의 제한이 없다. 간단하게 deque, enqueue의 구현만 적는다.

아래는 코틀린 연습을 위해 코틀린으로 구현한 코드입니다. 

class Node(val value: Int, var next: Node? = null) {
}
class Queue(val MAX_SIZE: Int = 10) {
    var rear:Node? = null
    var front:Node? = null
    private var size: Int = 0
 
    fun getSize() = size
    fun isEmpty() = (size === 0 || (rear === null && front === null))
    fun isFull() = (size === MAX_SIZE)
 
    fun enQueue(n:Int){
        var newNode:Node = Node(n);
        if (isEmpty()) {
            front = newNode
            rear = newNode
        } else {
            rear?.next = newNode
            rear = newNode
        }
        size++
    }
 
    fun deQueue():Int? {
        if (isEmpty()) {
            return null
        }
        var removeNode:Node? = front
 
        //데이터가 하나남을때
        if (front == rear) {
            front = null
            rear = null
        } else {
            front = front?.next
        }
        size--
        return removeNode?.value;
    }
}

 

 

- 스택으로 큐 구현, 큐로 스택 구현

https://mhwan.tistory.com/56