Queue + Stack C++

Question

Hello,

How do u push Items to the front of the array, ( like a stack ) without starting at MAXSIZE-1? I've been trying to use the modulus operator to do so..

bool quack::pushFront(const int nPushFront) 
{     
    if ( count == maxSize ) // indicates a full array
    {
         return false;
     }
    else if ( count == 0 ) 
    {
     ++count;
     items[0].n = nPushFront;
     return true;
    }
     intBack = intFront;
     items[++intBack] = items[intFront];
     ++count;
     items[(top+(count)+maxSize)%maxSize].n = nPushFront;
 /*
    for ( int shift = count - 1; shift >= 0; --shift )
    {
      items[shift] = i€tems[shift-1];
    } 
     items[top+1].n = nPushFront; */
     return true;    
  }

"quack" meaning a cross between a queue and a stack. I cannot simply shift my elements by 1 because it is terribly inefficient. I've been working on this for over a month now. I just need some guidence to push_front by using the modulus operator...I dont think a loop is even necessary.

Its funny because I will need to print the list randomly. So if I start adding values to the MAXSIZE-1 element of my integer array, and then need to print the array, I will have garbage values..

not actual code:

pushFront(2);
pushFront(4);
cout << q;

if we started adding from the back i would get several null values. I cannot just simply shift the array elements down or up by one.

I cant use any stls, or boosts.

Answer 1

Not sure what your problem is. Are you trying to implement a queue (which also can work as a stack, no need for your quack) as a ring buffer?

In that case, you need to save both a front and a back index. The mechanics are described in the article linked above. Pay attention to the “Difficulties” section: in particular, you need to either have an extra variable or pay attention to leave one field empty – otherwise you won’t know how to differentiate between a completely empty and a completely full queue.

Answer 2

Well, it seems kind of silly to rule out the stl, since std::deque is exactly what you want. Amortized constant time random access. Amortized constant insert/removal time from both the front and the back.

This can be achieved with an array with extra space at the beginning and end. When you run out of space at either end, allocate a new array with twice the space and copy everything over, again with space at both the end and the beginning. You need to keep track of the beginning index and the end index in your class.

Answer 3

It seems to me that you have some conflicting requirements:

1. You have to push to the head of a C++ array primitive.
2. Without shifting all of the existing elements.
3. Maintain insertion order.

Short answer: You can't do it, as the above requirements are mutually exclusive.

One of these requirements has to be relaxed.

To help you without having to guess, we need more information about what you are trying to do.