[자료구조] 큐, Queue

큐 : LIFO(Last in First Out)을 만족하는 자료구조

마지막으로 들어온 데이터가 가장 먼저 나간다.

 

배열과 비슷하게 front와 rear을 통해 데이터에 접근할 수 있다.

front는 가장 나중에 들어온 데이터에 접근할 수 있고

rear는 가장 먼저 들어온 데이터에 접근할 수 있다.

 

배열을 통해 큐를 구현할 때 선형적으로 구현하면 데이터를 계속해서 이동시켜야한다.

 

이것은 알고리즘상 매우 비효율적이라서 사용하지 않고 원형 큐를 통해 구현해서 이러한 문제를 해결한다.

 

 

이렇듯 원형큐는 선형큐의 처음과 끝은 연결한 형태이다.(메모리 상으로는 선형큐와 다르지 않다)

 

 

 

### 원형 큐, CurcularQueue ###

원형큐 UML diagram

 

 

# 삽입, 삭제 연산, enqueue(), dequeue() #

나머지연산(mod) 를 통해 원형 큐를 만들 수 있다.

 

ex) 원형 큐의 크기가 5인 상황에서 rear가 4일때 enqueue를 한다면 rear가 0이 되어야한다.

이때 (rear+1) mod MAX_QUEUE_SIZE; 나머지 연산을 한다면 0이 되는 것을 알 수 있다.

void enqueue(int val)
    {
        if (isFull()) error(" error : 큐가 포화상태입니다");
        else {
            rear = (rear + 1) % MAX_QUEUE_SIZE;
            data[rear] = val;
        }
    }

int dequeue()
    {
        if (isEmpty()) error("큐가 공백상태입니다");
        else
        {
            front = (front + 1) % MAX_QUEUE_SIZE;
            return data[front];
        }
    }

    bool isEmpty()
    {
        return rear == front;
    }
    bool isFull()
    {
        return front == (rear + 1)%MAX_QUEUE_SIZE;
    }

#include<iostream>
#define MAX_QUEUE_SIZE 100
#pragma once
#include <stdio.h>
#include <stdlib.h>
 
inline void error(const char* message)
{
    printf("%s", message);
    exit(1);
}
 
class CircularQueue
{
private:
    int front;
    int rear;
    int data[MAX_QUEUE_SIZE];
public:
    CircularQueue()
    {
        front = rear = 0;
    }
    bool isEmpty()
    {
        return rear == front;
    }
    bool isFull()
    {
        return front == (rear + 1)%MAX_QUEUE_SIZE;
    }
 
    void enqueue(int val)
    {
        if (isFull()) error(" error : 큐가 포화상태입니다");
        else {
            rear = (rear + 1) % MAX_QUEUE_SIZE;
            data[rear] = val;
        }
    }
 
    int dequeue()
    {
        if (isEmpty()) error("큐가 공백상태입니다");
        else
        {
            front = (front + 1) % MAX_QUEUE_SIZE;
            return data[front];
        }
    }
    int peek()
    {
        if (isEmpty())
        {
            if (isEmpty()) error("큐가 공백상태입니다");
            else
                return data[(front + 1) % MAX_QUEUE_SIZE];
        }
    }
    void display()
    {
        printf("큐 내용 : ");
        int maxi = (front < rear) ? rear : rear + MAX_QUEUE_SIZE;
        for (int i = front + 1; i <= maxi; i++)
        {
            printf("[%2d]", data[i%MAX_QUEUE_SIZE]);
        }
        printf("\n");
    }
};