[Cpp]큐 구현

🤔큐

🔑배열로 큐 구현

큐는 스택과 다르게 뒤로 집어 넣고 앞에서 꺼내는 방식이라서 처음(head)과 끝(tail)을 나타내는 인덱스가 필요합니다. 일단 배열의 인덱스는 0부터 시작하므로 head와 tail 인덱스들을 -1로 초기화해줍니다.

const int QUEUE_SIZE = 10;

struct Queue
{
    int container[QUEUE_SIZE]{};
    int head{-1};
    int tail{-1};
};

정수를 큐에 넣고자(Enqueue) 한다면 tail 인덱스를 하나 증가시킨 곳에 해당 정수를 큐 배열에 넣으면 됩니다.

정수를 큐에서 빼고자(Dequeue) 한다면 큐 배열에서 head 인덱스를 하나 증가시켜줍시다.

큐에 원소가 들어가면 tail이 증가하고 원소가 빠지면 head가 증가합니다. 따라서, head와 tail이 같아지면 큐 배열에는 원소가 없는 상태입니다.

큐의 사이즈를 구할때는 tail 인덱스에서 head 인덱스를 빼주면 됩니다.

🔑전체 소스 코드

#include <iostream>
#include <string>
 
const int QUEUE_SIZE = 10;
 
struct Queue
{
    int container[QUEUE_SIZE]{};
    int head{-1};
    int tail{-1};
};
 
void UserInput(Queue& queue, std::string temp);
void Enqueue(Queue& queue, int value);
void Dequeue(Queue& queue);
void Size(Queue& queue);
void Empty(Queue& queue);
void Print(Queue& queue);
 
int main()
{
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
 
    Queue myQueue;
 
    while (true)
    {
        std::string temp;
 
        std::cin >> temp;
 
        UserInput(myQueue, temp);
 
        if (temp == "quit")
        {
            break;
        }
    }
}
 
void UserInput(Queue& queue, std::string temp)
{
    if (temp == "enqueue")
    {
        int value;
 
        std::cin >> value;
 
        Enqueue(queue, value);
    }
    else if (temp == "dequeue")
    {
        Dequeue(queue);
    }
    else if (temp == "size")
    {
        Size(queue);
    }
    else if (temp == "empty")
    {
        Empty(queue);
    }
    else if (temp == "print")
    {
        Print(queue);
    }
    else
    {
        return;
    }
}
 
void Enqueue(Queue& queue, int value)
{
    if (queue.tail == QUEUE_SIZE - 1)
    {
        return;
    }
 
    queue.container[++queue.tail] = value;
}
 
void Dequeue(Queue& queue)
{
    if (queue.head == queue.tail)
    {
        std::cout << -1 << '\n';
        return;
    }
 
    std::cout << queue.container[++queue.head] << '\n';
}
 
void Size(Queue& queue)
{
    std::cout << queue.tail - queue.head << '\n';
}
 
void Empty(Queue& queue)
{
    if (queue.head == queue.tail)
    {
        std::cout << 1 << '\n';
    }
    else
    {
        std::cout << 0 << '\n';
    }
}
 
void Print(Queue& queue)
{
    for (int i = 0; i < QUEUE_SIZE - 1; i++)
    {
        if (i <= queue.head || i > queue.tail)
        {
            std::cout << " ";
        }
        else
        {
            std::cout << queue.container[i] << " ";
        }
    }
    std::cout << '\n';
}