Implementing a Stack Using a Dynamic Array in C++
May 20, 2021
DS&A Adventures
The stack is a ubiquitous data structure that makes an appearance in all manner of applications. The operating system is responsible for maintaining a stack in memory to track variables across different scopes. When a program fails, a debugger or crash report will emit a stack trace to help you find the bug. And indeed, the very process of interpreting a program and evaluating expressions involves the use of stacks.
This short post walks through the process of implementing a stack from scratch using C++.
Defining the API
At the outset, it is useful to map out the functionality that the stack should provide in broad strokes. The defining feature of a stack is that it operates on a last-in, first-out (LIFO) policy. This means that elements are added to and removed from the top of the stack. It also means that iteration should proceed from the top of the stack to the bottom.
With that in mind, our API should have the following minimal features:
is_empty- Returns true if the stack is empty.size- Returns the number of elements on the stack.push- Push an element on top of the stack.pop- Pop an element from the top of the stack.beginandend- For iteration.
Storage and Manipulation
There are several ways to slice this particular apple. In this post, we will implement a templated class which uses a dynamic array as the backing storage and an index to track the size of the stack.
Templated Class
We could implement one stack for strings and another stack for integers. But this quickly becomes unwieldy as the number of types in your program increases, and maintenance would be a nightmare. Instead, many modern languages allow you to define generics, classes that can operate on arbitrary types. In C++, generics are called template classes.
To begin, we define our Stack class as a template.
template<typename T>
class Stack
{
...
};The template<typename T> declaration at the top makes this a template class, and T is a type parameter that must be specified when this class is instantiated. When the class is instantiated, the provided typename is substituted for T throughout the class. Using a template allows us to achieve uniform behavior for a Stack<std::string>, a Stack<int>, and any other variant.
Dynamic Array Storage
The stack needs to store its elements somewhere, somehow.
One way to do this is by creating a fixed size array. However, a fixed size (or static) array needs to be large enough to accommodate any possible scenario that may arise in its application. Consider the situation where an application needs to stack one million items once a year, but only five items the rest of the year. To accommodate this, the stack would always need to hold space for one million items, just in case, which is a major waste of memory.
Instead, our implementation will use a dynamically sized array as storage. This storage will grow and shrink as necessary to accomodate the number of items on the stack.
Because C++ does not support static variable length arrays, we will need to dynamically allocate the array at runtime. Add storage_ and capacity_ members to Stack and set the capacity to one in the constructor. The storage_ member is a pointer to the item type, which can be indexed like an array. The capacity member is an integer that indicates the max items that the array will support.
T* storage_;
int capacity_;
...
Stack()
{
capacity_ = 1;
storage_ = new T[capacity_];
}We also need to make sure dynamically allocated memory is cleaned up when the stack goes out of scope, so we delete the storage in the stack destructor.
~Stack()
{
delete[] storage_;
}Resizing
By default, the storage_ array can only hold a single item. We want to be able to increase or decrease storage depending on the number of items on the stack. To do so, we create a private resize function that updates the capacity.
void resize(int capacity)
{
T* temp = new T[capacity];
for (int i = 0; i < n_; ++i)
{
temp[i] = storage_[i];
}
delete[] storage_;
storage_ = temp;
capacity_ = capacity;
}In the function above, we first create a temp array to represent the newly sized storage, then copy existing data to the new array. We then delete the old storage to release its memory and set storage_ to temp. Finally, we update our capacity_ member to reflect the new maximum.
We will put this function to use in our push and pop methods to size the array appropriately.
Push and Pop
Adding an item to the top of the stack, or pushing it, requires us to track the current top of the stack. To track this, create an int member n_, which indicates the current top of the stack.
int n_;
...
Stack()
{
...
n_ = 0;
}Our push method can then be implemented as follows.
void push(T item)
{
if (n_ == capacity_)
{
resize(capacity_ * 2);
}
storage_[n_++] = item;
}If the stack size is equal to the storage capacity, double the capacity. Then add the new item and increment the item count.
The pop method can be implemented in similar fashion.
T pop()
{
T item = storage_[--n_];
if (n_ > 0 && n_ == capacity_ / 4)
{
resize(capacity_ / 2);
}
return item;
}Get the item on the top of the stack and decrement the item count. If the new item count is greater than zero and equal to one-quarter of the storage capacity, halve the capacity. This ensures that storage is never less than one-quarter full. Finally, return the popped item.
Query Size Information
Size information is easy to gather using the members we have already declared. The size method simply returns the item count stored in n_. The is_empty method returns true if size is zero.
int size() { return n_; }
bool is_empty() { return size() == 0; }Iteration Support
One frequent operation on collections is to iterate over each item in the collection. Without getting into the details, any class in C++ can be made into an iterable by adding the begin and end methods to it, both of which should return something that acts like an iterator.
Iterator begin()
{
return Iterator(this);
}
Iterator end()
{
return Iterator();
}The private Iterator class should be defined within Stack as follows.
class Iterator
{
Stack* stack_;
int n_;
public:
Iterator()
: stack_(nullptr)
, n_(-1)
{
}
Iterator(Stack* stack)
: stack_(stack)
, n_(stack->capacity_ - 1)
{
}
void operator++()
{
--n_;
}
bool operator!=(const Iterator& Other)
{
return n_ != Other.n_;
}
T& operator*()
{
return stack_->storage_[n_];
}
};Implementing an iterator can be a hairy task and it is beyond the scope of this post (but maybe worth exploring in another one). For now, just drop this one into our class.
With this, our Stack can be iterated from top to bottom.
Final Result
This is what the complete Stack class looks like.
template<typename T>
class Stack
{
T* storage_;
int capacity_;
int n_;
friend class Iterator;
private:
void resize(int capacity)
{
T* temp = new T[capacity];
for (int i = 0; i < n_; ++i)
{
temp[i] = storage_[i];
}
delete[] storage_;
storage_ = temp;
capacity_ = capacity;
}
class Iterator
{
Stack* stack_;
int n_;
public:
Iterator()
: stack_(nullptr)
, n_(-1)
{
}
Iterator(Stack* stack)
: stack_(stack)
, n_(stack->capacity_ - 1)
{
}
void operator++()
{
--n_;
}
bool operator!=(const Iterator& Other)
{
return n_ != Other.n_;
}
T& operator*()
{
return stack_->storage_[n_];
}
};
public:
Stack()
{
capacity_ = 1;
storage_ = new T[1];
n_ = 0;
}
~Stack()
{
delete[] storage_;
}
void push(T item)
{
if (n_ == capacity_)
{
resize(capacity_ * 2);
}
storage_[n_++] = item;
}
T pop()
{
T item = storage_[--n_];
if (n_ > 0 && n_ == capacity_ / 4)
{
resize(capacity_ / 2);
}
return item;
}
bool is_empty() const
{
return n_ == 0;
}
int size() const
{
return n_;
}
Iterator begin()
{
return Iterator(this);
}
Iterator end()
{
return Iterator();
}
};Testing the Implementation
To test this implementation of the stack, try running the following client code.
#include <string>
#include "stack.h"
int main()
{
Stack<std::string> notes;
notes.push("Hey");
notes.push("what's");
notes.push("up.");
for (const std::string& note : notes)
{
std::cout << note << std::endl;
}
return 0;
}The program should print the items in the stack from most recent to least recent.
up.
what's
Hey
