CircularArray(환형 배열, queue)

환형 큐(이하 Circular Queue)에 대해서 간략히 설명해보겠습니다.

보통 스택이나 큐 같은 자료구조는 선형모양의 구조를 가지고 있는데요...

하지만 큐로 단순히 선형모양의 구조를 이용해 구현하게 된다면 문제점이 발생하죠..

바로 Front, rear사이에서 dequeue(앞 노드를 삭제)가 계속 이루어지고 enqueue(맨 뒤에 노드를 추가)작업을 하게되면 초기 배열의 N값을 넘어가게되면 추가를 못하게 되고 이전에 dequeue를 작업했던 front 앞의 배열공간들을 사용하지 못한다는게 단점인데요. 이 단점을 극복하고자 만들어진 구조가 바로 Circular queue가 되겠습니다.

사실은 별거 없구...

Enqueue 수행 시 => rear = (rear+1) Mod N

Dequeue 수행 시 => front = (front+1) Mod N

이것만 기억해두고 소스를 보시면 쉽게 이해하실 듯 합니다.

/*

Circular_Array.cpp

Made by hahahia

*/

#include <iostream>

#include <string>

using namespace std;

 

class CircularArray{

private:

        int N;

        string data[5];

        int n; // ArraySize

        int f; // front

        int r; // rear

public:

        CircularArray() : f(0), r(0), n(0), N(5) {} // Constructor

        void Enqueue(string str); // Insert

        void Dequeue(); // Remove

        bool isEmpty(); // Empty check

        void elemAtRank(int i); // at

        int size(); // size

        string front();

};

 

bool CircularArray::isEmpty(){

        return (n==0);

}

 

int CircularArray::size(){

        return n;

}

 

string CircularArray::front(){

        if(isEmpty())

        {

               cout << "error" << endl;

               return 0;

        }

        return data[f];

}

void CircularArray::Enqueue(string str){

        if(size() == N){

               cout << "error!!" << endl;

               return;

        }

        data[r] = str;

        r = (r+1)%N;

        n++;

        return;

}

 

void CircularArray::Dequeue(){

        if(isEmpty())

        {

               cout << "error" << endl;

               return;

        }

        string temp;

        temp = data[f];

        f = (f+1)%N;

        n--;

        cout << "delete : " << temp << endl;

}

void CircularArray::elemAtRank(int i){

        if(i>n-1)

        {

               cout << "error" << endl;

               return;

        }

        else cout << data[(i + f) % N] << endl;

}

int main(){

        CircularArray A;

        A.Enqueue("hahahia");

        A.Enqueue("qwerty");

        A.Enqueue("Inha");

        A.Enqueue("Computer Science");

        cout << A.front() << endl;

        A.elemAtRank(3);

        A.Dequeue();

        A.elemAtRank(0);

        A.elemAtRank(2);

        A.Enqueue("Science");

        A.Dequeue();

        A.elemAtRank(2);

        A.elemAtRank(3); // error

        A.Enqueue("tas");

        A.elemAtRank(3);

        A.Enqueue("asdf");

        A.elemAtRank(4);

        A.Dequeue();

        A.elemAtRank(0);

        return 0;

}