Queue Implementation Using a Circular Array

Question

I have to implement a queue using a circular array and am having difficulty. This is what should happen: The enqueue() function returns a bool value: true if the queue is non-full prior to enqueuing the value, false if the queue is already full in which case the value is not enqueued. The dequeue() function returns the dequeued value if the queue is non-empty, or 0 if the queue is empty.

here is IntegerArrayQueue.h (Don't change):

`#pragma once

#include <iostream>

using namespace std;

class IntegerArrayQueue
{
    private:
        int* array; //pointer to array of integers
        int front; //index of item to dequeue
        int back; //index of item to enqueue
        int size;

    public:
        IntegerArrayQueue() :
            array(new int[10]), front(0), back(9), size(10)
            {
                for (int i = 0; i<10; i++) array[i]=0;
            }
        IntegerArrayQueue(int size) :
            array(new int[size]), front(0), back(size-1), size(size)
            {
                for (int i = 0; i<size; i++) array[i]=0;
            }
        ~IntegerArrayQueue() { delete [] array;}
        void printArrayQueue()
        {
            for (int i = 0; i<size; i++) cout << array[i] << " ";
            cout << endl;
            cout << "front: " << front << endl;
            cout << "back: " << back << endl;
            cout << "size: " << size << endl;
        }
        //Implement the enqueue and dequeue functions
        //enqueue: if there is space available enqueue value and
        //return true, otherwise return false
        bool enqueue(int value);
        
        //dequeue: if there is a value at the front of the queue
        //return the value and remove from the queue,
        //otherwise return 0
        int dequeue();

};`

IntegerArrayQueue.cpp:

`#include "IntegerArrayQueue.h"


bool IntegerArrayQueue::enqueue(int value)
{
    if ((back + 1) % size == front) {
      return false;
    }

    else {
        back = (back + 1) % size;
        array[back] = value;
        return true;
    }
}

int IntegerArrayQueue::dequeue()
{
    if (front == 0) {
        return 0;
    }
    else {
        int val = array[front];
        if (front == back) {
            front = 0;
            back = 0;
        }
        else {
        front = (front) % size;
        }
        return val;
    }
}`

anyone have any guidance on what i'm doing wrong in IntegerArrayQueue.cpp:

confused on what i'm doing wrong

dequeue() returns 0 if front is 0 but regardless of back. In dequeue() you never move front forward. Why not to use standard container instead of raw pointer to C-style array? — dimich
– dimich, Commented May 6, 2024 at 17:50
Odd that you want a circular array, but won't add to the queue when it's full. The point of circular arrays is to overwrite old data. — sweenish
– sweenish, Commented May 6, 2024 at 18:07
Just a small note, never use "using namespace anything", especially std in header files. It can lead to really bad situations. More stackoverflow.com/questions/5849457/… — aturt13
– aturt13, Commented May 6, 2024 at 18:45
Side note: You don't need to initialize values in a queue. The customer will initialize the queue by inserting numbers into it. The customer will never see the initial values you put in there. — Thomas Matthews
– Thomas Matthews, Commented May 6, 2024 at 19:32
I was taught that there should be a flag to differentiate a full queue from an empty one. When back == front, the queue is either full or empty. — Thomas Matthews
– Thomas Matthews, Commented May 6, 2024 at 19:33

dimich · Accepted Answer · 2024-05-06 19:53:15Z

Besides of raw pointer (supposing you want it for some reason), your implementation has several problems.

IntegerArrayQueue(int size) {
...
    for (int i = 0; i<10; i++) array[i]=0;

Dequeuing empty queue shall return a fixed value, so you don't need to initialize entire array with it.

bool IntegerArrayQueue::enqueue(int value)
{
    if ((back + 1) % size == front) {
      return false;
    }
...

In general you can't use entire array and distinguish empty queue from full queue with only two variables (front and back). In both cases front == back, so you either waste 1 element of array or need boolean flag to distingush empty queue from full queue.

    }
    else {

else is redundant if function returned in previous block.

int IntegerArrayQueue::dequeue()
{
    if (front == 0) {
        return 0;
    }

front can be 0 even if queue is not empty.

front = (front) % size;

This doesn't change front.

Naive straightforward implementation may be the following:

template <typename T>
class ring
{
    T *data;
    std::size_t size;
    std::size_t front { 0 };
    std::size_t back  { 0 };
    bool full { false };
public:
    ring(std::size_t _size) : data{new T[_size]}, size{ _size } {}

    ~ring() {
        delete [](data);
    }

    bool enqueue(T value) {
        if (full) {
            return false;
        }
        data[back] = value;
        back = (back + 1) % size;
        if (back == front) {
            full = true;
        }
        return true;
    }

    T dequeue() {
        if ((front == back) && !full) {
            return {};
        }
        full = false;
        std::size_t old_front = front;
        front = (front + 1) % size;
        return data[old_front];
    }
};

Usage example:

ring<int> ring { 3 };

std::cout << "Dequeue empty: " << ring.dequeue() << '\n';
std::cout << std::boolalpha;

for (int i = 1; i <= 5; ++i) {
    std::cout << "Enqueue " << i << ": " << ring.enqueue(i) << '\n';
}

for (int i = 1; i <= 5; ++i) {
    std::cout << "Dequeue " << i << ": " << ring.dequeue() << '\n';
}

Output:

Dequeue empty: 0
Enqueue 1: true
Enqueue 2: true
Enqueue 3: true
Enqueue 4: false
Enqueue 5: false
Dequeue 1: 1
Dequeue 2: 2
Dequeue 3: 3
Dequeue 4: 0
Dequeue 5: 0

Collectives™ on Stack Overflow

Queue Implementation Using a Circular Array

1 Answer 1

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related