Data Structures – Stack

Hi All! πŸ™‚

Today we are continuing on with our discussion of some of the basic data structures used in computer science and software development. Previous posts in this series can be accessed below:

In this post we will be looking through my implementation of a Stack.

A Stack is a Last In, First Out (LIFO) data structure which uses 2 main operations, push and pop, to add elements and remove elements respectively. It’s easy to think about a Stack as a physical stack of plates.

plates-stackWhen we have a stack of plates we can’t just grab a plate from the middle, that would cause all kinds of problems.

broken-plateTo get to plates in the middle we must first remove the plates on top. Effectively we can only ever access the plate on top which is the last plate we added. The same is true of Stacks in computer science.

For a more detailed explanation of Stacks we can always turn to trusty Wikipedia. But how do we implement this in code? Well let’s see.

Stack Class

Source Code

Here are the complete source code files for our test implementation of a Stack:

You can also access the source on GitHub: https://github.com/gabeb1920/Stack.git

Note that I have created this as a template class so it is capable of holding any data type. You can even use your own classes however note that they will need an overloaded assignment operator(=) and output operator(<<) to use this data structure.

Now let’s get to it!

Stack.h

Our Stack implementation ends up being similar to the DynamicArray class we created previously. The data elements of the Stack are:

  • int capacity
    • This is used to keep track of the Stack. ie. the number of elements the Stack can hold before it needs expanding.
  • int size
    • This is used to keep track of the number of elements in the Stack. We also use it to point to the help us find the top element in the Stack.
  • T * data
    • This is a pointer which we use to hold an array which will represent theΒ Β  data in the Stack.

Similarly to the DynamicArray class we also have a private function void grow() which we use to expand the Stack dynamically.

We also have a number of public functions:

Constructors:

  • Stack()
    • A basic default constructor used to initialise the Stack.
  • Stack(int newCapacity)
    • This constructor is used to create an empty Stack with a predetermined capacity.
  • Stack(const Stack & newStack)
    • This is our copy constructor used to create a new Stack initialised with the same data as the newStack parameter.

Destructor:

  • ~Stack()
    • This is required because we are dealing with dynamic memory. If we don’t correctly destroy the Stack it will cause a memory leak in our application.

The essential Stack functions:

  • bool pop()
    • This function is used to remove the top element from the Stack.
  • void push(const T newData)
    • This function is used to add data to the top of the Stack.

Get & Set Functions:

  • T peek()
    • Used to get the top element without removing it from the Stack.
  • int getSize()
    • Returns the number of elements currently in the Stack.
  • int getCapacity()
    • Returns the current capacity of the Stack. As mentioned this is the number of elements which the Stack can hold before it will need to grow.
  • bool setCapacity(const int newCapacity)
    • Allows the developer to set the capacity of the Stack directly. Note that if the new capacity is smaller than the current capacity then the difference is deleted from the top of the Stack.

Other Functions:

  • ostream& operator<<(ostream& out, Stack<U>& rhs)
    • Simply used to run through the Stack, print out each element and remove the elements as it goes. Note that I’m not sure about this function as I’ll explain further below.
  • bool isEmpty()
    • Simply used to determine if there are any elements remaining in the Stack.

Most of these functions are self-explanatory but there are a few I’d like to examine in a bit more detail.

grow

Click the title to see the source code for my grow function.

The grow function is used to expand the Stack when it becomes full. I’ve used the convention of doubling the capacity with each growth. Growths are expensive operations because we are storing the Stack in an array. In order to grow the Stack we must

  1. Create a new array
  2. Copy over all the elements currently in the Stack
  3. Delete the current Stack pointer
  4. Point the Stack pointer to the new array

As you can see there are a few steps here and particularly the copy operation (2) would be very expensive for large data sets. As such we want to reduce the number of growths we need to undertake. By doubling the capacity with each growth we limit the number of growths required for large data sets. It is common to use this method of growing by doubling the capacity of the structure and it is used throughout other implementations.

pop

Some implementations of pop will return the element before removing it from the Stack. I decided not to do this and instead use the peek function to return the top element. Basically all this function does is reduce the size variable which will limit the position in our array where the other functions will look to.

Note that this implementation doesn’t destroy the element so the data is still in memory until being written over.

push

The push function is quite simple. We check if the Stack is full and grow if needed. Then we simply add the newData to the array and increment size variable to point to the new top element.

setCapacity

Click the title to see the source code for my setCapacity function.

The setCapacity function is fairly simple but it becomes interesting when the new capacity is smaller than the current one.

The function works in a similar fashion to the grow function:

  1. Create a new array
  2. Copy over all the elements currently in the Stack
  3. Delete the current Stack pointer
  4. Point the Stack pointer to the new array

Only this time the new capacity won’t be double the current but rather specified by the developer. Now this is fine for increasing the capacity and can allow developers who know the approximate size of the data set they’ll be working with to drastically reduce the number of growths they’ll need. But what about if the new capacity is smaller than the current?

In this case what I decided to do was to remove the difference from the top of the Stack. I’m actually curious to know how others have implemented this as I’m not sure my version is the best. In any case there is going to be some data lost but whether it’s from the top or the bottom of the Stack I’m not sure. I’ve gone with the top for this implementation but I’m sure you can adapt it to suit your needs.

operator<<

If you’ve read my other posts about data structures you would see that I often create an overloaded output operator (<<) for my classes. The problem here came when I considered if I should remove the elements from the stack as I went or not. Traditionally when you return the top element of the Stack you also remove it thus exposing the next but I can imagine there’d be times when you might want to see the contents of the Stack without destroying it. I guess you could create a copy of it to output but maybe I can modify the function in some way to allow the developer to choose? I’m not sure.

To be honest I’m not comfortable with this implementation as I don’t think an output function should alter the class. In fact I think the traditional implementation of the overloaded (<<) operator has the rhs variable being const. I may end up changing this in a future update. Let me know your thoughts.

Summary

So there you have it, a sample implementation of a Stack in C++. Granted this is not perfect but hopefully it serves to illustrate how a Stack is created in code. I hope you find it useful.

Feel free to leave comments or suggestions to improve the implementation or how you might use it.

Until next time! πŸ™‚

Leave a Reply

Your email address will not be published. Required fields are marked *