[Data Structure] 자료구조 - 큐(Queue)

큐(Queue)

개념: 스택과 마찬가지로 삽입, 삭제의 위치와 방법이 제한되어있는 

유한 순서 리스트(Finite ordered list)지만,

스택과 달리 리스트의 한쪽 끝에서는 삽입 작업이 이루어지고, 

반대쪽 끝에서는 삭제 작업이 이루어져서

삽입된 순서대로 삭제되는

 

선입선출(FIFO: First In First Out)

구조 입니다!

흔한 예로 볼수 있는게 

놀이동산의 놀이기구 기다리는 줄이 있죠.

표로 조금 정리를 해서 

스택과 큐의 연산을 비교해 보도록 하겠습니다!

 

항목 자료구조	삽입연산		삭제연산
	연산자	삽입 위치	연산자	삽입 위치
스택	push	top	pop	top
큐	enQueue	rear	deQueue	front

이처럼 큐의 삽입은 rear에서 일어나고

큐의 삭제는 front에서 일어납니다!

아래는 큐의 구조입니다!

위에 보시는 것처럼 front에서 삭제가 일어납니다.

front에는 그럼 가장 먼저 들어간 원소가 있는 거죠.

rear에서는 삽입이 일어나고,

가장 나중에 들어온 원소가 존재합니다!

큐는 컴퓨터의 여러분야에서 발생한 순서대로 문제를 해결해야 하는 경우에 선입 선출 구조인 큐를 사용합니다!!

운영체제에서 실행을 요청한 작업들을 순서대로 처리하기 위해 버퍼 큐와 프로세스 스케줄링 큐

산업공학등의 분야에서 최적의 시스템을 설계하기 위한 시뮬레이션에서 대기 행렬 큐

그럼 예제를 통해 알아보도록 합시다!

먼저, 배열로 구현한 큐의 구조입니다!

클래스다이어그램 먼저 보시죠~

큐에는 크게 4개의 연산을 가지고 있습니다!

enQueue: 큐안에 데이터를 집어 넣는 연산

 deQueue: 큐안의 데이터를 끄집어 내는 연산

Peek: 큐의 front 데이터를 반환하는 연산(deQueue와는 다른 용도입니다!!!)

 Empty: 스택이 비어있는지 불리언 값 반환하는 연산

Quque.java

 

package queue;
 
public interface Queue {
    public boolean isEmpty();
 
    public void enQueue(String item);
 
    public String deQueue();
 
    public void delete();
 
    public String peek();
}
 

ArrayQueue.java

 

 
package queue;
 
public class ArrayQueue implements Queue {
 
    private int front;
    private int rear;
    private int queueSize;
    private String[] itemArray;
 
    public ArrayQueue(int queueSize) {
        front = -1;
        rear = -1;
        // 초기의 front와 rear는 같은 위치선상에 있음
 
        this.queueSize = queueSize;
        itemArray = new String[this.queueSize];
    }
 
    public boolean isEmpty() {
        return (front == rear);
    }
 
    public boolean isFull() {
        return (rear == this.queueSize - 1);
    }
 
    public void enQueue(String item) {
        if (isFull()) {
            System.out.println("삽입 실패! 큐가 꽉찼습니다!");
        } else {
            itemArray[++rear] = item;
            System.out.println("삽입된 아이템 : " + item);
        }
    }
 
    public String deQueue() {
        if (isEmpty()) {
            System.out.println("삭제 실패! 큐가 비어있습니다!");
            return null;
        } else {
            return itemArray[++front];
        }
    }
 
    public void delete() {
        if (isEmpty()) {
            System.out.println("삭제 실패! 큐가 비어있습니다!");
        } else {
            ++front;
        }
    }
 
    public String peek() {
        if (isEmpty()) {
            System.out.println("삭제 실패! 큐가 비어있습니다!");
            return null;
        } else {
            return itemArray[front + 1];
        }
    }
 
    public void printQueue() {
        if (isEmpty()) {
            System.out.println("큐가 비어있습니다!");
        } else {
            System.out.print("큐 >> ");
 
            for (int i = front + 1; i <= rear; i++)
                System.out.print(itemArray[i] + " ");
            System.out.println();
        }
    }
 
}
 

QueueMain.java

 

 
package queue;
 
public class QueueMain {
    public static void main(String[] args) {
        int queueSize = 4;
        ArrayQueue Q = new ArrayQueue(queueSize);
 
        Q.enQueue("I");
        Q.enQueue("AM");
        Q.enQueue("A");
        Q.enQueue("BOY");
 
        Q.printQueue();
 
        String deleteItem = Q.deQueue();
        if (!deleteItem.isEmpty())
            System.out.println("deleted Item : " + deleteItem);
 
        Q.printQueue();
    }
}
 

결과는 아래와 같습니다!!

 

다음은 원형 큐(Circular Queue)에 대해 진행합니다!!

원형 큐(Circular Queue)

위에서 설명한 기존 큐의 문제는 

프론트와 리어가 붙어있는 경우에 포화상태로 잘못 인식하여 

잘못된 연산을 수행합니다!!

아래와 같은 상황에 말이죠!

위와 같은 상황시에 원소들을 배열의 앞부분으로 이동시켜서 위치를 조정해야합니다!!

그러나!

그렇게 하기엔 이동 작업은 연산이 복잡하고,

큐의 효율성을 떨어트립니다!!!

그래서 고안한게 

원형 큐!!!!

원형 큐는 Circular Linked List의 개념과 비슷하다고 보시면 됩니다!!!

원형 큐의 개념: 

초기 공백 상태일 때 front와 rear의 값이 0 이 되고,

공백 상태와 포화 상태를 쉽게 구분하기 위해서 자리 하나를 항상 비워둡니다!!! 

원형큐에서의 공백상태 조건은 front = rear 와같은 조건이면 공백상태로 인지합니다!!

그럼 소스코드로 보시기 전에 원형큐의 구조를 보시겠습니다!!!

위처럼 돌돌 말려진 큐라고 보시면 되겠습니다!!!

그럼 원형 큐에 대한 알고리즘을 살펴보도록 하죠~

생성 알고리즘

 

 
 
createQueue() {
    cQ[n];
    front <- 0;
    rear <- 0;
}

  

공백 검사 & 포화 상태 검사 알고리즘

 

isEmpty(cQ) {
    if (front == rear) then return true;
    else return false;
}
 
isFull(cQ) {
    if (((rear + 1) mod n) == front) then return true;
    else return false;
}
 

포화 검사(isFull)이 좀 특이하죠??

rear가 원형 큐를 한바퀴 돌면서 원소를 삽입하여 큐를 모두 채우면 

rear의 다음 위치((rear+1) mod n)는 현재의 front 위치가 되어 

더이상 삽입할 수 없는 포화상태가 됩니다!!! 

삽입 알고리즘

 

 
enQueue(cQ, item) {
    if(isFull(cQ)) then Queue_Full();
    else {
        rear <- (rear + 1) mod n;
        cQ[rear] <- item;
    }
}

삭제 알고리즘

 

deQueue(cQ) {
    if(isEmpty(cQ)) then Queue_Empty();
    else {
        front <- (front + 1) mod n;
        return cQ[front];
    }
}

자 알고리즘은 이정도로 올려 드리고,

소스를 통해서 보겠습니다!!

배열로 구현한 원형 큐 예제입니다!

ArrayCQueue.java

 

package circularQueue;
 
import queue.Queue;
 
public class ArrayCQueue implements Queue {
    private int front;
    private int rear;
    private int queueSize;
    private String[] itemArray;
 
    public ArrayCQueue(int queueSize) {
        rear = front = 0;
        this.queueSize = queueSize;
        itemArray = new String[this.queueSize];
    }
 
    public boolean isEmpty() {
        return (front == rear);
    }
 
    public boolean isFull() {
        return (((rear + 1) % this.queueSize) == front);
    }
 
    public void enQueue(String item) {
        if (isFull()) {
            System.out.println("삽입 실패! 원형 큐가 꽉찼습니다!");
        } else {
            rear = (rear + 1) % queueSize;
            itemArray[rear] = item;
            System.out.println("삽입된 아이템 : " + item);
        }
    }
 
    public String deQueue() {
        if (isEmpty()) {
            System.out.println("삭제 실패! 원형 큐가 비어있습니다!");
            return null;
        } else {
            front = (front + 1) % queueSize;
            return itemArray[front];
        }
    }
 
    public void delete() {
        if (isEmpty()) {
            System.out.println("삭제 실패! 원형 큐가 비어있습니다!");
        } else {
            front = (front + 1) % queueSize;
        }
    }
 
    public String peek() {
        if (isEmpty()) {
            System.out.println("삭제 실패! 원형 큐가 비어있습니다!");
            return null;
        } else {
            return itemArray[(front + 1) % queueSize];
        }
    }
 
    public void printQueue() {
        if (isEmpty()) {
            System.out.println("원형 큐가 비어있습니다!");
        } else {
            System.out.print(" 원 형  큐 >> ");
 
            for (int i = (front + 1) % queueSize; i != (rear + 1) % queueSize; i = ++i
                    % queueSize)
                System.out.print(itemArray[i] + " ");
            System.out.println();
        }
    }
}
 

QueueMain.java

 

 
package circularQueue;
 
public class QueueMain {
    public static void main(String[] args) {
        int queueSize = 5;
 
        ArrayCQueue cQ = new ArrayCQueue(queueSize);
 
        cQ.enQueue("HELLO");
        cQ.enQueue("WORLD");
        cQ.printQueue();
 
        cQ.delete();
        cQ.enQueue("MAP");
        cQ.printQueue();
 
    }
}
 

결과는 아래와 같습니다!!

 

이번 예제의 queue 인터페이스는 이전에 작성한 걸로 끌어다 썼습니다!!!

연결 큐(Linked Queue)

배열로 구현하면 배열의 고질적 문제를 가지고 있게 되죠???

그럼 연결 리스트로 예제를 작성해 보도록 하겠씁니다!

QNode.java

 

 

package linkedQueue;
 
public class QNode {
    private String data;
    private QNode link;
 
    public String getData() {
        return data;
    }
 
    public void setData(String data) {
        this.data = data;
    }
 
    public QNode getLink() {
        return link;
    }
 
    public void setLink(QNode link) {
        this.link = link;
    }
 
}
 

LinkedQueue.java

 

 
package linkedQueue;
 
import queue.Queue;
 
public class LinkedQueue implements Queue {
 
    private QNode front;
    private QNode rear;
 
    public LinkedQueue() {
        front = null;
        rear = null;
    }
 
    public boolean isEmpty() {
        return (front == null);
    }
 
    public void enQueue(String item) {
        QNode newNode = new QNode();
        newNode.setData(item);
        newNode.setLink(null);
 
        if (isEmpty()) {
            front = newNode;
            rear = newNode;
        } else {
            rear.setLink(newNode);
            rear = newNode;
        }
        System.out.println("Inserted Item : " + item);
    }
 
    public String deQueue() {
        if (isEmpty()) {
            System.out.println("Deleting fail!! Linked Queue is empty!");
            return null;
        } else {
            String item = front.getData();
            front = front.getLink();
 
            if (front == null) {
                rear = null;
            }
 
            return item;
        }
 
    }
 
    public void delete() {
        if (isEmpty()) {
            System.out.println("Deleting fail!! Linked Queue is empty!");
        } else {
            front = front.getLink();
            if (front == null) {
                rear = null;
            }
        }
    }
 
    public String peek() {
        if (isEmpty()) {
            System.out.println("Peeking fail!! Linked Queue is empty!");
            return null;
        } else {
            return front.getData();
        }
    }
 
    public void printQueue() {
        if (isEmpty()) {
            System.out.println("Linked Queue is empty!");
        } else {
            QNode tmp = front;
            System.out.print("Linked Queue >> ");
 
            while (tmp != null) {
                System.out.print(tmp.getData() + " ");
                tmp = tmp.getLink();
            }
 
            System.out.println();
        }
    }
 
}
 

QueueMain.java

 

 
package linkedQueue;
 
public class QueueMain {
    public static void main(String[] args) {
        LinkedQueue lQ = new LinkedQueue();
 
        lQ.enQueue("THIS");
        lQ.enQueue("IS");
        lQ.enQueue("AWESOME");
        lQ.enQueue("!!");
        lQ.printQueue();
 
        System.out.println();
        System.out.println("삭제 후 출력한 큐");
 
        lQ.delete();
        lQ.delete();
        lQ.printQueue();
    }
}
 

결과는 아래와 같습니다!!!