Implementation of a Dynamically Resizing Stack in C++

This C++ code features a dynamic stack implementation, ArrayStack, supporting key operations such as push, pop, and peek. The stack's underlying array dynamically resizes, doubling when capacity is reached and halving when usage drops below 25%. The constructor initializes the stack, the destructor handles memory cleanup, and methods ensure efficient stack management. Explicit instantiation for integers is included. This versatile template-based design promotes code reuse for different data types. Overall, the code showcases a robust and memory-efficient solution for implementing a dynamic stack structure in C++.

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.