C++ Array Queue Implementation Method Errors

Question

I'm trying to implement a queue using an array within C++. I cannot for the life of me figure out why some of my methods are not working properly. My exists method does not find a value that's in the queue and my duplicate method is duplicating the rear of my queue instead of the front. The duplicate method should take whatever is at the front of the queue (given it's not empty or full), copy that value, and put it at the front of the queue. Mine will take the rear value, copy it, and put it one position from the rear. In addition, the Enqueue method is not properly inserting values.

#include <iostream>
#include "queue.h"

using namespace std;

static int nums[10];
int front = 0, rear = 0, sizeOfArray = 0;
int initialCapacity = 10;


int Enqueue(int num) {
    if (sizeOfArray == initialCapacity) {
        return -58;
    }
        for (int i = 0; i < initialCapacity; i++) {
            if (nums[i] == num) {
                return -62;
            }
            else {
                nums[rear] = num;
                rear = (rear + 1);
                sizeOfArray++;
                return 0;
            }   
    }
}

int Dequeue(int& num) {
    if (sizeOfArray == 0) {
        return -64;
    }
    front = (front + 1);
    sizeOfArray--;
    return 0;
}

int isEmpty() {
    if (sizeOfArray == 0) {
        return 1;
    }
    else {
        return 0;
    }
}

int Exists(int num) {
    for (int i = 0; i < sizeOfArray; i++) {
        int index = (front + i);
        if (nums[index] == num) {
            return 1;
        }
        else {
            return 0;
        }

    }
    return 0;
}

void Clear(void) {
    front = rear = sizeOfArray = 0;
}

void Print(void) {
    for (int i = 0; i < sizeOfArray; i++) {
        cout << nums[i] << " ";

    }
    cout << endl;
}


int Duplicate(void) {
    if (sizeOfArray == 0) {
        return -78;
    } 
    if (sizeOfArray == initialCapacity) {
        return -81;
    }
    int dupeNum;
    dupeNum = nums[front];

    nums[front + 1] = dupeNum;
    sizeOfArray++;
    return 0;
}

Whenever I do the following methods in a test driver: Enqueue 4 Enqueue 5 Exists 5 Duplicate Print

I get this output:

Test 1 0 - 0 indicates success

Test 2 0 - 0 indicates success

Test 3 0 - 0 indicates a failure

Test 4 0 - indicates a success

4 4 0

Answer 1

For a start, unless front is always zero, this code is not going to do what you expect:

int index = (front + i);
if (nums[index] == num) ...

That's because you will try to read the array beyond its end. You need to wrap around at the top end of the array, with something like:

int index = (front + i) % initialCapacity;

---

Other problems are:

• your queueing function checks for a duplicate in all elements of the array, even those that technically are not populated. You should only check the populated values (from front to front + sizeOfArray, with wrapping as detailed above).
• it also doesn't correctly handle wrap-around when you add an item. The next value of rear should wrap back to zero after inserting an element in the last array item: rear = (rear + 1) % initialCapacity.
• ditto for the dequeue and duplicate functions, when adjusting front.
• use of magic return codes is a bad idea, a better one would be to use an enumeration (see my code below for an example).
• your dequeue never actually places the dequed value into the reference parameter you pass in, meaning it will never be changed. Before you increment front (making sure you've fixed the wrapping), you can just do num = nums[front].

---

There may well be other problems but your biggest one is that, despite the use of certain C++ stuff, this is not really C++ code. The greatest mistake a C++ coder can make is to be a C+ coder, that strange breed lost halfway between the C and C++ worlds :-)

Your queue should really be a class rather than just stand-alone functions. That way, you can properly encapsulate it and protect the data from outside interference.

I won't tell you how to do that since it would make this answer intolerably long but, the sooner you start heading that way, the better a C++ programmer you will become.

---

For example, the following complete program shows one way to do this. I wouldn't hand this in as your own work but it's useful to get an idea as to how a C++ programmer may do it:

#include <cstdlib>
#include <memory>

template<class T>
class MyQ {
private:
    size_t m_sz, m_first, m_next, m_used;
    T *m_data;

public:
    enum RetCode { OK, FULL, EMPTY };

    MyQ(size_t sz = 10) : m_sz(sz), m_first(0), m_next(0), m_used(0), m_data(new T[sz]) {}
    ~MyQ() { delete [] m_data; }

    enum RetCode Enqueue(T item) {
        if (m_used == m_sz) return FULL;
        m_data[m_next] = item;
        m_next = (m_next + 1) % m_sz;
        ++m_used;
        return OK;
    }

    enum RetCode Dequeue(T &item) {
        if (m_used == 0) return EMPTY;
        item = m_data[m_first];
        m_first = (m_first + 1) % m_sz;
        --m_used;
        return OK;
    }
};

// The class proper is above, the following is just a test harness.

#include <iostream>

int main() {
    MyQ<int> x(6);
    for (int i = 0; i < 7; i++) {
        std::cout << "Enqueueing " << i << " returns " << x.Enqueue(i) << '\n';
    }
    std::cout << '\n';

    int val;
    for (int i = 0; i < 4; i++) {
        MyQ<int>::RetCode rc = x.Dequeue(val);
        if (rc == MyQ<int>::OK) {
            std::cout << "Dequeueing returns " << rc << ", value was " << val << '\n';
        } else {
            std::cout << "Dequeueing returns " << rc << '\n';
        }

        std::cout << "Enqueueing " << (i + 7) << " returns " << x.Enqueue(i + 7) << '\n';
    }
    std::cout << '\n';

    for (int i = 0; i < 7; i++) {
        MyQ<int>::RetCode rc = x.Dequeue(val);
        if (rc == MyQ<int>::OK) {
            std::cout << "Dequeueing returns " << rc << ", value was " << val << '\n';
        } else {
            std::cout << "Dequeueing returns " << rc << '\n';
        }
    }
    std::cout << '\n';
}

---

The output shows the various actions and error conditions:

Enqueueing 0 returns 0
Enqueueing 1 returns 0
Enqueueing 2 returns 0
Enqueueing 3 returns 0
Enqueueing 4 returns 0
Enqueueing 5 returns 0
Enqueueing 6 returns 1

Dequeueing returns 0, value was 0
Enqueueing 7 returns 0
Dequeueing returns 0, value was 1
Enqueueing 8 returns 0
Dequeueing returns 0, value was 2
Enqueueing 9 returns 0
Dequeueing returns 0, value was 3
Enqueueing 10 returns 0

Dequeueing returns 0, value was 4
Dequeueing returns 0, value was 5
Dequeueing returns 0, value was 7
Dequeueing returns 0, value was 8
Dequeueing returns 0, value was 9
Dequeueing returns 0, value was 10
Dequeueing returns 2