deque implementation from scratch - push_back () question?

[cpplover]

I'm trying to learn about the deque container. Here is the code that I have written so far. However, looks like the push_back() and the pop_front() functions are not working as expected. CAn some one take a look and comment please?

#include<iostream>

using namespace std;

class dequeue {
    friend ostream & operator <<(ostream &os,dequeue &d);
    public: 
        dequeue(int size); //constructor
        ~dequeue(){ delete [] storage; } //destructor
        void push_front(int data);
        void push_back(int data);
        int pop_back();
        int pop_front();
        int & dequeue::operator[] (int index);
    private:
        int size;
        int curr_front,curr_back;
        int * storage;
};

dequeue:: dequeue(int size){
    curr_back=curr_front=0;
    storage = new int [size];
    
}

void dequeue:: push_front(int data){
    storage[curr_front]=data;
    curr_front++;
}

void dequeue:: push_back(int data){
    
    storage[curr_back]=data;
    curr_back--;
}

int dequeue:: pop_front(){
    curr_front++;
    return storage[curr_front];
}

int dequeue:: pop_back(){
    
    return storage[curr_back];--curr_back;
}
 int & dequeue::operator[] (int index)
{
	if(index < 0 || index >size)
	cout<<"Error \n";
	else
    return storage[index];
 
}

ostream & operator <<(ostream &os,dequeue &d)
{
	int i;
	os << "[ ";
	for(i=0; i<d.size; i++)
		os << d[i] << " ";
	os << "]" << endl;
	return os;

}

int main(){
    cout<<"This is a Dequeue implementation \n";
    dequeue q(10);
    
    q.push_front(2);
    
    q.push_front(1);
    q.push_front(5);
    q.push_back(7);
    cout<<"Elements of the dequeue entered so far are \n";
    for(int i=0;i<4;i++)
        cout<<q[i]<<" ";

    cout<<q.pop_front()<<endl;
    cout<<q.pop_back();
    
    return 0;
}
        
        
    

[coder777]

both pop_front() and pop_back() are wrong. You need to get the value first (to a temporary variable) and then increment/decrement. Plus you cannot do anything after return on line 45

EDIT: I suggest looking at this: http://www.cplusplus.com/reference/stl/deque/

hm, yeah the push functions are also wrong. To accomplish it start in the middle:

dequeue:: dequeue(int size){
    curr_back=curr_front=size/2;
  curr_back++;
    storage = new int [size];
    
}

push_back:

storage[curr_back]=data;
    curr_back++;

push_front:

storage[curr_front]=data;
    curr_front--;

Take care that the indexes don't go out ouf bounds

[Gaminic]

I only glanced over your code, but I wonder about lines 29 and 35. If something is added to the front of the deque, shouldn't "front" be decremented, as the new first is one ahead of the old first? Similarly, if you add one to the end, the new last is one after the old last, thus it's location is incremented, no?

[cpplover]

coder 777,
Thank You.
Well, I'm pretty sure all my push and pop functions are a mess. I think I'm confused here.

Also, I understand your functions but not able to understand why to start from the middle?

[cpplover]

Gaminic,
Thanks.
I've corrected that now.

[cpplover]

coder777,
is this correct for the pop functions??

  
int dequeue:: pop_front(){
    int x = storage[curr_front];
    curr_front++;
    return x;
}

int dequeue:: pop_back(){
     int y= storage[curr_back];
     curr_back--;
     return y;
}

[coder777]

Also, I understand your functions but not able to understand why to start from the middle?

Well, if you start both with 0 you cannot push anything to the front.

Another (maybe better) approach would be starting from the ends going to the middle:

dequeue:: dequeue(int size){
    curr_back=size;
    curr_front=0;
    storage = new int [size];
    
}

Then you have to change just push_back:

void dequeue:: push_back(int data){
    
    curr_back--;
    storage[curr_back]=data;
}

Anyway you need to check in your push function if it's still possible to push

[Gaminic]

Personally, I prefer having my "deque front" at the "array end", as if array[0] was the middle of the array.

If I know "front" is -10 (i.e. there are 10 items 'before the middle'), then I can find the first by doing "size+front", regardless of size. You can check for overflow if "end-front = size". Resizing requires you to copy the last "front" items of your array to the last "front" items of the new one. (Start from size-1 and go backward)

I have no idea if that's the best way to do it, but it seems a lot easier to me than the "start from the middle" trick, which still has troubles when you add more to one side than to the other, and is more difficult to resize.

[cpplover]

Thanks guys.

#include<iostream>

using namespace std;

class dequeue {
    friend ostream & operator <<(ostream &os,dequeue &d);
    public: 
        dequeue(int size); //constructor
        ~dequeue(){ delete [] storage; } //destructor
        void push_front(int data);
        void push_back(int data);
        int pop_back();
        int pop_front();
        int & dequeue::operator[] (int index);
    private:
        int size;
        int curr_front,curr_back;
        int * storage;
};

dequeue:: dequeue(int size){
    curr_back=curr_front=0;
 // curr_back=curr_front=size/2; // some issue here...i don't get it!
 //curr_back++;
    storage = new int [size];
    
}
 
void dequeue:: push_front(int data){
    storage[curr_front]=data;
    curr_front++;
}

void dequeue:: push_back(int data){
    storage[curr_back]=data;
    curr_back--;
}

int dequeue:: pop_front(){
   
   int x = storage[curr_front];
    
   storage[curr_front]=x;
}

int dequeue:: pop_back(){
    
   int y= storage[curr_back];
    storage[curr_back]=y;
}
 int & dequeue::operator[] (int index)
{
	if(index < 0 || index >size)
	cout<<"Error \n";
	else
    return storage[index];
 
}

ostream & operator <<(ostream &os,dequeue &d)
{
	int i;
	os << "[ ";
	for(i=0; i<d.size; i++)
		os << d[i] << " ";
	os << "]" << endl;
	return os;

}

int main(){
    cout<<"This is a Dequeue implementation \n";
    dequeue q_obj(4);
    q_obj.push_front(1);
    q_obj.push_front(2);
    q_obj.push_front(3);
    q_obj.push_back(7);
    cout<<"Elements of the dequeue entered so far are \n";
    for(int i=0;i<4;i++)
        cout<<"[" <<q_obj[i]<<"] ";
    cin.get();
    cout<<"\nPopping from the front of the deque.... "<<q_obj.pop_front()<<endl;
    cin.get();
    cout<<"\nPopping from the back of the deque.... "<<q_obj.pop_back();
  cin.get();
    return 0;
}

[cpplover]

I'm having issues with the initialization of the array for the deque.....can anyone help me please?

[Gaminic]

Can you show us the errors? There doesn't seem to be anything wrong with the line you marked.