c++ circular queue

Asked 2 years ago, Updated 2 years ago, 99 views

#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;
}

I'm going to implement Circular Queue.
All the code I've done all night, the code in the textbook, the code I can find on the Internet, all fail to run that main program. Mainly, the isFull() function does not return the correct return value or The isEmpty() function does not return an exact value. The content of the main program is correct in terms of circular cue theory, but I'm asking because I'm tired of modifying itㅠ<

If mFront and mRear are initialized to -1 at first, if 0 is initialized, I tried it separately from two things.

When initializing to -1, the condition of checking whether it is full when PUSH is

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

That's it. However, newRear is modular to maxSize, so it only has a value up to (0~maxSize-1), and when it has never been POP, there is a problem that queue cannot be checked.

So, we fixed the condition to front == newRear-1;.

When the queue is full, assume (maxSize) is 3.) If you push when front = -1 and Rear = 2, newRear = -1, and the full recognition test went well. However, when front = -1 and Rear = -1 at the beginning, the newRear becomes -1, so the queue seems to be full even though there is nothing in it.

Problems like this are constantly happeningcrying I'd appreciate it if you could reply (__)

c++ data-structure

2022-09-22 20:55

1 Answers

I think it would be better to reconsider the meaning of mFront and mRear.

I think it would be appropriate if you think about it as follows.

In the case of IsEmpty, mFront and mRear are the same. This is because the front of the queue (mFront) is where the new element will be added (mRear). That's because there's no element.

IsFull is when mRear cannot point to a new free space. According to the previous rule, mRear should always point to the place where a new element can be added.

mRear+1 is equal to QueueSize. In circular queue, (mRear+1)%SIZE and mFront.

The code you posted seems to have a slightly distorted concept of mFront and mRear. Please modify it like this and do it.


2022-09-22 20:55

If you have any answers or tips


© 2024 OneMinuteCode. All rights reserved.