3
\$\begingroup\$

I have made a basic stack class utilizing a linked list for data storage and \$O(1)\$ push and pop and just want some basic feedback on the class to see if there is anything basic I missed. It seems to be working perfectly and I know there are no memory leaks. I'm just being cautious and wondering if there is one or two big things I am missing or doing wrong.

template <typename T>
class Stack {
public:
  struct Node {
    T data;
    Node *next = nullptr;
    Node(T data) : data(data) {}
    Node(T data, Node *next) : data(data), next(next) {}
  };
  Node *top;
  int size_;

  Stack() : size_(0), top(nullptr) {}

  bool empty() {
    return top == 0;
  }

  void push(T data) {
    if(empty()) {
      top = new Node(data);
      size_++;
    } else {
      top = new Node(data, top);
      size_++;
    }
  }

  T pop() {
    if(!empty()) {
      T ret = top->data;
      Node *tmp = top->next;
      delete top;
      top = tmp;
      size_--;
      return ret;
    }

    return -1;
  }

  int size() {
    return size_;
  }

  ~Stack() {
    if(empty()) return;

    if(size_ == 1) {
      delete top;
      return;
    }

    Node *current = top;
    Node *next;
    while( current != 0 ) {
        next = current->next;
        delete current;
        current = next;
    }
    top = nullptr;

  }

};
\$\endgroup\$
  • \$\begingroup\$ Take a look into const methods. empty() and size() should be const. \$\endgroup\$ – glampert Sep 20 '15 at 18:16
3
\$\begingroup\$

Your code is easy to read, formatting is pretty consistent, and does indeed do what it is supposed to as far as I can tell, so that's a good. I just have a few suggestions.

class Stack {
public:

Well if everything is public, use a struct instead, it will save you a few keystrokes. But the size_ and top members probably shouldn't be public - they're not meant to be inspected (much less changed) from outside your class.

bool empty() { return top == 0; }
while (current != 0) {

Prefer nullptr instead of 0 (you already did that in other places).

void push(T data) {
  if(empty()) {
    top = new Node(data);
    size_++;
  } else {
    top = new Node(data, top);
    size_++;
  }
}

You can simplify this: if the stack is empty, then top is null, and new Node(data) does the same thing as new Node(data, nullptr). So you don't need the conditional, you can simplify it to:

void push(T data) {
  top = new Node(data, top);
  size_++;
}

The pop function will fail to compile for e.g. Stack<std::string>: you can't construct a string from -1. Your only real option here is to throw an exception if pop is called on an empty stack. (You should look at the standard container's interface: they have separate top() and pop() members. See this answer for example as for why it is done that way.)

And your destructor is a bit too complex, you don't need the two special cases as they'll be handled by the main loop just fine: if empty(), top is null so the while loop simply won't run. If there's just one element, the while loop will run just once. So you can cut it down to:

~Stack()
{ 
  while (top != nullptr) {
    Node *next = top->next;
    delete top;
    top = next;
  }
}

One last observation - what happens if someone writes this:

Stack<int> s1;
s1.push(1);
Stack<int> s2 = s1;
s1.pop();
s2.pop();

Unfortunately, this will compile but produces undefined behavior - the second pop will access free'd memory. You should either implement the rule of three (sometimes now called the "rule of 5" taking into account move constructor and move assignment), or simply not allow copying of your stacks:

Stack(Stack const&) = delete;
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.