자료구조 순환큐

 

 

X는 초기 과정입니다. Rear와 Front는 0인 상태입니다.

 

 

#include <stdio.h>
#include <iostream>

using namespace std;

template <typename T>
class Test
{

// 변수 정의
private:
    T* cycleQueue;
    int maxSize = 0;
    int rear = 0;
    int front = 0;

public:
// 생성자
    Test(int count)
    {
        maxSize = count;
        // 의도적으로 크기를 1을 해서 빈 경우와 꽉찬 경우 비교
        cycleQueue = new T[maxSize + 1];
    }

    ~Test()
    {
        delete[] cycleQueue;
        cycleQueue = NULL;
    }




    int IsSize()
    {
    	// rear이 더 크므로 front를 빼면됨
        if (front <= rear)
            return rear - front;

		// rear이 더 작으므로 값 보정이 필요함
        return rear - front + maxSize + 1;
    }

    bool IsEmpty()
    {
    	// front와 rear이 같으면 비어있는 상황
        return front == rear;
    }

    void Enqueue(T t)
    {
        int position = 0;
        if (rear == maxSize)
        {
        	// 만약 최대크기면 0 으로 이동
            position = rear;
            rear = 0;
        }
        else
        	// 아닐 경우 rear값 올리기
            // 후위연산자이므로 position에 값 부여된 후 추가됨
            position = rear++;

        cycleQueue[position] = t;

        printf("Add ");
        printf("value : %d \n", t);
        Print();
    }

	// 한 번에 값 넣기 편하게 설정함
    void Enqueues(T* tP, int count)
    {
        for (int i = 0; i < count; i++)
        {
            Enqueue(*(tP + i));
        }
    }

    T Dequeue()
    {
        int position = front;
        if (front == maxSize)
        {
        	// 최대 값이면 0으로 이동
            front = 0;
        }
        else
            front++;

        return cycleQueue[position];
    }

	// 디버깅 장치들입니다.
    void Print()
    {
        printf("front : %d ", front);
        printf("rear : %d ", rear);
        printf("IsSize : %d ", IsSize());
        if (IsEmpty() == 1)
            printf("IsEmpty : TRUE\n");
        else
            printf("IsEmpty : FALSE\n");
    }

    void Print2()
    {
        printf("Before\n");
        printf("Value = %d ", Dequeue());
        Print();
        printf("After\n");
        Print();
    }
};

int main()
{
	// 공간 10 확보
    Test<int> testInt(10);

	// 5개 추가
    testInt.Enqueues(new int[5] {1, 2, 3, 4, 5}, 5);

	// 4개 출력 즉 1개 남게됨
    testInt.Print2();
    testInt.Print2();
    testInt.Print2();
    testInt.Print2();

    printf("--------------------\n");
    
    // 3개 추가
    testInt.Enqueues(new int[3] {6, 7, 8}, 3);

	// 4개 출력
    testInt.Print2();
    testInt.Print2();
    testInt.Print2();
    testInt.Print2();
    
    // 0개 남음

    return 0;
}

 

IsSize(현재 큐의 사이즈 입니다.)

=> front와 rear의 위치를 비교합니다. 만일 rear즉 데이터가 들어간 상황이라면 rear이 더 클 것입니다.

그러므로 rear - front로 값이 나오게 됩니다.

IsEmpty(큐가 비어있는지 입니다.)

=> rear == front인 경우입니다. 모든 데이터를 사용한 경우가 아니라면 같은 경우는 빈 경우밖에 없습니다.

Enqueue(데이터 한 개 추가입니다.)

=> 만약 최대값이라면 rear가 0이 되므로 , 순환의 형태가 됩니다.

Enqueues(데이터 여러 개를 한 번에 추가합니다.)

=> 그저 포인터와 사이즈를 받아와서 한 번에 추가하는 코드입니다.

Dequeue(데이터를 반환합니다.)

=> front값을 더하게 됩니다. position에 들어갈 때에는 후위 연산자로 값을 더하므로 positon에 값에 정상적으로 들어가게 됩니다. 

 

 

Add value : 1 
front : 0 rear : 1 IsSize : 1 IsEmpty : FALSE
Add value : 2 
front : 0 rear : 2 IsSize : 2 IsEmpty : FALSE
Add value : 3 
front : 0 rear : 3 IsSize : 3 IsEmpty : FALSE
Add value : 4 
front : 0 rear : 4 IsSize : 4 IsEmpty : FALSE
Add value : 5 
front : 0 rear : 5 IsSize : 5 IsEmpty : FALSE
Before
Value = 1 front : 1 rear : 5 IsSize : 4 IsEmpty : FALSE
After
front : 1 rear : 5 IsSize : 4 IsEmpty : FALSE
Before
Value = 2 front : 2 rear : 5 IsSize : 3 IsEmpty : FALSE
After
front : 2 rear : 5 IsSize : 3 IsEmpty : FALSE
Before
Value = 3 front : 3 rear : 5 IsSize : 2 IsEmpty : FALSE
After
front : 3 rear : 5 IsSize : 2 IsEmpty : FALSE
Before
Value = 4 front : 4 rear : 5 IsSize : 1 IsEmpty : FALSE
After
front : 4 rear : 5 IsSize : 1 IsEmpty : FALSE
--------------------
Add value : 6 
front : 4 rear : 6 IsSize : 2 IsEmpty : FALSE
Add value : 7 
front : 4 rear : 7 IsSize : 3 IsEmpty : FALSE
Add value : 8 
front : 4 rear : 8 IsSize : 4 IsEmpty : FALSE
Before
Value = 5 front : 5 rear : 8 IsSize : 3 IsEmpty : FALSE
After
front : 5 rear : 8 IsSize : 3 IsEmpty : FALSE
Before
Value = 6 front : 6 rear : 8 IsSize : 2 IsEmpty : FALSE
After
front : 6 rear : 8 IsSize : 2 IsEmpty : FALSE
Before
Value = 7 front : 7 rear : 8 IsSize : 1 IsEmpty : FALSE
After
front : 7 rear : 8 IsSize : 1 IsEmpty : FALSE
Before
Value = 8 front : 8 rear : 8 IsSize : 0 IsEmpty : TRUE
After
front : 8 rear : 8 IsSize : 0 IsEmpty : TRUE
--------------------
Before
Value = 0 front : 9 rear : 8 IsSize : 10 IsEmpty : FALSE
After
front : 9 rear : 8 IsSize : 10 IsEmpty : FALSE

[Execution complete with exit code 0]

 

컴파일러 사이트 : https://www.mycompiler.io/ko/new/cpp

 

아쉬운점은 마지막에 한 번 더 출력을 하게되면 IsSize가 스택오버플로우 처럼 최대값이 출력됩니다.

 

 

 

이론만 듣고 구현한다고 고민했었는데, 쉽사리 잊혀지지 않을 듯 합니다. 읽어주셔서 감사합니다.