CodeStepByStep

Define a class called PancakeStack using inheritance as described below. Suppose that an existing class named ArrayStack has already been written. An ArrayStack is an implementation of a stack of integers using an array as its internal representation. It has the following implementation:

class ArrayStack {
public:
    ArrayStack();                   // construct empty stack
    ~ArrayStack();                  // free memory

    virtual bool isEmpty() const;   // true if stack has no elements
    virtual int peek() const;       // return top element (error if empty)
    virtual int pop();              // remove/return top element (error if empty)
    virtual void push(int n);       // add to top of stack, resizing if needed

private:
    int* elements;                  // array of stack data (index 0 = bottom)
    int size;                       // number of elements in stack
    int capacity;                   // length of array
};
ostream& operator <<(const ArrayStack& stack);  // prints a stack

Define a new class called PancakeStack that extends ArrayStack through inheritance. A "pancake stack" is a silly variation of a stack where just after an element is pushed onto or popped from the stack, some portion of the stack is "flipped" into reverse order. (This is not a very good or realistic use of inheritance; it is meant to test your knowledge of the mechanics and not meant as a practical example.)

We will define our pancake stack to accept an integer argument K to its constructor, and then for that stack's lifetime, every time there is a push or pop, the top K elements (or the entire stack, if it does not contain at least K elements) are "flipped" into the reverse order.

Your class should provide the same member functions as the superclass, along with the constructor that accepts an int parameter for K. If a negative value for K is passed to the constructor, throw an int exception. Your code must work with the existing ArrayStack as shown, unmodified.

For example, the following code demonstrates the use of a PancakeStack with a K value of 3. This means that after each push or pop, the top 3 elements of the stack should be flipped. The output at right illustrates this flipping. For example, when the value 5 is pushed onto the top, without any flipping the stack would be {3, 4, 2, 1, 5}. But the top 3 elements are flipped to yield {3, 4, 5, 1, 2}. The flips are shown underlined in the output below for clarity.

PancakeStack stack(3);
cout << stack << endl;

// push seven elements
for (int i = 1; i <= 7; i++) {
    stack.push(i);
    cout << stack << endl;
}

// pop all elements
while (!stack.isEmpty()) {
    int top = stack.pop();
    cout << stack << "  " << top << endl;
}
cout << stack << endl;

{}
{1}
{2, 1}
{3, 1, 2}
{3, 4, 2, 1}
{3, 4, 5, 1, 2}
{3, 4, 5, 6, 2, 1}
{3, 4, 5, 6, 7, 1, 2}
{3, 4, 5, 1, 7, 6}  2
{3, 4, 7, 1, 5}  6
{3, 1, 7, 4}  5
{7, 1, 3}  4
{1, 7}  3
{1}  7
{}  1
{}

You must appropriately utilize the behavior inherited from the superclass. This means, use proper syntax, and do not re-implement or break behavior that already works properly in the superclass, and do not illegally try to access unauthorized superclass members. Recall that subclasses are not able to access private members of the superclass.

You may create ArrayStack or Queue<int> objects as local variables in your code if it is helpful to do so, but otherwise you should not create any other auxiliary data structures (arrays, vectors, maps, sets, Stack<int>, strings, etc.).