(22.08.21)자료구조 7 - 큐(Queue)

큐란?

FIFO(선입선출)의 구조를 갖는 자료구조

Rear(후단)으로 데이터를 넣고,

Front(전단)으로 데이터를 빼는 자료보관이 가능한 자료 구조이다.

그림 1 단순 큐 - 출처 : https://www.programiz.com/java-programming/queue

 

응용

• 시뮬레이션의 대기열
• 통신에서 데이터 패킷들의 모델링
• 프린터와 컴퓨터 사이의 버퍼링(성능차)
• CPU의 태스크 스케줄링(Task Scheduling)
• 다양한 이벤트 구동 방식( Event-driven) 컴퓨터 시뮬레이션
• 이진 트리의 레벨 순회(Level-order Traversal)
• 그래프의 너비우선탐색(BFS) 등

ADT

Objects: 0개 이상 n개의 원소를 가진 유한 순서 리스트

 

Functions

• Queue createQueue()
  queue 만들기
• Bool is_empty(queue)
  queue가 비어있는 지에 대한 Bool값을 return
  
  
• Bool is_full(queue)
  queue가 가득찼는 지에 대한 Bool값을 return
  
  
• Queue enqueue(queue,data)
  queue의 Rear에 Data를 넣기
  
  
• Element dequeue(queue)
  queue의 front에 Data를 빼기

 

 

 

배열 기반 큐의 구현

단순 큐와 원형 큐

단순 큐는 그림 1과 같은 구조의 큐를 말한다.

문제는 단순 큐의 경우, 데이터가 enqueue되고 dequeue되는 과정이 반복되면 rear와 front가 점점 배열의 뒤쪽으로 가게 되면서

배열의 앞쪽을 쓰지 못하게 되는 메모리의 낭비가 발생하게 된다.

그림 2 - 출처: https://quescol.com/data-structure/circular-queue-representation-using-array

원형 큐는 이를 보완하기 위한 것으로 큐의 전단과 후단을 가르키는 rear와 front의 조작을 통해서 물리적은 아니지만 논리적으로 앞과 뒤과 연결되어 있는 원형의 자료구조이다.

하지만 원형큐에도 문제점이 있는데 바로 큐가 꽉찬 경우와 빈 경우가 구분이 안된다는 것이다.

그림 3 - 원형 큐에서 full과 empty가 구분이 안되는 문제상황

enqueue는 rear를 1 증가시키고 그 자리에 데이터를 넣는 방식인데,

이렇게 하게되면 꽉 찼을 때나, 비었을 때나 모두 rear와 front의 값이 같게 되어 full과 empty를 구별할 수가 없다.

그래서?

해결법은 바로 N-1만큼의 공간을 사용하고 N번째 메모리 공간은 비워두는 것이다.

그림 4 - N-1만큼의 공간을 쓰는 원형큐

 이렇게 되면 비어 있을 경우에는 front와 rear가 같은 위치를 가르키고, 가득 차있을 때는 front의 뒤에 rear가 위치하게 되어

두 상태의 구분이 가능해진다.

 물론, 혹자는 메모리가 1개 낭비된다고 지적할 수도 있지만 상태를 구분할 수 있다는 점을 생각한다면 상당히 합리적인 trade-off이다.

*별도의 boolean 변수를 이용할 수도 있다.(<- 큐의 단위 사이즈가 클 때에 활용하면 메모리를 크게 아낄 수 있다.)

구현 코드

typedef int data;
#define TRUE 1
#define FALSE 0

#define QUEUE_SIZE 100

typedef struct Queue {
    int front;
    int rear;
    data q_arr[QUEUE_SIZE];
} queue;

queue createQueue() {
    queue newQueue;
    newQueue.front = 0;
    newQueue.rear = 0;
    return newQueue;
}

int is_Empty(queue *q) {
    if (q->front == q->rear)
        return TRUE;
    else
        return FALSE;
};

int nextPostIdx(int pos) {
    if (pos == QUEUE_SIZE - 1)
        return 0;
    else
        return pos + 1;
}

int is_Full(queue *q) {
    if (nextPostIdx(q->rear) == q->front)
        return TRUE;
    else
        return FALSE;
}

void enqueue(queue *q, data value) {
    if(is_Full(q)){
        printf("The queue is full.");
        exit(-1);
    }
    q->rear = nextPostIdx(q->rear);
    q->q_arr[q->rear] = value;
}

data dequeue(queue *q){
    if(is_Empty(q)){
        printf("The queue is empty.");
        exit(-1);
    }
    q->front = nextPostIdx(q->front);
    return q->q_arr[q->front];
}

연결리스트 기반 큐의 구현

연결리스트 기반의 큐는 동적할당을 이용한 Node기반이기 때문에 위와 같이 단순 큐, 원형 큐 등의 개념이 필요하지 않다.

양방향 연결리스트에서의 head와 tail개념 처럼 front와 rear 포인터 변수를 운용하면된다.

주의할 점은 front변수로만 Empty를 체크한다는 것이다.

C 코드

typedef int data;
#define TRUE 1
#define FALSE 0


typedef struct _Node {
    data value;
    struct _Node *next
} node;

typedef struct Queue {
    node *front;
    node *rear;
} queue;

queue createQueue() {
    queue newQueue;
    newQueue.front = NULL;
    newQueue.rear = NULL;
    return newQueue;
}

int is_Empty(queue *q) {
    if (q->front == NULL)
        return TRUE;
    else
        return FALSE;
};

void enqueue(queue *q, data item) {
    node *newNode = (node *) malloc(sizeof(node));
    newNode->value = item;
    newNode->next = NULL;

    if(is_Empty(q)){
        q->front = newNode;
        q->rear = newNode;
    } else{
        q->rear->next = newNode;
        q->rear = newNode;
    }

}

JavaScript

class Node{
    constructor(data){
        this.data = data;
        this.next = null;
    }
}

class Queue{
 
    constructor(){
        this.front = null;
        this.rear = null;
    }

    isEmpty(){
        return this.front == null;
    }

    enqueue(data){
        const newNode = new Node(data);
        if(this.isEmpty()){
            this.front = newNode;
        } else {
            this.rear.next = newNode;
        }
        this.rear = newNode;
    }

    dequeue(){
        if(this.isEmpty()){
            console.log("Queue underflow error");
            return;
        }
        let val = this.front.data;
        this.front  = this.front.next;
        return val;
    }

    peek(){
        if(this.isEmpty()){
            console.log("Queue underflow error");
            return;
        }
        return this.front.data;
    }

}

덱(deque)

덱(deque)란 double-ended queue를 줄인 것으로,

양방향으로 전단과 후단 모두에서 삽입, 삭제가 가능한 큐이다.

 

양방향 연결리스트에서 head와 tail 개념을 그대로 이용하면 된다.

 

 

In C++

#include <queue> 를 통하여 queue 클래스를 사용할 수 있다.

queue 클래스의 메서드는 다음과 같다.

• empty
• size
• front
• back
• push_back
• pop_front

자세한 설명은 생략한다.

 

uderlying contatiner로서

• list
• dequeue

를 사용할 수 있으며, default container는 dequeue입니다.

 

In Java

자바에서 queue는 Linked-List를 컨테이너로 활용한다.

import java.util.LinkedList; //import
import java.util.Queue; //import
Queue<Integer> queue = new LinkedList<>(); //int형 queue 선언, linkedlist 이용
Queue<String> queue = new LinkedList<>(); //String형 queue 선언, linkedlist 이용

이런 식으로 사용하면 된다.

메서드는 다음과 같다.

• add
  후단에 값을 추가, 성공 시 true 반환, 큐의 크기를 넘으면 IllegalStateException 예외 발생
• offer
  후단에 값을 추가, 성공 시 true 반환, 큐의 크기를 넘으면 false를 반환
  일반적으로 크기 제한이 있는 큐의 경우, add보다 offer가 권장된다.
• poll
  전단의 값을 반환 및 제거, 비어 있으면 null 반환
• remove
  전단의 값을 반환 및 제거, 비어 있으면 NoSuchElment 예외 발생
• element
  전단의 값을 반환, 비어 있으면 NoSuchElment 예외 발생
• peek
  전단의 값을 반환, 비어 있으면 null 반환
• isEmpty
  비어있으면 True, 아니면 False 반환 (java.util.Collection 에서 상속받은 메소드)
• clear
  원소를 모두 삭제하고 초기화 (java.util.Collection 에서 상속받은 메소드)

 

참고 :

1. https://docs.oracle.com/javase/7/docs/api/java/util/Queue.html#add(E)  

2. https://cplusplus.com/reference/queue/queue/

3. <윤성우의 열혈 자료구조>