Queue 란?

선입선출(FIFO: First-In First-Out)의 특성을 가지는 기본적인 자료구조(Data Structure)중 한가지다.

Queue에서의 데이터 입력은 뒤에서 새로운 데이터가 추가되고 앞에서 데이터가 하나씩 삭제되는 구조를 가진다.

Queue에서 삽입이 일어나는 곳을 후단(rear) 이라 하고 삭제가 일어나는 곳을 전단(front) 이라고 한다.

DataStructure_Queue

Queue의 연산

  • enqueue() : 삽입 연산으로 큐의 맨 뒤에 새로운 요소를 추가한다.
  • dequeue() : 삭제 연산으로 큐의 맨 앞에 있는 요소를 꺼내서 반환한다.
  • is_empty() : 큐가 공백상태에 있는지 검사한다.
  • is_full() : 큐가 포화상태에 있는지 검사한다.
  • peek() : 큐의 맨 앞에 있는 요소를 읽어서 반환한다.

DataStructure_Queue

Queue의 구현

Queue을 구현하는 방법이 여러 가지이나 이번에는 1차원 배열을 쓰는선형큐(Linear Queue)와 원형큐(Circular Queue) 두가지 방법을 다뤄 보겠다.

선형큐(Linear Queue)

1차원의 배열을 정의하고 삽입, 삭제를 위한 변수인 front와 rear를 만든다.

  • front는 Queue의 첫 번째 요소를 가리킨다.
  • rear는 Queue의 마지막 요소를 가리킨다.
#include <stdio.h>
#include <stdlib.h>

#define MAX_QUEUE_SIZE 5

typedef ine element;
typedef struct{
    int front;
    int rear;
    element data[MAX_QUEUE_SIZE];
} QueueType;

//오류 함수
void error(char *message){
    fprintf(stderr, "%s\n", message);
    exit(1);
}

void init_queue(QueueType *q){
    q->rear = -1;
    q->front = -1;
}
void queue_print(QueueType *q){
    for(int i = 0; i < MAX_QUEUE_SIZE; i++){
        if(i <= q->front || i > q->rear)
            printf(" | ");
        else
            printf("%d | ", q->data[i]);
    }
    printf("\n");
}

//포화상태 검출
int is_full(QueueType *q){
    if(q->rear == MAX_QUEUE_SIZE - 1)
        return 1;
    else
        return 0;
}
//공백상태 검출
int is_empty(QueueType *q){
    if(q->front == q->rear)
        return 1;
    else
        return 0;
}
//삽입연산
void enqueue(QueueType *q, int item){
    if(is_full(q)){
        error("큐가 포화상태입니다.");
        return;
    }
    q->data[++(q->rear)] = item;
}
//삭제연산
int dequeue(QueueType *q){
    if(is_empty(q)){
        error("큐가 공백상태입니다");
        return -1;
    }
    int item = q->data[++(q->front)];
    return item;
}

int main(void){
    int item = 0;
    QueueType q;

    init_queue(&q);

    enqueue(&q, 10); queue_print(&q);
    enqueue(&q, 20); queue_print(&q);
    enqueue(&q, 30); queue_print(&q);

    item = dequeue(&q); queue_print(&q);
    item = dequeue(&q); queue_print(&q);
    item = dequeue(&q); queue_print(&q);
    return 0;
}

실행 결과

10 |    |    |    |    |
10 | 20 |    |    |    |
10 | 20 | 30 |    |    |
   | 20 | 30 |    |    |
   |    | 30 |    |    |
   |    |    |    |    |



원형큐(Circular Queue)

front와 rear의 값이 배열의 끝에 도달하면 다음의 증가되는 값은 0이 되도록한다.

원형큐에서는 front와 rear의 개념이 약간 변경된다.

  • 초기값은 -1이 아닌 0이다.
  • front는 항상 큐의 첫 번째 요소의 하나 앞을, rear는 마지막 요소를 가리킨다.
  • front와 rear의 값이 같으면 원형큐가 비어있음을 나타낸다.
  • 포화 상태와 공백 상태를 구별하기 위해 하나의 자리는 항상 비워둔다.

//공백상태 검출
int is_empty(QueueType *q){
    return (q->front == q->rear);
}

//포화상태 검출
int is_full(QueueType *q){
    return((q->rear + 1) % MAX_QUEUE_SIZE == q->front);
}

//삽입연산
void enqueue(QueueType *q, element item){
    if(is_full(q))
        error("큐가 포화상태입니다");
    q->rear = (q->rear + 1) % MAX_QUEUE_SIZE;
    q->data[q->rear] = item;
}

//삭제함수
element dequeue(QueueType *q){
    if(is_empty(q))
        error("큐가 공백상태입니다");
    q->front = (q->front + 1) % MAX_QUEUE_SIZE;
    return q->data[q->front];
}

//원형큐 출력
void queue_print(QueueType *q){
    printf("QUEUE(front = %d rear = %d) = ", q->front, q->rear);
    if(!is_empty(q)){
        int i = q->front;
        do{
            i = (i + 1) % (MAX_QUEUE_SIZE);
            printf("%d | ", q->data[i]);
            if(i == q->rear)
                break;
        }while(i != q->front);
    }
}

Java에서의 Queue

Java에서의 Queue는 LinkedList를 활용하여 생성해야한다.

import java.util.LinkedList와 import java.util.Queue을 import 해준후에

Queue<> queue = new LinkedList<>() 와 같이 선언해주면 된다.

Queue 선언

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

Queue<Integer> queue = new LinkedList<>();
Queue<String> queue = new LinkedList<>();

Queue 메서드

Queue<Integer> queue = new LinkedList<>();
queue.add(1);   //queue에 1추가
queue.offer(2); //queue에 2추가
queue.peek();   //queue의 첫 번째 값 참조
queue.poll();   //queue의 첫 번째 값을 반환후 제거, 비어 있다면 null
queue.remove(); //queue의 첫 번째 값 제거
queue.clear();  //queue 초기화