Question

Write an implementation of the ADT stack that uses a resizeable array to represent the stack items. Anytime the stack becomes full, double the size of the array. Maintain the stack's top entry at the beginning of the array.

Use c++ to write this code.

Answer 1

template<class ItemType>

class ArrayStack

{

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

ItemType* items; // resizable array of stack entries

public:

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

{

items = new ItemType[arraySize];

}

ArrayStack(const ArrayStack<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];

}

~ArrayStack() // 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;

}

};