PushFront method for an array C++

Question

Hello,

I thought i'd post a little of my homework assignment. Im so lost in it. I just have to be really efficient. Without using any stls, boosts and the like. By this post, I was hoping that someone could help me figure it out.

bool stack::pushFront(const int nPushFront)
{     
     if ( count == maxSize ) // indicates a full array
     {
        return false;
     }
     else if ( count <= 0 )
     {
      count++;
      items[top+1].n = nPushFront;
      return true;
     }
     ++count;
     for ( int i = 0; i < count - 1; i++ )
     {
      intBackPtr = intFrontPtr;
      intBackPtr++;
     *intBackPtr = *intFrontPtr;
     }
     items[top+1].n = nPushFront;
     return true;    
}

I just cannot figure out for the life of me to do this correctly! I hope im doing this right, what with the pointers and all

int *intFrontPtr = &items[0].n;
int *intBackPtr  = &items[capacity-1].n;

Im trying to think of this pushFront method like shifting an array to the right by 'n' units...I can only seem to do that in an array that is full. Can someone out their please help me?

Answer 1

Firstly, I'm not sure why you have the line else if ( count <= 0 ) - the count of items in your stack should never be below 0.

Usually, you would implement a stack not by pushing to the front, but pushing and popping from the back. So rather than moving everything along, as it looks like you're doing, just store a pointer to where the last element is, and insert just after that, and pop from there. When you push, just increment that pointer, and when you pop, decrement it (you don't even have to delete it). If that pointer is at the end of your array, you're full (so you don't even have to store a count value). And if it's at the start, then it's empty.

Edit

If you're after a queue, look into Circular Queues. That's typically how you'd implement one in an array. Alternatively, rather than using an array, try a Linked List - that lets it be arbitrarily big (the only limit is your computer's memory).

Answer 2

You don't need any pointers to shift an array. Just use simple for statement:

int *a; // Your array
int count; // Elements count in array
int length; // Length of array (maxSize)

bool pushFront(const int nPushFront)
{
    if (count == length) return false;
    for (int i = count - 1; i >= 0; --i)
        Swap(a[i], a[i + 1]);
    a[0] = nPushFront; ++count;
    return true;
}

Answer 3

Without doing your homework for you let me see if I can give you some hints. Implementing a deque (double ended queue) is really quite easy if you can get your head around a few concepts.

Firstly, it is key to note that since we will be popping off the front and/or back in order to efficiently code an algorithm which uses contiguous storage we need to be able to pop front/back without shifting the entire array (what you currently do). A much better and in my mind simpler way is to track the front AND the back of the relevant data within your deque.

As a simple example of the above concept consider a static (cannot grow) deque of size 10:

class Deque
{
public:
    Deque() 
    : front(0)
    , count(0) {}

private:
    size_t front;
    size_t count;
    enum {
        MAXSIZE = 10
    };
    int data[MAXSIZE];
};

You can of course implement this and allow it to grow in size etc. But for simplicity I'm leaving all that out. Now to allow a user to add to the deque:

void Deque::push_back(int value)
{
    if(count>=MAXSIZE)
        throw std::runtime_error("Deque full!");
    data[(front+count)%MAXSIZE] = value;
    count++;
}

And to pop off the back:

int Deque::pop_back()
{
    if(count==0)
        throw std::runtime_error("Deque empty! Cannot pop!");
    int value = data[(front+(--count))%MAXSIZE];
    return value;
}

Now the key thing to observe in the above functions is how we are accessing the data within the array. By modding with MAXSIZE we ensure that we are not accessing out of bounds, and that we are hitting the right value. Also as the value of front changes (due to push_front, pop_front) the modulus operator ensures that wrap around is dealt with appropriately. I'll show you how to do push_front, you can figure out pop_front for yourself:

void Deque::push_front(int value)
{
    if(count>=MAXSIZE)
        throw std::runtime_error("Deque full!");
    // Determine where front should now be.
    if (front==0)
       front = MAXSIZE-1;
    else
       --front;
    data[front] = value;
    ++count;
}