#include <iostream>
#include <unistd.h>
#include <stdlib.h>
#include <string.h>
#include <stdio.h>

using namespace std;

template <typename T1>
class Queue
{
    private:
        int MaxSize; 
        int DataIndex; 
        int QueueSize; 
        T1  *Array; 
        int PushNum;
    public:
        // 생성자로써 디폴트 아규먼트로 
        // 큐의 사이즈를 지정했다. 
        // 아규먼트로 넘어온 크기만큼 Array 의 크기를 
        // 할당하고 기타 멤버변수들의 값을 적당히 초기화 한다.
        Queue(int size=40)
        {
            MaxSize = size;
            Array = (T1 *)malloc(sizeof(T1)*MaxSize);
            QueueSize = 0;
            DataIndex = 0;
            PushNum   = 0;
        }
        // 소멸자 자원을 해제한다.
        ~Queue()
        {
            free(Array);
        }
        // Array에 원소를 입력한다. 
        // 만약에 Array 의 크기를 초과해서 원소가 들어갈경우 
        // MaxSize*2 크기만큼 메모리의 크기를 재할당한다.  
        void push_back(T1 x)
        {
            if (QueueSize > MaxSize - 1)
            {
                MaxSize *= 2; 
                if ((Array = (T1 *)realloc(Array, sizeof(T1)*MaxSize)) == NULL)
                {
                    perror("realloc error:");   
                    exit(0);
                }
                cout << "Realloc OK" << endl;
            }
            Array[PushNum%MaxSize] = x;
            PushNum++;
            QueueSize++;
        }
        // 데이타를 꺼낸다. 
        T1 pop()
        {
            QueueSize--; 
            DataIndex++;
            return Array[(DataIndex-1)%MaxSize]; 
        }
        // 큐에 있는 데이타의 갯수를 얻어온다.
        int size()
        {
            return QueueSize;
        }
        // 큐의 크기를 얻어온다.
        int capacity()
        {
            return MaxSize;
        }
        // 원소를 삭제한다. 
        // 실제 데이타를 free 시키지는 않고, Index
        // 값들을 조정해서 삭제한것 처럼 보이게 한다.
        void clear()
        {
            QueueSize = 0;
            DataIndex = 0;
            PushNum   = 0;
        }
};

int main()
{
    Queue<char *> myqueue(4);
    cout << "Queue capacity "  << myqueue.capacity() << endl;
    myqueue.push_back("hello 1");
    myqueue.push_back("hello 2");
    myqueue.push_back("hello 3");
    myqueue.push_back("hello 4");
    myqueue.push_back("hello 5");
    myqueue.push_back("hello 6");
    int size = myqueue.size();
    for (int i = 0; i < size; i++)
        cout << myqueue.pop() << endl;

    myqueue.push_back("hello 1");
    myqueue.push_back("hello 2");
    myqueue.push_back("hello 3");
    myqueue.push_back("hello 4");

    for (int i = 0; i < size; i++)
        cout << myqueue.pop() << endl;

    cout << "Queue capacity "  << myqueue.capacity() << endl;
    myqueue.clear();
    cout << "Queue Size " << myqueue.size() << endl;
}