C++ Stack Implementation for Dynamic Memory Management

Illustrative C++ Stack Implementation

This C++ code presents a robust ArrayStack implementation, demonstrating crucial stack operations and dynamic memory management. The versatility of this template-based solution enables adaptation to diverse data types. Notably, its automatic array resizing optimizes memory use, showcasing a sophisticated approach to stack efficiency. Developers looking to understand dynamic memory allocation, array manipulation, and template usage will find this code invaluable. For students seeking support with their C++ assignment, this implementation serves as a practical learning resource, offering insights into fundamental concepts and fostering a deeper understanding of stack structures.

Block 1: Constructor


template

ArrayStack
::ArrayStack() : top(-1), capacity(DEFAULT_CAPACITY) {
items = new ItemType[DEFAULT_CAPACITY];
}

The constructor initializes the stack with an empty state (top set to -1) and a default capacity.
Dynamic memory allocation is performed to create an array (items) with the specified default capacity.

Block 2: Destructor


template

ArrayStack
::~ArrayStack() {
delete[] items;
}

The destructor deallocates the dynamically allocated memory for the array (items) when the object is destroyed.

Block 3: isEmpty


template

bool ArrayStack
::isEmpty() const {
return top == -1;
}

Checks if the stack is empty by examining whether the top index is -1.

Block 4: push


template

bool ArrayStack
::push(const ItemType& newEntry) {
if (top == capacity - 1) {
resize(capacity * 2);
}
items[++top] = newEntry;
return true;
}

Pushes a new element onto the stack.
If the stack is full (reached capacity), it dynamically resizes the array by doubling its capacity.
The new element is then added at the updated top index.

Block 5: Pop


template

bool ArrayStack
::pop() {
if (isEmpty()) return false;
top--;
if (top < capacity / 4 && capacity > DEFAULT_CAPACITY) {
resize(capacity / 2);
}
return true;
}

Removes the top element from the stack.
Checks for emptiness and returns false if the stack is already empty.
After removing an element, it checks if the stack size has fallen below 25% of its capacity. If true, it dynamically resizes the array by halving its capacity.

Block 6: peek


template

ItemType ArrayStack
::peek() const {
return items[top];
}

Returns the element at the top of the stack without modifying the stack.

Block 7: resize


template

void ArrayStack
::resize(int newCapacity) {
ItemType* newItems = new ItemType[newCapacity];
std::copy(items, items + (top + 1), newItems);
delete[] items;
items = newItems;
capacity = newCapacity;
}

Block 8: Explicit Instantiation


template class ArrayStack
;

Explicitly instantiates the template class for int data type. This is necessary to ensure that the template code is compiled for the specified type.

Conclusion

In summary, the provided C++ code implements a dynamic array-based stack through the ArrayStack template class. It facilitates standard stack operations, including push, pop, and peek, while dynamically resizing the underlying array to optimize memory usage. The constructor initializes the stack, and the destructor ensures proper memory deallocation. The code demonstrates an essential use of templates for generic programming, allowing the stack to accommodate elements of any data type. With its thoughtful handling of resizing to balance efficiency and memory conservation, the ArrayStack template offers a versatile and efficient implementation of a stack data structure in the C++ programming language.

Implementation of a Dynamically Resizing Stack in C++