chapter 2. 큐(queue)

 

 

 

여러분 안녕하세요? 오늘은 우리가 큐(queue)에 대해 배워보는 시간입니다. 지난 시간에 배웠던 스택에 비해서 큐는 조금 생소할 수도 있는데요...그래도 제가 차근 차근 열심히 설명도 하고 구현도 해보도록 하겠습니다. 

 

 

---

 

 

큐???

 

여러분들이 생각하는 큐는 무엇인가요? 제가 큐라는 단어를 제시했을 때, 무엇이 생각났나요? 

 

 

 

 

 

 

 

저는 이상하게 당구장 큐가 생각났습니다. 물론 제 생각이나 비유가 항상 답은 아니니까 참고만 하세요 ㅎㅎ....근데 아마 어느 정도 도움은 될 겁니다. 

 

 

 

 

 

 

 

큐 앞에 놓인 주황색 공을 앞으로 보내기 위해선 당연히 그 앞에 있는 빨간색 공부터 밖으로 보낼 수 밖에 없습니다. 너무나도 당연하죠. 우리가 오늘 배울 큐도 당구 큐와 그 원리가 똑같습니다. 

 

 

 

 

 

 

 

 

우리가 지난 시간에 배웠던 stack은 LIFO 구조였죠? 혹시 벌써 잊어버린건 아니죠?? ㅎ.... 큐는 처음 들어간 데이터가 가장 먼저 출력됩니다. 이를 First In First Out, FIFO라고 합니다. 

 

---

 

enqueue?, dequeue?

 

 

 

 

 

 

 

 

enqueue는 데이터를 넣는 과정을 칭하고 dequeue는 데이터를 밖으로 출력하는 과정을 말합니다. 마치 스택에서의 push와 pop 같은 역할을 해줍니다. 하지만 stack와 달리 데이터가 들어가고 나오는 과정은 다릅니다. 데이터의 입출력 과정을 다음과 같습니다. 

 

 

 

 

 

 

 

화살표의 방향때문에 조금 헷갈리수도 있는데 head가 앞쪽이고 tail이 뒤쪽입니다. enqueue를 하면 tail에 데이터가 들어가고 dequeue를 하면 데이터가 head에서 출력됩니다. 

 

---

 

 

C++로 queue 구현

 

 

queue.cpp

#include <iostream>
#define maxSize 5;

using namespace std;

class Queue
{

private:
    int front;
    int rear;
    int size;
    int *values;
    int number;

public:
    Queue()
    {

        size = maxSize;

        values = new int[size];

        front = 0;

        rear = 0;

        number = 0;
    }

    bool isEmpty()
    {

        if (number == 0)
        {

            return true;
        }
        else
        {

            return false;
        }
    }

    bool isFull()
    {

        if (number == size)
        {

            return true;
        }
        else
        {

            return false;
        }
    }

    void push(int value)
    {

        if (isFull() == true)
        {

            cout << "Queue is Full" << endl;
        }
        else
        {
            values[rear] = value;

            rear = (rear + 1) % size;

            number = number + 1;
        }
    }

    void pop()
    {

        if (isEmpty() == true)
        {
            cout << "Queue is Empty" << endl;
        }
        else
        {

            front = (front + 1) % size;

            number = number - 1;
        }
    }

    void print()
    {

        if (isEmpty() == true)
        {
            cout << "There is nothing" << endl;
        }
        else
        {

            int j = front;

            for (int i = 0; i < number; i++)
            {

                cout << values[j] << " ";

                j = (j + 1) % size;
            }

            cout << endl;
        }
    }
};

 

 

 

main.cpp

#include <iostream>
#include "queue.cpp"

using namespace std;

int main()
{

    Queue q;

    q.push(1);

    q.push(2);

    q.push(3);

    q.push(11);

    q.push(20);

    q.print();

    q.pop();

    q.pop();

    q.pop();

    q.print();

    q.pop();

    q.pop();

    q.pop();

    q.print();
}