Question

QUESTION: ADT stack: resizable array-based implementation
   for Ch4 programming problem 4
"maintain the stacks's top entry at the end of the array" at array index N-1 where the array is currently allocated to hold up to N entries. MAKE SURE YOU IMPLEMENT the functions:  bool isEmpty() const; bool push(const ItemType& newEntry); bool pop(); in ArrayStackP4.cpp

//FILE StackInterface.h

#ifndef STACK_INTERFACE_
#define STACK_INTERFACE_

template<class ItemType>
class StackInterface
{
public:
   /** Sees whether this stack is empty.
   @return True if the stack is empty, or false if not. */
   virtual bool isEmpty() const = 0;

   /** Adds a new entry to the top of this stack.
   @post If the operation was successful, newEntry is at the top of the stack.
   @param newEntry The object to be added as a new entry.
   @return True if the addition is successful or false if not. */
   virtual bool push(const ItemType& newEntry) = 0;

   /** Removes the top of this stack.
   @post If the operation was successful, the top of the stack
   has been removed.
   @return True if the removal is successful or false if not. */
   virtual bool pop() = 0;

   /** Returns the top of this stack.
   @pre The stack is not empty.
   @post The top of the stack has been returned, and
   the stack is unchanged.
   @return The top of the stack. */
   virtual ItemType peek() const = 0;

   /** Destroys object and frees memory allocated by object. */
   virtual ~StackInterface() { }
}; // end StackInterface
#endif

//ArrayStackP4.h

#ifndef ARRAY_STACK_P4_
#define ARRAY_STACK_P4_
#include <cassert>
#include "StackInterface.h"

template<class ItemType>
class ArrayStackP4 : public StackInterface<ItemType>
{
private:
   static const int INIT_SIZE = 5; // initial size of the array

   int arraySize;   // current size of the array
           // "Anytime the stack becomes full, double the size of the array"

   int top;   // Index to top of stack

   int numEntries;   // number of entries in the stack
           // this number was deducible from top in ArrayStackP1 and ArrayStackP2

   ItemType* items; // resizable array of stack entries

public:
   ArrayStackP4() : arraySize(INIT_SIZE), top(INIT_SIZE - 1), numEntries(0) // Default constructor
   {
       items = new ItemType[arraySize];
   }
   ArrayStackP4(const ArrayStackP4<ItemType>& rhs) : arraySize(rhs.arraySize), top(rhs.top), numEntries(rhs.numEntries) // copy constructor
   {
       items = new ItemType[arraySize];
       for (int i = arraySize - numEntries; i < arraySize; ++i)
           items[i] = rhs.items[i];
   }
   ~ArrayStackP4()   // destructor
   {
       delete[] items;
   }
   bool isEmpty() const;
   bool push(const ItemType& newEntry);
   bool pop();
   ItemType peek() const {
       assert((!isEmpty()) && (top == arraySize - 1));
       return items[top];
   };
   int getNumEntries() const // returns the number of entries in the stack
   {
       return numEntries;
   }
   int getCapacity() const   // returns the size of the resizable array
   {
       return arraySize;
   }
};
#endif

Answer 1

//ArrayStackP4.h

#ifndef ARRAY_STACK_P4_

#define ARRAY_STACK_P4_

#include <cassert>

#include "StackInterface.h"

template<class ItemType>

class ArrayStackP4 : public StackInterface<ItemType>

{

private:

static const int INIT_SIZE = 5; // initial size of the array

int arraySize; // current size of the array

// "Anytime the stack becomes full, double the size of the array"

int top; // Index to top of stack

int numEntries; // number of entries in the stack

// this number was deducible from top in ArrayStackP1 and ArrayStackP2

ItemType* items; // resizable array of stack entries

public:

ArrayStackP4() : arraySize(INIT_SIZE), top(INIT_SIZE - 1), numEntries(0) // Default constructor

{

items = new ItemType[arraySize];

}

ArrayStackP4(const ArrayStackP4<ItemType>& rhs) : arraySize(rhs.arraySize), top(rhs.top), numEntries(rhs.numEntries) // copy constructor

{

items = new ItemType[arraySize];

for (int i = arraySize - numEntries; i < arraySize; ++i)

items[i] = rhs.items[i];

}

~ArrayStackP4() // destructor

{

delete[] items;

}

bool isEmpty() const;

bool push(const ItemType& newEntry);

bool pop();

bool isEmpty() const {

return numEntries == 0;

}

bool push(const ItemType& newEntry) {

if (numEntries == arraySize) {

ItemType* newItems = new ItemType[arraySize * 2];

int i;

for(i = 0; i < numEntries; i++) {

newItems[arraySize * 2 - 2 - i] = items[arraySize - 1 - i];

}

items = newItems;

arraySize *= 2;

top = arraySize - 1;

items[top] = newEntry;

numEntries++;

return true;

}

int i;

for (i = numEntries - 1; i >= 0; i--) {

items[arraySize - 2 - i] = items[arraySize - 1 - i];

}

items[top] = newEntry;

numEntries++;

return true;

}

bool pop() {

if(isEmpty())

return false;

int i;

numEntries--;

for (i = 0; i < numEntries; i++) {

items[arraySize - 1 - i] = items[arraySize - 2 - i];

}

return true;

}

ItemType peek() const {

assert((!isEmpty()) && (top == arraySize - 1));

return items[top];

};

int getNumEntries() const // returns the number of entries in the stack

{

return numEntries;

}

int getCapacity() const // returns the size of the resizable array

{

return arraySize;

}

};

#endif