6
\$\begingroup\$

Please feel free to be as harsh as possible.

Implementation file:

#include "Stack.h"
#include <iostream>
using namespace std;

// Initializes an empty Stack.
Stack::Stack() {
    this->head = new node();
    this->num_elements = 0;

    // set default values for head
    this->head->next = 0;
    this->head->value = 0;
}

// Cleans up memory before the Stack's destruction.
Stack::~Stack() {
    while (this->head->next != 0) {
        pop();
    }
    delete this->head;
}

// Pushes value onto the top of the stack.
void Stack::push(int value) {
    node* newTopNode = new node();
    newTopNode->value = value;

    // currentTopNode may be null if stack is empty
    node* currentTopNode = this->head->next;

    this->head->next = newTopNode;
    newTopNode->next = currentTopNode;

    this->num_elements++;
}

// Pops the top-most value off the stack and returns its value.
int Stack::pop() {
    if (this->head->next == NULL) {
        cout << "\nIllegal State Exception: You cannot pop an empty stack." << endl;
        return 0;
    } else {
        node* topNodeToRemove = this->head->next;

        // save the value of the node before deleting it
        int topNodeValue = topNodeToRemove->value;

        this->head->next = this->head->next->next;

        delete topNodeToRemove;
        this->num_elements--;

        return topNodeValue;
    }
}

// Returns the value at the top of the stack.  Works similarly to pop(), but
// retains the internal structure of the stack.  That is, it does not remove
// the top-most element.
int Stack::getTopElement() const {
    if (this->head->next == NULL) {
        cout << "\nIllegal State Exception: You cannot get the top element of an empty stack." << endl;
        return 0;
    } else {
        return this->head->next->value;
    }
}

// Returns the number of elements currently in the stack.
int Stack::size() const {
    return this->num_elements;
}

Header file:

#ifndef STACK_H_
#define STACK_H_

class Stack {
public:
    Stack();
    ~Stack();
    void push(int);
    int pop();
    int getTopElement() const;
    int size() const;

private:
    struct node {
        int value;
        node* next;
    };

    node* head;
    int num_elements;
};

#endif // STACK_H_
\$\endgroup\$
5
\$\begingroup\$
  • Do not use using namespace std.

  • In the constructor and push(), it looks like you're calling new on a function. It should be node.

  • Prefer nullptr to NULL and 0 for the node pointers if you're using C++11. Otherwise, you should choose either NULL or 0 for node pointers and keep it consistent.

  • You don't need this-> everywhere as the code already has the current object in scope.

  • It's needless to call pop() in the destructor. For one thing, pop() returns a value. You should just be using delete.

    Instead, have head point to the first element, loop through the stack (stopping when NULL is hit) and call delete on each node. With this, you won't need to delete head at the end.

  • pop() and getTopElement() might be best as void. Here, a 0 is returned if the list is empty. Sure, no errors happening there. But then the calling code will take it as an element 0, never knowing whether or not the stack is empty. If you make them void, you can simply return if the stack is empty. As for retrieving an element, that's why you have getTopElement(). Once you get the value with getTopElement(), call pop() after that.

    Regarding checking for an empty stack, you could make a public empty() function for calling code. The two functions above should still check for an empty stack, but containers like this usually utilizes such a function. This could go in the header:

    bool empty() const { return num_elements == 0; }
    
  • You could make your class more useful by using templates. This will allow you to populate the stack with any type instead of just ints.

\$\endgroup\$
  • \$\begingroup\$ Thank you Jamal for your suggestions. Much appreciated! 1 question: how would I get the top element if both pop and getTopElement are set to void? I don't get it? \$\endgroup\$ – Q Liu Oct 4 '13 at 2:29
  • \$\begingroup\$ @628496: Actually, you can still have top() return a value. It's up to you. If you want to make it void anyway, then you would pass in a variable from the calling code by reference. pop() should still be void. Have a look at std::stack. \$\endgroup\$ – Jamal Oct 4 '13 at 2:34
  • \$\begingroup\$ @628496: The link provided will give you much info on that. Essentially, it's discouraged because it can cause name-clashing (bugs). For instance, if you create your own function with the same name and parameter types as a function in the STL, the compiler will be confused and you'll get undefined behavior. I had to break this habit when I first started, too. :-) \$\endgroup\$ – Jamal Oct 4 '13 at 2:41
4
\$\begingroup\$

You are using a Sentinel at the beginning of the list, but this is not really needed.

Sentinel are very useful for double linked list but don't make things easier for singly linked list. Your code will be simlified by removing it.

You can make your code simpler by moving the initialization of the node into its constructor.

The destructor can be made simpler just be running accross the nodes and deleting them. There is no point in the extra work in pop() to keep the object in a valid state.

class Stack
{
    struct Node
    {
        int   value;
        Node* next;
        Node(int v, Node* n): value(v), next(n) {}
    };

    Node*   head;
    int     size;

    Stack() :head(NULL), size(0) {}
    void push(int v)  { head = new Node(v, head);++size;}
    void pop()        { Node* old = head; head = old->next;delete old;--size;}
    bool empty()      { return size == 0;}
    // Calling this when empty() is true is undefined behavior.
    // Make sure you know that the list is valid before calling.
    int  top()        { return head->value;}
    int  size()       { return size;}
    ~Stack()
    {
        for(Node* next = head;next;)
        {
            Node* old = next;
            next      = old->next;
            delete old;
        }
    }
}
\$\endgroup\$
1
\$\begingroup\$

I see it has been some time since you asked this question. I found out that your implementation of pop() function is deleting top element from stack but does not assign second as new top. Here is my suggestion on how to implement this:

int Stack::pop() {
    if (head->next == NULL) {
        std::cout << "\nIllegal State Exception: You cannot pop an empty stack." << std::endl;
        return 0;
    }
    int val = head->next->value; // Value to return
    node *newTopElemen = head->next->next; // Second element from top assigned to temp
    delete head->next; // Deleting a pointer to old top element
    head->next = newTopElemen; // Second element from top is now first element
    num_elements--;
    return val;
}
\$\endgroup\$
  • \$\begingroup\$ this->head->next = this->head->next->next; assigns second as the new top in the original code. \$\endgroup\$ – mdfst13 Feb 4 '16 at 19:22

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.