Queue implementation and array resizing using C++

Question

The code is supposed to do queue functions which I got right.

The only problem I am having is: I am supposed to double the array size to twice its original size once the array gets completely filled.

I have coded for it but still getting garbage values when I try to put in more values than the original array size. So the problem seems to be in the inc() function below:

#ifndef Q_H_
#define Q_H_

#include <iostream>
using namespace std;



template <class elemType>
class arrayQueue
{
    int size;
    int *array;
    int front;
    int back;
    int count;

public:
    arrayQueue(elemType size)
{
        this->size = size;
        array = new int[size];
        front = 0;
        back = -1;
        count=0;
}

    bool isEmpty()
    {
        return (max()==0);
    }

    bool isFull() {
        return (max()==size);
    }

    void enqueue(elemType entry)
    {
        cout << "enqueue " << entry;

        if(isEmpty())
        {
            front = back = 0;
            array[back] = entry;
            count++;
        }
        else
        {
            back = (back+1) % size;
            array[back] = entry;
            count++;
        }
        cout << endl;
    }

    int maxsize()
    {
        return count;
    }

    void dequeue() {
        cout << "dequeue : " << Front();
        if(isEmpty())
        {
            cout << " error : empty";
        }
        else if(back == front)
        {
            back = front = -1;
        }
        else
        {
            front = (front+1) % size;
            count--;
        }
        cout << endl;
    }

    void print()
    {
        if(isEmpty())
        {
            cout << "Queue is empty";
        }
        else
        {
            for(int i = front; i<count; i++)
            {
                cout << array[i] << " ";
            }
            cout << array[back];

        }
        //cout<<"count is:" <<count<<endl;
        cout << endl;
    }

    int Front()
    {

        if(front == -1)
        {
            cout<<"Queue is empty\n";
            return -1;
        }
        return array[front];

    }

    int Back()
    {
        if(back==-1)
        {
            cout<<"Queue is full";
        }
        return array[back];
    }

    int max()
    {
        return count;
        cout <<"count: " <<count;

    }

    void inc()
    {
        int newsize = this->size*2;

        elemType *temp = new elemType[newsize];



        for (int i=0; i<this->count;i++)
        {
            temp[i]=this->array[(front+i) % size];
        }

        delete [] this->array;
        this->array=temp;
        this->count=newsize;

//      front=array[front];  //0
        //front = 0;
        //back=count;


    }


};



#endif /* Q_H_ */

I would really appreciate help with this.

In incyou don’t update this->size

001
– 001

2019-03-22 02:21:33 +00:00
Commented Mar 22, 2019 at 2:21 — 001
– 001, Commented Mar 22, 2019 at 2:21

pexeer · Accepted Answer · 2019-03-22 02:51:21Z

three small changes:

enqueue method: inc when isFull
```
if (isFull())
{
    inc();
}
```
print method: print every element from front to back

inc method: copy every element from front to back, and reset front and back index

void inc()
{
    int newsize = this->size*2;

    elemType *temp = new elemType[newsize];

    // ******* IMPORTANT ******
    // copy count elements
    for (int i = 0; i < count; ++i) {
        int index = (front + i) % size;
        temp[i] = array[index];
    }
    front = 0;
    back = count - 1;
    delete []array;
    array=temp;
    count=newsize;
}

  template <class elemType>
  class arrayQueue
  {
    int size;
    int *array;
    int front;
    int back;
    int count;
    public:
    arrayQueue(elemType size)
    {
        this->size = size;
        array = new int[size];
        front = 0;
        back = -1;
        count=0;
    }

    bool isEmpty()
    {
        return (max()==0);
    }

    bool isFull() {
        return (max()==size);
    }

    void enqueue(elemType entry)
    {
        cout << "enqueue " << entry;

        if(isEmpty())
        {
            front = back = 0;
            array[back] = entry;
            count++;
        }
        else
        {
            if (isFull()) {
                inc();
            }
            back = (back+1) % size;
            array[back] = entry;
            count++;
        }
        cout << endl;
    }

    int maxsize()
    {
        return count;
    }

    void dequeue() {
        cout << "dequeue : " << Front();
        if(isEmpty())
        {
            cout << " error : empty";
        }
        else if(back == front)
        {
            back = front = -1;
        }
        else
        {
            front = (front+1) % size;
            count--;
        }
        cout << endl;
    }

    void print()
    {
        if(isEmpty())
        {
            cout << "Queue is empty";
        }
        else
        {
            // ******* IMPORTANT ******
            for (int i = 0; i < count; ++i) {
                int index = (front + i) % size;
                cout << array[index] << " ";
            }
        }
        //cout<<"count is:" <<count<<endl;
        cout << endl;
    }

    int Front()
    {

        if(front == -1)
        {
            cout<<"Queue is empty\n";
            return -1;
        }
        return array[front];

    }

    int Back()
    {
        if(back==-1)
        {
            cout<<"Queue is full";
        }
        return array[back];
    }

    int max()
    {
        return count;
        cout <<"count: " <<count;

    }

    void inc()
    {
        int newsize = this->size*2;

        elemType *temp = new elemType[newsize];

        // ******* IMPORTANT ******
        // copy count elements
        for (int i = 0; i < count; ++i) {
            int index = (front + i) % size;
            temp[i] = array[index];
        }

        front = 0;
        back = count - 1;
        delete []array;
        array = temp;
        count = newsize;
    }
    };

1201ProgramAlarm · Accepted Answer · 2019-03-22 02:20:53Z

0

Since you move elements to the beginning of the newly allocated array, inc needs to update front and back to refer to their respective new positions.

Also, you're updating count to be the new size instead of size.

answered Mar 22, 2019 at 2:20

1201ProgramAlarm

32.8k7 gold badges47 silver badges60 bronze badges

1 Comment

Bunty Over a year ago

Where should back refer to in this case?

Collectives™ on Stack Overflow

Queue implementation and array resizing using C++

2 Answers 2

Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related