Question

IMPLEMENT IN C++

2. Although a queue is "best" implemented with a list, it can be implemented with a vector if you take into account the starting position of the queue. For example, if five elements are pushed onto the queue, the start of the queue is at position zero and the end is at position 4. If we, then, pop two elements, the start would be at position 2 and the end at position 4. The two "popped" elements are not really removed from the vector, and that avoids the O(N) time problem for the pop function.
Implement a class which uses a vector to store the queue. Be mindful of performance, such that if the queue is empty, the size of the underlying vector is "reset."

Answer 1

Here is the completed code for this problem. Comments are included, go through it, learn how things work and let me know if you have any doubts or if you need anything to change. If you are satisfied with the solution, please rate the answer. If not, PLEASE let me know before you rate, I’ll help you fix whatever issues. Thanks

#include<iostream>

#include<vector>

using namespace std;

//templated Queue class using vector

template<class T>

class Queue{

                vector<T> data;

                int startPos; //start position of front element

                int count; //current number of elements in queue

public:

                Queue(){

                                //setting 0 as startPos and count

                                startPos=0;

                                count=0;

                }

                //method to add an element to the back

                void enqueue(T element){

                                //simply appending element to the end and updating count

                                data.push_back(element);

                                count++;

                }

                //method to remove front element

                void dequeue(){

                                //checking if queue is not empty

                                if(count>0){

                                                //simply advancing startPos

                                                startPos++;

                                                //decrementing size

                                                count--;

                                                //if count is 0, resetting vector, setting startPos to 0

                                                if(count==0){

                                                                data.clear();

                                                                startPos=0;

                                                }

                                }

                }

               

                //returns the front element without removing

                T front() const{

                                //assuming queue is not empty, returning element at startPos

                                return data[startPos];

                }

               

                //returns true if queue is empty

                bool isEmpty() const{

                                return count==0;

                }

};

//main method for testing

int main(){

                //creating an integer queue, adding numbers 1 to 5

                Queue<int> q;

                for(int i=1;i<=5;i++){

                                q.enqueue(i);

                }

                //displaying and removing two front values,

                cout<<q.front()<<endl; //1

                q.dequeue();

                cout<<q.front()<<endl; //2

                q.dequeue();

                //adding 6 and 7

                q.enqueue(6);

                q.enqueue(7);

                //looping until q is empty

                while(!q.isEmpty()){

                                //displaying and removing front value

                                cout<<q.front()<<endl; //should display values 3 to 7 in each line

                                q.dequeue();

                }

                return 0;

}

/*OUTPUT*/

1

2

3

4

5

6

7