Simple stack implementation

Question

I am not experienced in C++, and wrote this code for implementing a stack data structure using a linked list.

Can you please point out any flaws, errors, stupid mistakes, general improvements etc that can make this code better?

#include <iostream>                                                                      
using namespace std;

struct Node;

struct Node {
    int data;
    Node* next;
};

class Stack {
public:
    Node* first;
    Node* last;

    Stack() {
        first = 0;
        last = 0;
    }

    ~Stack() {
         while (first != 0) { pop(); }
    }

    Stack& push(int value) {
        Node* temp = new Node;
        temp->data = value;
        temp->next = 0;

        if (first == 0) {
            first = temp;
            last = temp;
        } else {
            last->next = temp;
            last = last->next;
        }

        cout << "Pushed " << value << " on the stack\n";

        temp = 0;
        return *this;
    }

    Stack& pop() {
        if (first == 0) {
            cout << "No nodes to pop.\n";
        } else {
                // only one node left
                if (first == last) {
                cout << "Popped " << first->data << " off the stack\n";
                delete first;
                first = 0;
                last = 0;                                                                
                return *this;
            }

            Node* temp = first;
            while (temp->next != last) {
                temp = temp->next;
            }
            cout << "Popped " << last->data << " off the stack\n";
            delete last;
            last = temp;
            last->next = 0;
        }
        return *this;
    }
};

int main() {
    Stack s;
    s.pop();
    s.push(1);
    s.push(2);
    s.pop();
    s.push(3).push(4);
    s.pop().pop();
    return 0;
}

Answer 1

Style

Please learn to indent your code consistently.
This is really hard to read and make sure ti works.

Algorithm

I would expect both push() and pop() to have a complexity of O(1). Unfortunately the pop is O(n) as you have to search to the end to remove the last item.

        while (temp->next != last) {
            temp = temp->next;
        }

You can solve this by using a doubly linked list. Then removing the last item would be:

       temp = last->prev;

Personally I would use a doubly linked list and sentinel values (thus you don't need to check for NULL). This makes both inserting and removing the values very simple.

 // Note:  First points at the sentinel.
 //        Last points at the last item inserted.
 //        If no items are inserted then it points at the sentinel.
 //        When there are no items the sentinel points at itself in next/prev
 //        thus making the list circular.
 stack& push(int value)
 {
                        //  Value   Prev   Next
     Node*  temp = new node(value,  last,  last->next);
     last->next->prev = temp;
     last->next       = temp;
     last = temp;
     return *this;
 }
 stack& pop()
 {
     if (first == last)
     {    throw std::runtime_error("Bad Pop");
     }
     Node*  temp = last;
     last->next->prev = temp->prev;
     last->prev->next = temp->next;
     delete temp;
     return *this;
 }

Code Comments

Stop doing this

using namespace std;

Its a bad habit to get into it. See my other posts for an explanation.

Use encapsulation correctly.

public:
    Node* first;
    Node* last;

Member variables should not be public.
Modification of the object state should only be through a controlled environment (method call).

Note: It is OK for the Node to have all public member variables (ie a struct)

struct Node {
    int data;
    Node* next;
};

This is because you never expose a Node object via the Stack interface. Though personally I would make node a private sub class inside the Stack class.

Use a constructor in Node to set it up.

    Node* temp = new Node;
    temp->data = value;
    temp->next = 0;

    // Can be written:
    Node* temp = new Node(value, 0);

Don't bother with this.
It does not add to readability and it does no work.

    temp = 0;

In main if you don't explicitly return the compiler inserts a return 0. Thus if there is no possibility of an error state for your program then don't return anything (this is an indication that it will always work).

int main() {
    // return 0;  Don't need this if the application always works.
}

Answer 2

A few comments, wrt style.

#include <iostream>                                                   
using namespace std;

You don't need a forward declaration of struct Node.

//struct Node;

You could add a constructor here just like in class. So your initialization is simpler.

struct Node {
    int data;
    Node* next;
    Node(int d):data(d), next(0){}
};

It may be a good idea to write an abstract class as an interface, and then write the concrete class to conform to it. Another idea is to try to templatize Node so that the data can be any type. Also look at the stack class in STL

You may also want top() and empty() methods

on logic: If you are going to implement a stack using a linked list, you don't really need to keep a first and a last. Just keep the reference to the top element. On push, create a new node, set its next to the current top, and set it to top. On pop, set the top to the next of current top, and delete the node. Something along the lines of: (may contain bugs.)

struct Node {
    int data;
    Node* next;
    Node(int v, Node* n):data(v),next(n) {}
};

class Stack {
  public:
    Node* top;
    Stack():top(0){}
    ~Stack() {
      while (top != 0) pop();
    }
    Stack& push(int value) {
      top = new Node(value, top);
      return *this;
    }    
    Stack& pop() {
      if (!top) throw "No nodes to pop.";
      Node* t = top;
      top = top->next;
      delete t;
      return *this;
    }
};

Answer 3

Adding to what has already been mentioned by others.

1. Since you wish to learn C++, it is alright to implement a stack class. On the other hand, if you want a stack class for use in a production project, it would be wiser to simply use the built-in STL stack class. Humble thyself and reuse :)

2. The std namespace

   using namespace std;
   

   You are dumping all the identifiers from the std namespace into your global namespace. This defeats the purpose of having namespaces. Since the only thing that you are using from the std namespace is cout, you can write using std::cout; or std::cout << "Pushed " << value << " on the stack\n"; Read this for more.

3. In the Stack class's constructor, prefer initialization lists to assignment. Read more here.

4. In future, when you go one step forward and start implementing reusable classes, you would need to start thinking about how another part of your code (say, another class) can use your Stack class. Currently, this is not (directly/gracefully/intuitively) possible because the other class can only push data onto the stack; it cannot retrieve any data since the pop() method does not return any int data.

5. For containers like the stack, you should also (at least) implement overloaded assignment operator and copy constructor.