Stack Class Example

Simple Stack Abstract Type Implementation

Encapsulation is a useful feature of object-oriented languages, even without considering inheritance or polymorphism. This is an illustration of some of the C++ syntax features related to encapsulation, using a simple Stack class. It also includes a template version.

Table of Contents

PREREQUISITES — You should already…

have some C programming experience;
know how to create and compile C++ programs.

Background

A stack is a last-in, first-out (LIFO) data structure. The primary operations defined on this concept are ‘push’ and ‘pop’. This implies that there is a location called the ‘top’, which changes as values are pushed or popped. Practical implementations must also deal with popping from an empty stack (underflow), or pushing onto an already full stack (overflow).

For simplicity, our Stack class will use only inline functions, so that the whole class can be presented in one file. The stack will only handle values of type double, but this is abstracted with DataType using a typedef statement. We also use a namespace for extra realism.

This class is for demonstration purposes: to introduce features and syntax. The C++ standard library provides a std::stack<T> type, which you should use in real life applications.

Stack Class

The design of the Stack class is simplistic, but it does contain a fair number of C++ (and C++11) features. It throws exceptions on stack underflow or underflow. Memory for the stack is dynamically allocated, and because of that feature, a proper copy constructor, and overloaded assignment operator had to be written.

For completeness, the example includes a move constructor, and a move assignment operator, both of which involve rvalue references as parameters.

`Stack.hpp` — Stack Specification

/*!@file  Stack.hpp
*  @brief Stack Specification & Implementation
*/
#if !defined _STACK_HPP_
    #define  _STACK_HPP_

#include <stdexcept>
#include <algorithm>
#include <utility>

namespace ADT { // abstract data type namespace //

using DataType = double;

class Stack {

   public: // constant(s)

      static constexpr size_t DEFAULT_SIZE = 10U;  // C++11

   private: // fields | instance variables | data members

      size_t top_;
      size_t size_{DEFAULT_SIZE};  // C++11
      DataType* stack_;

      void swap (Stack& rhs) {
         std::swap(top_, rhs.top_);
         std::swap(size_, rhs.size_);
         std::swap(stack_, rhs.stack_);
         }

   public: // ctors & dtor & overloaded copy assignment operator.

      Stack () 
         : top_{0}, stack_{new DataType[DEFAULT_SIZE]}
         { }

      Stack (const Stack& rhs)
         : top_{rhs.top_}, size_{rhs.size_},
               stack_{new DataType[size_]} {
         std::copy(rhs.stack_, rhs.stack_ + rhs.size_, stack_);
         }

      explicit Stack (size_t size)
         : top_{0}, size_{size}, stack_{new DataType[size_]}
         { }

      ~Stack () noexcept {
         delete [] stack_;
         stack_ = nullptr;
         }

      Stack& operator= (const Stack& rhs) {
         if (this != &rhs) {
            Stack tmp{rhs};
            swap(tmp);
            }
         return *this;
         }

   public: // C++11 move ctor, & move assignment operator.

      Stack (Stack&& rhs) noexcept
         : top_{rhs.top_}, size_{rhs.size_}, stack_{rhs.stack_} {
         rhs.size_ = rhs.top_ = 0;
         rhs.stack_ = nullptr;
         }

      Stack& operator= (Stack&& rhs) noexcept {
         swap(rhs);
         return *this;
         }

   public: // methods | member functions

      bool isempty() const noexcept { return top_ == 0; }
      bool isfull() const noexcept { return top_ == size_; }
      size_t length() const noexcept { return top_; }
      size_t capacity() const noexcept { return size_; }

      void push (const DataType& data) {
         if (isfull()) 
            throw std::runtime_error("Stack full");
         stack_[top_++] = data;
         }

      void pop (DataType& dest) {
         if (isempty())
            throw std::runtime_error("Stack empty");
         dest = stack_[--top_];
         }

      DataType top() const {
         if (isempty())
            throw std::runtime_error("Stack empty");
         return stack_[top - 1];
         }
   };

} // namespace

#endif // _STACK_HPP_

This class uses a C++11 feature called field initialiser, to provide the size_ member with a default value. Field initialisers create code that is called before any constructor.

Just a reminder: all functions have been made inline, to keep all the code together. Any of the patterns to either make any of them inline outside the class, or make any non-inline in a separate .cpp file, could have been employed.

Client Program

This example client / test program exercises a few of the Stack features. It forces an underflow, which will throw an exception, so the exception is handled by enclosing most of the code in a try block, and the exception is ‘handled’ in the catch block.

`main.cpp` — Stack Test / Client

/*!@file  main.cpp
*  @brief Stack Test / Client
*/
#include <iostream>
#include <iterator>
#include <utility>

#include "Stack.hpp"

int main () {
   using std::cout;

   try{
      ADT::Stack s1{};         // default ctor called.
      s1.push(1.2);
      s1.push(2.3);
      s1.push(3.4);

      cout << "s1.length() = " << s1.length() 
         << ", s1.capacity() = " << s1.capacity() << "\n";

      ADT::Stack s2{s1};       // copy ctor called.

      cout << "s2.length() = " << s2.length() 
         << ", s2.capacity() = " << s2.capacity() << "\n";

      ADT::Stack s3{};         // default ctor called.
      s3 = std::move(s1);      // s1 *moved* to s3 via the 
                               // move assignment operator.

      cout << "s3.length() = " << s3.length() 
         << ", s3.capacity() = " << s3.capacity() << "\n";

      ADT::DataType d;
      s3.pop(d); cout << "d = " << d << std::endl;
      s3.pop(d); cout << "d = " << d << std::endl;
      s3.pop(d); cout << "d = " << d << std::endl;
      s3.pop(d); cout << "d = " << d << std::endl;
      }
   catch (std::exception& ex) {
      std::cerr << "Exception: " << ex.what() << std::endl;
      }

   ADT::Stack s4{std::move(ADT::Stack{20})}; // force move ctor.
   cout << "s4.length() = " << s4.length() 
        << ", s4.capacity() = " << s4.capacity() << "\n";

   return EXIT_SUCCESS;
   }

A more complete test client would check if overflow throws an exception, and whether all the constructors work correctly. It would be a good exercise to add functions that take a Stack as parameter, and / or return a Stack. Overloading the insertion operator to dump the whole stack, could also be useful.

NOTE — Copy Elision

You may get warnings about the use of std::move, which prevents a special optimisation technique called copy elision, but we wanted to test that the move constructor and move assignment get called. If that bothers you, you can add the -Wno-pessimizing-move command line option to GCC's g++ to suppress the warning, or you can remove the offending call.

Template Stack Version

Here, for completeness, and without much explanation, is the template version of the Stack abstract data type. Just a few points to keep into consideration:

The template<⋯> construct applies only to the next declaration, definition, or type.
Older code may use class instead of typename in template parameter list. It is still valid.
Class templates are instantiated when used for the first time. Effectively making a copy of the template.

`Stack.hpp` — Stack Template

///@file  Stack.hpp
///@brief Stack Template Specification & Implementation

#if !defined _STACK_HPP_
    #define  _STACK_HPP_

#include <stdexcept>
#include <algorithm>
#include <utility>

namespace ADT { // abstract data type namespace //

template <typename DataType>
class Stack {

   public: // constant(s) & types

      static constexpr size_t DEFAULT_SIZE = 10U;
      using value_type = DataType;

   private: // fields | instance variables | data members

      int top_;
      int size_{DEFAULT_SIZE};
      DataType* stack_;
      inline void swap (Stack& rhs);

   public: // ctors & dtor & overloaded copy assignment operator.

      Stack () 
         : top_{0}, stack_{new DataType[DEFAULT_SIZE]}
         { }

      Stack (const Stack& rhs)
         : top_{rhs.top_}, size_{rhs.size_},
               stack_{new DataType[size_]} {
         std::copy(rhs.stack_, rhs.stack_ + rhs.size_, stack_);
         //or: copy(rhs.stack_, rhs.stack_ + rhs.top_, stack_);
         }

      explicit Stack (int size)
         : top_{0}, size_{size}, stack_{new DataType[size_]}
         { }

      ~Stack () noexcept {
         delete [] stack_;
         stack_ = nullptr;
         }

      Stack& operator= (const Stack& rhs);

   public: // C++11 move ctor, & move assignment operator.

      Stack (Stack&& rhs) noexcept
         : top_{rhs.top_}, size_{rhs.size_}, stack_{rhs.stack_} {
         std::cout << "Move ctor\n";
         rhs.size_ = rhs.top_ = 0;
         rhs.stack_ = nullptr;
         }

      Stack& operator= (Stack&& rhs) noexcept {
         swap(rhs);
         return *this;
         }

   public: // methods | member functions

      bool isempty() const noexcept { return top_ == 0; }
      bool isfull() const noexcept { return top_ == size_; }
      int length() const noexcept { return top_; }
      int capacity() const noexcept { return size_; }

      void push (const DataType& data) {
         if (isfull()) 
            throw std::runtime_error("Stack full");
         stack_[top_++] = data;
         }

      void pop (DataType& dest) {
         if (isempty())
            throw std::runtime_error("Stack empty");
         dest = stack_[--top_];
         }

      DataType top () const {
         if (isempty())
            throw std::runtime_error("Stack empty");
         dest = stack_[top_ - 1];
         }
   };

template <typename DataType>
inline void Stack<DataType>::swap (Stack& rhs) {
   std::swap(top_, rhs.top_);
   std::swap(size_, rhs.size_);
   std::swap(stack_, rhs.stack_);
   }

template <typename DataType>
Stack<DataType>& Stack<DataType>::operator= (const Stack& rhs) {
   if (this != &rhs) {
      Stack tmp{rhs};
      swap(tmp);
      }
   return *this;
   }

} // namespace
#endif

Not much has to be changed in the client code. For cleaner code, we could have created a type alias for ADT::Stack<double> and replaced all occurrences with that alias, e.g.:

   using dStack = ADT::Stack<double>

But we did not, in order to keep it as close as possible to the previous client code.

`main.cpp` — Stack Template Client

///@file  main.cpp
///@brief Stack Template Test / Client

#include <iostream>
#include <iterator>
#include <utility>

#include "Stack.hpp"

int main () {
   using std::cout;

   try{
      ADT::Stack<double> s1{};
      s1.push(1.2);
      s1.push(2.3);
      s1.push(3.4);

      cout << "s1.length() = " << s1.length() 
         << ", s1.capacity() = " << s1.capacity() << "\n";

      ADT::Stack<double> s2{s1};

      cout << "s2.length() = " << s2.length() 
         << ", s2.capacity() = " << s2.capacity() << "\n";

      ADT::Stack<double> s3{};
      s3 = std::move(s1); // s1 not valid anymore.
      cout << "s3.length() = " << s3.length() 
         << ", s3.capacity() = " << s3.capacity() << "\n";

      ADT::Stack<double>::value_type d;
      s3.pop(d);
      cout << "d = " << d << std::endl;
      s3.pop(d);
      cout << "d = " << d << std::endl;
      s3.pop(d);
      cout << "d = " << d << std::endl;
      s3.pop(d);
      cout << "d = " << d << std::endl;
      }
   catch (std::exception& ex) {
      std::cerr << "Exception: " << ex.what() << std::endl;
      }

   ADT::Stack<double> s4{std::move(ADT::Stack<double>{20})};
   cout << "s4.length() = " << s4.length() 
        << ", s4.capacity() = " << s4.capacity() << "\n";

   return EXIT_SUCCESS;
   }

2022-08-18: Change typedef to using and int to size_t. [brx]
2017-11-18: Update to new admonitions. [brx]
2017-09-15: Created. Edited. [brx;jjc]