Queue/큐(원형 큐)

큐는 데이터를 처리하기 위해 일시적으로 쌓아 놓은 자료구조이다. 하지만 큐는 스택과는 다르게

가장 먼저 넣은 데이터를 가장 먼저 꺼내는 선입선출(FIFO, First In First Out)인 점이 스택과 다르다.

쉽게 이해하려면 은행 창구나 선착순 시스템을 생각하면 된다 먼저 온 사람한테 서비스를 제공하듯이

큐도 먼저 들어온 데이터부터 우선 처리해준다. 선형 큐도 있지만 원형 큐를 구현할 줄 알면 선형 큐도

구현할 수 있으니 굳이 설명하지 않는다.

 

코드

#include <iostream>
using namespace std;

struct queue{
    int max; // 큐의 최대 용량
    int size; // 현재 요소의 개수
    int front; // 프런트
    int rear; // 리어
    int *que; // 큐의 맨 앞 요소에 대한 포인터
};

int que_init(queue* q, int max){ // 큐를 초기화
    q->size = q->front = q->rear = 0;
    if((q->que = new int[max]) == NULL){
        q->max = 0;
        return -1;
    }
    q->max = max;  
    return 0;
}

int enque(queue* q, int data){ // 인큐 함수
    if(q->size >= q->max){
        return -1;
    }
    else{
        q->size++; // 사이즈를 늘려주고 
        q->que[q->rear++] = data; // 데이터를 삽입하고 rear++
        if(q->rear == q->max){
            q->rear = 0;
        }
        return 0;
    }
}

int deque(queue* q){ // 디큐 함수
    if(q->size <= 0){
        return -1;
    }
    else{
        q->size--; // 사이즈를 줄여주고
        q->que[q->front++]; // front++ 이러면 큐의 구조에서는 다시 디큐한 데이터에 접근할수 없다.
        if(q->front == q->max){
            q->front = 0;
        }
        return 0;
    }
}

int peek(const queue* q){ // 프런트의 값을 반환
    if(q->size <= 0){
        return -1;
    }
    return q->que[q->front];
}

void Clear(queue* q){
    q->size = q->front = q->rear = 0;
}

int capacity(queue* q){
    return q->max;
}

int size(const queue *q){
    return q->size;
}

int isEmpty(const queue *q){
    return q->size <= 0;
}

int isFull(const queue *q){
    return q->size >= q->max;
}

int search(const queue *q, int key){
    for(int i = 0, idx; i < q->size; i++){
        if(q->que[idx = (i + q->front) % q->max] == key){ // 인덱스를 구하는 식 (i + front의 위치)  % 큐의 최댓값
            return idx;
        }
    }
    return -1;
}

void que_terminate(queue *q){
    if(q->que != NULL){
        delete q->que;
    }
    q->max = q->size = q->front = q->rear = 0;
}

int main(){
    queue* q = new queue;
    que_init(q, 10);
    for(int i = 0; i < 10; i++){
        enque(q,i);
        cout << "enque : " << i << endl;
    }
    cout << size(q) << endl;
    cout << "search is 6 " << search(q,6);
    que_terminate(q);
    return 0;
}