c++ circular queue


#include <iostream> 
#include <assert.h>
using namespace std;
class CircularQueue {
private:
    int *mData;
    int mFront, mRear, mMaxSize;
public:
    CircularQueue();
    CircularQueue(int _data);
    ~CircularQueue();

    bool isFull();
    bool isEmpty();
    void push(int _data);
    int pop();
};

CircularQueue::CircularQueue()
    : mFront(0)
    , mRear(0)
    , mMaxSize(0)
    , mData(nullptr)
{}

CircularQueue::CircularQueue(int _maxsize)
    : mFront(0)
    , mRear(0)
    , mMaxSize(_maxsize) {
    mData = new int[_maxsize];
}

CircularQueue::~CircularQueue() {
    if (mData != nullptr) 
        delete[] mData;
}

bool CircularQueue::isFull() {

    return (mRear+1) % mMaxSize == mFront;
}

bool CircularQueue::isEmpty() {

    return (mFront == mRear);
}

void CircularQueue::push(int _data) {

    if (isFull()) {
    //  cout << "Circular Queue is Full. You can't push any data. Exiting program.." << endl;
        exit(0);
    }
    else {
        mRear = (mRear + 1) % (mMaxSize);
        mData[mRear] = _data;
        cout << "pushing complete!!" << endl;
    }

}

int CircularQueue::pop() {
    if (isEmpty()) {
        cout << "Circular Queue is Empty. You can't pop any data. Exiting program.." << endl;
        exit(0);
    }
    else {
        mFront = (mFront + 1) % (mMaxSize);
        return mData[mFront];
    }

}

int main() {
    CircularQueue queue(3);
    queue.push(1);
    queue.push(2);
    queue.push(3);
    cout << "Poping Elements : " << queue.pop() << endl;

    queue.push(4);
    cout << "Poping Elements : " << queue.pop() << endl;
    cout << "Poping Elements : " << queue.pop() << endl;
    cout << "Poping Elements : " << queue.pop() << endl;

    return 0;
}

Circular Queue(원형 큐)를 구현 해보려고 하는데요,
제가 밤새도록 해본 코드나, 교재에 나와있는 코드나, 인터넷에서 찾아볼 수 있는 코드들 모두 저 main프로그램을 실행을 못시키네요.. 주로 isFull()함수가 정확한 리턴값을 리턴하지 않거나 isEmpty()함수가 정확한 값을 리턴하지 못합니다.. 메인프로그램 내용은 원형 큐 이론상 맞는데, 계속 수정 하다하다 지쳐서 여쭤봅니다ㅠㅠ

맨 처음에 mFrontmRear-1로 초기화 시키는 경우,0으로 초기화 시키는경우 두가지에서 나눠서 해보았는데,

-1로 초기화 시켰을 때, PUSH 할 때 Full인지 검사하는 조건은,

newRear = (rear + 1) % maxSize; front == newRear

입니다. 하지만,newRearmaxSize로 모듈러스 한 것 이기 때문에 (0 ~ maxSize - 1)까지 값 밖에 가지지 못하는데, 한번도 POP하지 않은 상태(front == -1)일 때는 값을queue에 아무리 넣어도, Queue가 꽉 차있는 상태를 검사하지 못하는 문제가 있었습니다.

그래서, 조건을 front == newRear - 1;로 고쳐보았습니다.

Queue가 꽉차있을 때, (maxSize를 3으로 가정하겠습니다.) front = -1이고, Rear = 2 일 때 push를 하면 newRear = -1이 되어 Full인지 검사가 잘되었습니다. 하지만 맨 처음 넣을 때 front = -1, Rear = -1일 때 는 newRear가 -1이 되어, 아무것도 넣지 않았음에도 Queue가 꽉찬 상태인것처럼 되었습니다.

이와같은 문제가 끊임없이 일어납니다ㅠㅠ 답변좀 해주시면 감사하겠습니다(_ _)

  • 2016년 10월 18일에 작성됨
    컴퓨터공학과 재학중인 학생입니다.

조회수 110


1 답변


mFrontmRear의 의미를 다시 한번 생각해보는 것이 좋을 것 같습니다.

다음과 같이 생각하면 적절할 것 같네요.

  1. mFront는 큐의 맨 앞에 있는 원소를 가리킵니다.
  2. mRear는 큐에 새로운 원소가 추가될 수 있는 자리를 가리킵니다.

IsEmpty

IsEmpty의 경우는 mFront와 mRear가 같은 경우겠지요. 큐의 맨앞(mFront)가 새로운 원소가 추가될 자리(mRear)이기 때문입니다. 즉 원소가 하나도 없기 때문입니다.

IsFull

IsFull의 경우는 mRear가 새로운 여유공간을 가리킬 수 없을 때 입니다. 앞의 규칙에 따라서 mRear는 항상 새로운 원소가 추가될 수 있는 자리를 가리켜야 합니다.

  1. 즉 새로운 원소가 추가되었을 때.
  2. mRear가 가리키고 있던 자리에 새로운 원소가 추가되고,
  3. mRear는 그 다음 빈 공간을 가리켜야 합니다.
  4. 만약 mRear가 그 다음 빈공간을 찾지 못한다면 Full입니다.

mRear+1이 QueueSize와 같을 때입니다. 환형큐(Circular Queue)에서는 (mRear+1)%SIZEmFront와 같은 경우가 됩니다.

Enque or AddLast

  1. 따라서 push는 항상 data[mRear] = 추가할 원소를 하고나서
  2. mRear = (mRear + 1 )%SIZE와 같이 되어야 하며,
  3. 위 1,2를 하기전에 IsFull 체크가 선행되어서 IsFull인 경우 추가되지 않도록 해야 합니다.

Deque or RemoveFirst

  1. 먼저 IsEmpty를 체크(mFront == mRear)해서 비어있으면 실패처리
  2. 비어있지 않는 경우, data[mFront]값을 반환함과 함께 mFront = (mFront +1)%SIZE를 수행해야 합니다.

초기화

  1. mRear는 첫번째 빈자리를 가리켜야 함으로 0
  2. 아무것도 없으므로 mFirst는 mRear와 같은 값 0

올려주신 코드는 mFront와 mRear의 개념이 살짝 어그러져있는것 같습니다. 이와 같이 수정해서 해보세요.

  • 2016년 10월 18일에 작성됨
    리눅스(유닉스) 기반의 시스템에서 웹 서비스를 개발하고 있습니다.

  • 무조건 한칸을 비우고 사용하는게 맞나요? mMaxSize를 3으로 하고, 연속으로 3번넣으면 안되는데 그 이외에 상황은 다 되네요    이혁준   2016.10.19 14:18     
  • CircularQueue로 사용하려면 배열을 MaxSize+1로 해야 합니다. 결과적으로 남은 한개 원소자리가 IsEmpty와 IsFull을 구분해줍니다.    허대영(Daeyoung Heo)   2016.10.19 14:24     

로그인이 필요한 기능입니다.

Hashcode는 개발자들을 위한 무료 QnA사이트 입니다. 작성한 답변에 다른 개발자들이 댓글을 작성하거나 좋아요/싫어요를 할 수 있기 때문에 계정을 필요로 합니다.
► 로그인
► 계정만들기
Close