Writing various implementations of Stack class in C++

Question

I've recently taken a course in Data Structures in Java and I can write various structures and implement them in various ways in Java easily. I'm currently transferring this knowledge to the world of C++ which is a little different. I currently wrote a header file for a Stack interface (like you would writing an interface in Java for Stack) and I want to implement it in various ways (linked lists, array, vector, etc.) so I can master the idea of implementing structures in any language. The problem I'm currently having with C++ is understanding the notion of using pointers in my Stack and references (E&) plus making sure I can write various source implementations of Stack.h. Here is my current stack header...

/*
 * File: stack.h
 * -------------
 * Interface file of the Stack class. Follows a last-in/ first-out (LIFO) order. Includes contracts for the method bodies of Stack.
*/

#ifndef _stack_h
#define _stack_h

/*
 * declaration of Stack using template with type E for any data type or object using the Stack structure.
 *
 */

  template <typename E>
  class Stack {

    public: 

    //constructor blank
    Stack();

    //destructor
    ~Stack();

    //constructor with integer size
    Stack(int);

    //number of items in stack.
    int size() const;

    //is stack empty?
    bool empty() const;

    //top element of stack
    const E& top() const throw(StackEmpty);

    //push e onto the stack.
    void push(const E& e);

    //remove top element from stack
    void pop() throw(StackEmpty);

    //pop and return.
    E popReturn();

    //returns a string form of stack.
    std::string toString();
};

// Error exception
class StackEmpty : public RuntimeException {
    public:
       StackEmpty(const std::string& err) : RuntimeException(err) {}
};

#endif

Sorry for the formatting! :) Currently I'm working on the Array and Linked List implementation of this stack. I understand that a header file creates a link between files it is included in. I want to insure that when I create a stack for testing I can use both implementations I wrote with this header. I'm also not sure if I should use the keyword virtual or not to make an official interface. I know in java when you declare an implementation for Stack you would use

Stack test = new ArrayStack();

Is that the same for C++ to use a globalized header file and use different implementations of this Stack? Also this code is burrowed from a Data Structures book in C++ but sadly the authors do not say to make these interfaces a header file or not, and where to include that error checking exception for an empty stack. I just placed it in this file. C++ hasn't been a great language to me but I know that if I wanna build larger projects like Compilers, games, audio/ video players, OS, and writing an IDE for a new language that this and C are important to master. Please give me any insight to my current situation if possible I would greatly appreciate it. If anyone also can explain pointers and references in C++ I would greatly accept the knowledge. I believe the E& is a reference but the book didn't specify. Thank you! :)

P.S. this is what I thought would work for C++ for using different implementations of a header....

#include "stack.h"

Stack test = new ArrayStack();
Stack test2 = new LinkedStack();

Answer 1

Your code has a number of problems.

template <typename E>

Unless you honestly need run-time polymorphism (which you almost certainly don't in this case) you want to pass the underlying storage you're going to use as a template parameter instead of using inheritance:

template <typename E, typename Container = std::vector<E> >

This way, you can avoid (for example) virtual function calls for elementary operations that really don't need it.

//constructor blank
Stack();

You probably don't need to declare this default constructor at all. (See below in the comments about the other constructor you declared).

//destructor
~Stack();

If you're going to use Stack as a base class as you seem to be suggesting, then you want to make the destructor virtual.

//constructor with integer size
Stack(int);

Unless you really want to use an underlying container with a fixed size, there's no real need to specify the size here. If you want to specify a size anyway, I'd probably provide a default value (which is part of what renders the preceding default constructor declaration irrelevant) so you end up with something like this: Stack(int size = 20);

//top element of stack
const E& top() const throw(StackEmpty);

This is bad. Dynamic exception specifications like your throw(StackEmpty) turned out to be a mistake. They've been deprecated for a while now, and will probably disappear soon¹. In addition, if you're going to use inheritance, most of these interface functions should probably be virtual (probably pure-virtual).

//push e onto the stack.
void push(const E& e);

This is all right, but if you want to get the most out of C++, you probably want to add an overload that takes an rvalue reference as well.

//remove top element from stack
void pop() throw(StackEmpty);

This dynamic exception specification has the same problem as above.

//pop and return.
E popReturn();

This has a serious design flaw--if E's copy constructor throws an exception, it will (unavoidably) destroy data. There are two fairly well-known ways to avoid this problem. One is to just eliminate it and require the user to write code like:

Foo f = myStack.top();
myStack.pop();

This way, if the copy constructor throws, myStack.pop() never executes. The other well known possibility is something like:

void pop(E &dest) { 
    dest = top();
    pop();
}

Either way, we end up with exception safe code--either it completes (and the value is transferred from the top of the stack to the destination) or else it fails completely (and the data remains on the stack), so there was no effect.

//returns a string form of stack.
std::string toString();

In C++ this is normally named to_string.

// Error exception
class StackEmpty : public RuntimeException {
    public:
       StackEmpty(const std::string& err) : RuntimeException(err) {}
};

The standard already defines std::runtime_error. It's probably better to use that until/unless you know C++ well enough to know exactly what you want to do differently.

Also note: if you take the initial advice and make your stack a pure template instead of trying to use inheritance, many of the other comments become moot.

In the end, a stack class for C++ can end up more like this:

template <class T, class C = std::vector<T> >
class Stack { 
    C data;
public:
    void push(T const &t) { 
        data.push_back(t);
    }

    T top() const {  return data.back(); }

    void pop(T &d) { 
        if (data.empty())
            throw std::runtime_error("Attempt to pop empty stack");
        d = data.top();
        data.pop_back();
    }

    bool empty() const { return data.empty(); }
};

You've indicated that you want to test it with different underlying containers. Here's how you'd do it with three standard containers:

#include "stack.h"
#include <vector>
#include <list>
#include <deque>
...
// These two are equivalent:
Stack<int, std::vector<int>> vs;
Stack<int> vs1;

Stack<int, std::list<int>> ls;  
Stack<int, std::deque<int>> ds;

---

^{1. Yes, Java copied this mistake almost intact, then managed to actually make it even worse by adding tight coupling, which destroys one of the biggest advantages of exception handling to start with. About all I can say is: that hurts; don't do it any more.}

Answer 2

I'm not going to comment on the quality, usability, correctness, or "C++-ness" of that stack. To any (C++) programmer, it'd be painfully obvious that a Java programmer wrote that stack class, which might be fine in Java, but there are far better ways in C++.

What I'm going to do is try and answer your question about interfaces and using them, in relation to include files. (Again, let me emphasize that the stack class itself is not good.)

What you might want to do is have a "stack.h", with content similar to this:

template <typename E>
class Stack
{
public:
    // These are *usually* useless in an abstract interface 
    // Stack();
    // ~Stack();
    // Stack(int);

    // Every concrete class inheriting from this class must implement all these:
    virtual int size() const = 0;
    virtual bool empty() const = 0;
    virtual const E& top() const throw(StackEmpty) = 0;
    virtual void push(const E& e) = 0;
    virtual void pop() throw(StackEmpty) = 0;
    virtual E popReturn() = 0;
};

Now, you might have a "vector_stack.h" like this:

#include "stack.h"

template <typename E>
class VectorStack
    : public Stack<E>
{
public:
    VectorStack() {...}
    virtual ~VectorStack() {...}
    Virtual VectorStack(int) {...}

    virtual int size() const override {...}
    virtual bool empty() const override {...}
    virtual const E& top() const throw(StackEmpty) override {...}
    virtual void push(const E& e) override {...}
    virtual void pop() throw(StackEmpty) override {...}
    virtual E popReturn() override {...}
};

You'd do the exact same thing with any other implementation you want to do.

Now, in the code file that you want to use all these, you do this:

#include "VectorStack.h"
#include "ListStack.h"
#include "WhateverStack.h"

...
// I apologize to all C++ programmers, for not using unique_ptr<>!
Stack<int> * s1 = new VectorStack<int>;
Stack<int> * s2 = new ListStack<int>;
Stack<int> * s3 = new WhateverStack<int>;
...
...
// Don't forget to delete if you use raw pointers; you're
// not in Kansas anymore!
delete s3;
delete s2;
delete s1;

But this is not very "C++", not to mention flexible or efficient. Specially in this case, for containers like a stack. But if you insist on that interface (in the general sense,) this is probably what you have to do.

Oh, and don't forget to #include the headers that you use, such as <string>. And note that if you want those exception specifications (don't do it!) the declaration for your exception class must go before the declaration of your class.

(By the way, I'm pretty sure it's the popReturn method that throws, not pop.)