[자료구조] 큐(Queue)

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

먼저 들어온 데이터가 먼저 나가는 것.

맛집 웨이팅처럼!

 

연산

create : 큐를 생성한다

init : 큐를 초기화한다.

is_empty(q) : 큐가 비어있는지 검사한다.

is_full(q) : 큐가 가득찼는지 검사한다.

enqueue(q, e) : 큐의 뒤에 요소를 추가한다.

dequeue(q) : 큐의 앞에 있는 요소를 반환한 다음 삭제한다.

peek(q) : 큐에서 삭제하지 않고 앞에 있는 요소를 반환한다.

 

배열을 이용한 선형큐

front : 첫번째 요소 하나 앞의 인덱스

rear : 마지막 요소의 인덱스

#include <iostream>

#define MAX_QUEUE_SIZE 3

typedef int element;
typedef struct {
    element queue[MAX_QUEUE_SIZE];
    int front, rear;
}Queue;

void init(Queue *q){
    q->front = q->rear = -1;
}

bool is_full(Queue *q){
    return q->rear == MAX_QUEUE_SIZE -1;
}
bool is_empty(Queue *q){
    return q->front == q->rear;
}

void enqueue(Queue *q, element e){
    if(is_full(q)){
        std::cerr << "Queue is full\n";
        exit(-1);
    }
    q->queue[++q->rear] = e;
}

element dequeue(Queue *q){
    if(is_empty(q)){
        std::cerr << "Queue is empty\n";
        exit(-1);
    }
    return q->queue[++q->front];
}

element peek(Queue *q){
    if(is_empty(q)){
        std::cerr << "Queue is empty\n";
        exit(-1);
    }
    return q->queue[q->front + 1];
}

int main(){
    Queue q;

    init(&q);
    enqueue(&q, 1);
    enqueue(&q, 2);
    enqueue(&q, 3);

    std::cout << std::boolalpha << is_full(&q) << "\n";     // true
    std::cout << dequeue(&q) << "\n";                       // 1
    std::cout << dequeue(&q) << "\n";                       // 2
    std::cout << peek(&q) << "\n";                          // 3
    std::cout << dequeue(&q) << "\n";                       // 3
    std::cout << std::boolalpha << is_empty(&q) << "\n";    // true
}

연결리스트를 이용한 연결된 큐

front : 첫번째 요소 하나 앞의 인덱스

rear : 마지막 요소의 인덱스

#include <iostream>

typedef int element;
typedef struct QueueNode{
    element data;
    QueueNode *link;
}QueueNode;

typedef struct{
    QueueNode * front, *rear;
}linkedQueue;

void init(linkedQueue *q){
    q->front = q->rear = nullptr;
}

bool is_full(linkedQueue *q){
    return false;
}
bool is_empty(linkedQueue *q){
    return q->front == nullptr;
}

void enqueue(linkedQueue *q, element data){
    QueueNode *temp = (QueueNode *)malloc(sizeof(QueueNode));
    
    if(temp == nullptr){
        std::cerr << "Memory Allocation Error\n";
        return;
    }
    temp->data = data;
    temp->link = nullptr;
    if(is_empty(q)){
        q->front = temp;
        q->rear = temp;
    }else{
        q->rear->link = temp;
        q->rear = temp;
    }
}

element dequeue(linkedQueue *q){
    if(is_empty(q)){
        std::cerr << "Queue is empty\n";
        exit(-1);
    }
    QueueNode *temp = q->front;
    element data = temp->data;

    q->front = q->front->link;
    if(q->front == nullptr)q->rear = nullptr;
    free(temp);
    return data;
}

element peek(linkedQueue *q){
    if(is_empty(q)){
        std::cerr << "Queue is empty\n";
        exit(-1);
    }
    return q->front->data;
}

int main(){
    linkedQueue q;

    init(&q);
    enqueue(&q, 1);
    enqueue(&q, 2);
    enqueue(&q, 3);

    std::cout << dequeue(&q) << "\n";                       // 1
    std::cout << dequeue(&q) << "\n";                       // 2
    std::cout << peek(&q) << "\n";                          // 3
    std::cout << dequeue(&q) << "\n";                       // 3
    std::cout << std::boolalpha << is_empty(&q) << "\n";    // true
}