Deque push_front() and push_back() without including <deque>

Question

I need to create a deque by myself to understand how it works with practice and also I don't need to use the library, I'd like to write my own functions

I created a class Deque, which has methods push_back(), push_front(), pop_back(), pop_front();

At first I wrote such a code for push_front():

void Deque :: push_front( int data, int number ) {

 deque[head - 1] = data;
 head++;
}

here is the constructor:

  Deque :: Deque( int number ) : head (1), tail (1), 
                                 go_straight (0), go_back (1), 
                                 deque (new int [number]) {
                                    for( int i = 0; i < number; ++i) {
                                       deque[i] = 0;
                                    }
                                 };

but this push_front works in such a way: if I input 4(number of elements) and then 40(value)

   40 0 0 0

if I input 50(value) it will turn into:

  40 50 0 0

But I need to do it like this

  50 40 0 0

In other words I need to move the elements on +1, how can I do that?

Thank you in advance!!!

Answer 1

Assuming your sequence is stored in some array ar[N], and some ar[len] where len < Nis the current "back" of your queue, simply "shift" the elements:

#include <iostream>

template<typename T, size_t N>
bool push_front(const T& val, T(&ar)[N], size_t& len)
{
    if (len >= N)
        return false;

    size_t i = len;
    while (i--)
        ar[i+1] = ar[i];
    ar[0] = val;
    ++len;
    return true;
}

template<typename T, size_t N>
void print_array(const T(&ar)[N])
{
    for (auto& x : ar)
        std::cout << x << ' ';
    std::cout << '\n';
}

int main()
{
    int ar[10] = {0};
    size_t len = 0;
    print_array(ar);

    for (int i=10; push_front(i, ar, len); i+=10);
    print_array(ar);

    return 0;
}

Output

0 0 0 0 0 0 0 0 0 0 
100 90 80 70 60 50 40 30 20 10 

Note: this has O(N) complexity for every insertion (which means O(N^2) for inserting N items). Using a circular buffer and very careful modulo arithmetic you can make it O(1), but it isn't trivial, so I warn you ahead of time.

---

Regarding how this may work in your code, including fleshing out a copy/swap idiom for compliance with the Rule of Three. The two pushes have been implemented. I leave the two pops, the top(), and back() implementation to you.

#include <algorithm>

class Deque
{

private:
    unsigned int size;
    unsigned int length;
    int *elems;

    void swap(Deque& other)
    {
        std::swap(size, other.size);
        std::swap(length, other.length);
        std::swap(elems, other.elems);
    }

public:
    Deque(unsigned int size)
        : size(size)
        , length(0)
        , elems(new int[size]())
    {
    }

    Deque(const Deque& arg)
        : size(arg.size)
        , length(arg.length)
        , elems(new int[arg.size])
    {
        std::copy(arg.elems, arg.elems + arg.length, elems);
    }

    ~Deque()
    {
        delete [] elems;
    }

    Deque& operator =(Deque obj)
    {
        swap(obj);
        return *this;
    }

    // push to the front of the deque
    bool push_front(int value)
    {
        if (length == size)
            return false;

        unsigned int i=length;
        while (i--)
            elems[i+1] = elems[i];
        elems[0] = value;
        ++length;
        return true;
    }

    // push to the back of the deque
    bool push_back(int value)
    {
        if (length == size)
            return false;

        elems[length++] = value;
        return true;
    }
};