Stack Class Example

Simple Stack Abstract Type Implementation

Encapsulation is a useful feature of object-oriented languages, even without considering in­he­ri­tan­ce or poly­mor­phism. This is an illustration of some of the C++ syntax features related to en­cap­su­la­tion, using a simple Stack class. It also includes a template version.
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 val­ues are pushed or popped. Practical implementations must also deal with popping from an emp­ty stack (un­der­flow), 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 pre­sent­ed 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++ stan­dard li­bra­ry 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) fea­tures. It throws exceptions on stack underflow or underflow. Memory for the stack is dy­na­mi­cal­ly al­lo­ca­ted, and because of that feature, a proper copy constructor, and over­load­ed as­sign­ment op­e­ra­tor 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.hppStack 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 //

typedef double DataType;

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 de­fault val­ue. 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 pat­terns to either make any of them inline outside the class, or make any non-inline in a se­pa­rate .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.cppStack Test / Client

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

NOTECopy Elision

You may get warnings about the use of std::move, which prevents a special op­ti­mi­sa­tion technique called copy elision, but we wanted to test that the move constructor and move as­sign­ment 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:

Stack.hppStack 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 const int 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.:

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

main.cStack Template Client

2017-11-18: Update to new admonitions. [brx]
2017-09-15: Created. Edited. [brx;jjc]