Question

Create a dynamic array-based Queue ADT class in C++ that contains enqueue(Inserts newElement at the back ) and dequeue(Removes the frontmost element ). If the size of the array is equal to the capacity a new array of twice the capacity must be made.

The interface is shown:

class Queue {
    private:
        int* elements;  
        unsigned elementCount;  // number of elements in the queue
        unsigned capacity;      // number of cells in the array
        unsigned frontindex;    // index the topmost element
        unsigned backindex;     // index where the next element will be placed

    public:
        // Description: Constructor
        Queue();


        // Description: Inserts newElement at the back (O(1))
        void enqueue(int newElement);

 
        // Description: Removes the frontmost element (O(1))
        // Precondition: Queue not empty
        void dequeue();


        // Description: Returns a copy of the frontmost element (O(1))
        // Precondition: Queue not empty
        int peek() const;


        // Description: Returns true if and only if queue empty (O(1))
        bool isEmpty() const;
};

Thanks!

Answer 1

#include<iostream>
using namespace std;
class Queue {
private:
int* elements;
unsigned elementCount; // number of elements in the queue
unsigned capacity; // number of cells in the array
unsigned frontindex; // index the topmost element
unsigned backindex; // index where the next element will be placed

public:
// Description: Constructor
Queue()
{
           elements = new int[10];
           capacity =10;
           frontindex=backindex=-1;  
       }
  

// Description: Inserts newElement at the back (O(1))
void enqueue(int newElement)
{
           if(backindex+1==capacity)   //then expanding queue by double size
           {
               int *t = new int[capacity*2];
               for(int i=frontindex;i<=backindex;i++)
               t[i]=elements[i];
               elements = t;
               enqueue(newElement);
              
           }
           else
           {
               if(frontindex==-1)
               {
                   elements[frontindex+1]=newElement;
                   frontindex++;
                   backindex++;  
               }
               else
               {
                   elements[backindex+1]=newElement;
                   backindex++;  
               }  
           }  
       }

// Description: Removes the frontmost element (O(1))
// Precondition: Queue not empty
void dequeue()
{
           if(!isEmpty())//if list is not empty
           {
               for(int i=frontindex;i<backindex;i++)
               elements[i]=elements[i+1];
               backindex--;
               if(backindex==-1)
               frontindex=-1;
                  
           }
          
              
       }

// Description: Returns a copy of the frontmost element (O(1))
// Precondition: Queue not empty
int peek() const
{
           return elements[frontindex];  
       }

// Description: Returns true if and only if queue empty (O(1))
bool isEmpty() const
{
           if(frontindex==-1)return true;
           return false;  
       }
};

int main()
{//testing
   Queue q;
   q.enqueue(1);
   q.enqueue(2);
   q.enqueue(3);
   cout<<q.peek()<<endl;
   q.dequeue();
   cout<<q.peek()<<endl;
   q.dequeue();
   cout<<q.peek()<<endl;
   q.dequeue();
   return 0;
}

output:

1
2
3

Process exited normally.
Press any key to continue . . .

//PLS give a thumbs up if you find this helpful, it helps me alot, thanks.

//if you have any doubts, ask me in the comments