[ACCEPTED]-Node-based stack class (need peer review)-stack

Accepted answer
Score: 23

First, a few general comments which don't cause 145 problems in this case, but some may do so 144 in other situations:

You should only throw 143 exceptions derived from the class std::exception. C++ does 142 allow you to throw any type (like a string, in 141 your case), but it's a really bad idea.

Class 140 members should be initialized with initializer 139 lists, as shown below: (this can cause errors 138 in other cases. If you don't use the initializer 137 list, the members are first default-constructed, and 136 then the assignment operator is used in 135 the body of the constructor to overwrite 134 them. Not all types have an assigment operator, or 133 the assignment operator may have undesirable 132 side effects, so not using initializer lists 131 can be problematic)

Node(int val, Node* ptrToLast) : value(val), prev(ptrToLast) {}
Stack() : size(0), top(NULL) {}

Naming your functions 130 return* us pretty pointless. Just call them size() and 129 topPtr(), or perhaps getSize() and getTopPtr()

Second, you didn't follow the 128 rules. ;) Your stack class has two member 127 variables, it was only allowed to have one. :)

Finally, things 126 that break the stack:

This will crash, as 125 you try to dereference a null pointer:

void test() {
  Stack s;
  s.peek(); // crashes
}

This 124 will leak memory, as the allocated node 123 is never deleted (the Stack destructor should 122 do that):

void test() {
  Stack s;
  s.push(1);
}

The destructor should look something 121 like this:

~Stack() {
  while (top != NULL){
    Node* next = top.returnPtr();
    delete top;
    top = next;
  }
}

This one should be fun too:

void test() {
  Stack s;
  s.push(1);
  Stack t(s);
  s.pop();
}

t.returnSize() will 120 now return 1, but t.top points to the node in 119 s that was just deleted. This should be fixed 118 by defining a copy constructor and an assigment 117 operator for the stack (and perhaps for 116 the node class as well) The copy constructor 115 would look like this:

Stack(const Stack& s);

and is called if you 114 initialize one stack from another, like in the above. The 113 assignment operator looks like this:

Stack& operator= (const Stack& s);

and 112 is called if I assign one stack to another, after 111 both are initialized:

Stack s;
Stack t;
t = s; // now both are already initialized, so the assigment operator is used, not the copy constructor

The role of these functions 110 is to ensure that t becomes a copy of s. So each 109 node in s should be copied, and assigned 108 to t, to avoid them pointing to the same 107 nodes. (Which is a wonderful example of 106 your question about ownership earlier, btw. The 105 nodes should belong to exactly one Stack 104 object. If it becomes shared between multiple, you 103 have a problem, and it's just a matter of 102 time before it turns into a crash)

And finally, if 101 we want to get a bit nastier:

void test() {
  Stack s;
  s.push(1);
  s.push(2);
}

What happens 100 if the memory allocation for the second 99 node fails (perhaps we ran out of memory. Unlikely, but 98 it can happen). An exception is thrown after you 97 incrmented size. The size of s will now 96 be 2, even though top still points to the first 95 node If you think this is too unlikely a 94 problem to be taken seriously, imagine a 93 small extension to your class. Let's say 92 it was a template, so that it could store 91 other types than an int.

That means that 90 every time we create a node, we have to 89 call the value type's copy constructor. That 88 could throw an exception too. We don't know, because 87 we have no clue which type the user might 86 try to store in the stack.

The notion of 85 "Exception safety" is important 84 and really really difficult to get right. Basically, which 83 state is your class in if an exception is 82 thrown? Is it still in a valid state? (it 81 should always be). Has it lost any data 80 (for some cases that might be unavoidable, for 79 others it can be avoided with care), and 78 if it has lost data, has it been deleted 77 correctly? Destructors called, memory released? (again, this 76 should always be the case)

The last point 75 here is why I was so sure you'd have at 74 least one bug. Everyone gets exception safety 73 wrong, including me most of the time. Writing 72 a correct implementation of sometihng as simple 71 as a stack is surprisingly difficult in 70 C++. :)

Bonus:

In response to comments asking about 69 copy constructors, destructors and RAII, let's 68 just do the whole thing: First, let me say 67 that there is probably one or two bugs left 66 I haven't spotted. Second, here's the code 65 I tested against, and all the following 64 passes it. Feel free to run your own code 63 through it as well. (it should work as is, except 62 you'll have to rename the getSize function): (the 61 live variable is one I added for debugging. I've 60 modified my Stack implementations so that 59 constructors increment it, and destructors 58 decrement it, just to verify that the number 57 of constructions and destructions are equal. This 56 should obviously be removed from the Stack 55 class once you're sure it works

Test code

static int live; // debugging - keeps track of how many nodes have been allocated. Constructors add 1, destructors subtract. It should end in 0

#include "stack.h"
#include <iostream>
#include <cassert>

int main(){
    {
        // test stack creation + push
        Stack s;
        s.push(1);
        s.push(2);
        s.push(3);
        assert(s.getSize() == 3);

        Stack t;
        t.push(4);
        t.push(5);
        t.push(6);
        assert(t.getSize() == 3);

        // test assigment operator when both stacks contain data
        s = t;
        assert(s.getSize() == 3);
        assert(s.peek() == 6);
        assert(t.peek() == 6);

        Stack u(s);
        // test self assigment when stack contains data
        u = u;
        assert(u.getSize() == 3);
        assert(u.peek() == 6);


        Stack v;
        // test copy construction from stack with data
        Stack w(t);
        assert(w.getSize() == 3);
        assert(w.peek() == 6);
        assert(t.getSize() == 3);
        assert(t.peek() == 6);

        // test assignment operator when source is empty, destination contains data
        w = v;
        assert(w.getSize() == 0);
        assert(v.getSize() == 0);

        // test copy construction from empty stack
        Stack x(v);
        assert(x.getSize() == 0);
        assert(v.getSize() == 0);

        // test pop
        assert(t.pop() == 6);
        assert(t.pop() == 5);
        assert(t.pop() == 4);

        assert(s.pop() == 6);
        assert(s.pop() == 5);
        assert(s.pop() == 4);
    } // at this point, all allocated stacks go out of scope, so their destructors are called, so now is a good time to check for memory leaks:
    assert(live == 0);
}

Fixed implementation

Now, first 54 the straightforward fix. Copy constructor, assignment 53 operator and destructor have been added 52 on the Stack class. The Node class is still 51 problematic if used in isolation, but as 50 long as it is only used through the Stack, we 49 can make sure nodes get copied and deleted 48 properly. Unfortunately, Stack now needs access 47 to Node.tail_ in order for copying to work, so I made 46 it a friend. So it works, but it's not elegant.

#include <stdexcept> // for std::exception

class Stack;

class Node
{
    private: // changed naming to head/tail, which are commonly used in implementations of linked lists like this. The head is the current element, tail is a pointer to the remainder
        int head_;
        Node* tail_;

    public:
        friend class Stack; // this is necessary for the Stack copy constructor in order to modify the tail pointer after the node is created.
        // the elegant solution had been to define a copy constructor on the Node class as well, but we'll get to that

        int head() const { return head_; }
        Node* tail() const { return tail_; }

        Node(int val, Node* prev) : head_(val), tail_(prev) { ++live; } // use initializer list
        ~Node() { --live; }

        Node(const Node& other) : head_(other.head_), tail_(other.tail_){ ++live; }; // this could be omitted, but I use it to update 'live' for debugging purposes
};

class Stack
{
    private:
        Node* top;
//        int size; // we don't actually need the size at all, according to spec, so I removed it to keep things simple

        bool empty() const { return top == NULL;}

        void freeNodes() { // helper function to avoid duplicate code
            while (!empty()){
                pop();
            }
        }
    public:
        Stack() : top() {} // use initializer list
        ~Stack() { // destructor - the stack is being deleted, make sure to clean up all nodes
            freeNodes();
        }
        Stack(const Stack& other) : top() { // copy constuctor - we're being initialized as a copy of another stack, so make a copy of its contents
            if (other.empty()){
                return;
            }

            top = new Node(*other.top); // copy the first node, to get us started

            Node* otherNext = other.top->tail();            
            Node* current = top;

            while (otherNext != NULL){
                current->tail_ = new Node(*otherNext); // copy the current node
                current = current->tail(); // move to the next node
                otherNext = otherNext->tail();
            }
        }
        Stack& operator= (const Stack& other) {
            if (this == &other){ // If we assign this stack to itself (s = s), bail out early before we screw anything up
                return *this;
            }

            //now create the copy
            try {
                if (other.empty()){
                    freeNodes();
                    top = NULL;
                    return *this;
                }
                // naively, we'd first free our own stack's data before constructing the copy
                // but what happens then if an exception is thrown while creating the copy? We've lost all the current data, so we can't even roll back to a previous state
                // so instead, let's simply construct the copy elsewhere
                // this is almost straight copy/paste from the copy constructor. Should be factored out into a helper function to avoid duplicate code
                Node* newTop = new Node(*other.top); // copy the first node, to get us started

                Node* otherNext = other.top->tail();
                Node* current = newTop;

                while (otherNext != NULL){
                    current->tail_ = new Node(*otherNext); // copy the current node
                    current = current->tail(); // move to the next node
                    otherNext = otherNext->tail();
                }
                // once we're sure that we're able to create the copy of the other stack, we're ready to free the current one
                // this is a bit of duplicate code
                freeNodes();
                top = newTop;
                return *this;
            }
            catch (...){      // if an exception was thrown
                throw;        // and rethrow the exception so the application can deal with it
            }
        }

        // Node* returnTopPtr() { return top; } // not necessary. It's not a required part of the public interface, and class members can just access the top variable directly

        void push(int);
        int pop();
        int peek() const;

        int getSize() const{
            if (empty()){ return 0; }
            int i = 0;
            for (Node* cur = top; cur != NULL; cur = cur->tail_, ++i){}
            return i;
        }
};

void Stack::push(int value)
{ 
    Node* currentTop = top;
    top = new Node(value, currentTop); // this could throw an exception, but if it does, our stack will simply be left unchanged, so that's ok
}

int Stack::peek() const
{
    if (empty()){
        throw std::exception("Stack is empty");
    }
    return top->head();
}

int Stack::pop()
{    
    if (empty()){
        throw std::exception("Stack is empty");
    }

    Node* tail = top->tail();
    int result = top->head();
    delete top;
    top = tail;

    return result;
}

RAII v. 1

RAII is 45 a lousy name for a vital technique. The 44 basic idea is that every resource allocation 43 (including, but not limited to, memory allocations 42 with new.) should be wrapped in a class which 41 takes care of copying or deleting the resource 40 as necessary. In our case, rather than having 39 Stack keep track of all the nodes, we could simplify 38 things a bit by making the Node class itself 37 do most of that work. Now Node has been given 36 copy constructor, assignment operator and 35 destructor too. The stack now just has to 34 keep track of the top node... almost. It is 33 still a bit iffy because Stack.push allocates new 32 nodes, but Node is now responsible for most 31 of the deletions. . However, it does allow 30 us to get rid of the loops we needed before 29 to delete or copy the node list.

Stack still needs to access thetail_member ofNode`, but 28 this time, I made an accessor function instead 27 of making the class a member. Overall, better, but 26 I'm still not happy with it.

#include <stdexcept>

class Node
{
private:
    int head_;
    Node* tail_;

public:
    int head() const { return head_; }
    Node* tail() const { return tail_; }
    Node*& tail() { return tail_; } // Another way to allow Stack to modify the tail. Needed for pop()


    Node(int val, Node* prev = NULL) : head_(val), tail_(prev) { ++live; }

    ~Node(){ --live; delete tail_; } // it is safe to call delete on a NULL pointer

    Node(const Node& other) : head_(other.head()), tail_(NULL) {
        ++live;
        if (other.tail() == NULL){
            return;
        }
        tail_ = new Node(*other.tail());
    }

    Node& operator= (const Node& other){
        if (this == &other){
            return *this;
        }
        head_ = other.head();
        if (other.tail() != NULL){
            return *this;
        }

        Node* oldTail = tail_;

        try {
            tail_ = new Node(*other.tail());
        }
        catch(...){
            tail_ = oldTail;
            throw;
        }
    }
};

class Stack
{
private:
    Node* top;

    bool empty() const { return top == NULL;}

public:
    Stack() : top() {} 
    ~Stack() {
        delete top;
    }

    Stack(const Stack& other) : top(){
        if (other.empty()){
            return;
        }

        top = new Node(*other.top);
    }

    Stack& operator= (const Stack& other) {
        if (this == &other){
            return *this;
        }

        Node* oldTop = top;

        try {
            top = NULL;
            if (other.top != NULL){
                top = new Node(*other.top);
            }
            delete oldTop;
            return *this;
        }
        catch (...){ 
            delete top;
            top = oldTop;
            throw;  
        }
    }

    void push(int);
    int pop();
    int peek() const;

    int getSize() const{
        if (empty()){ return 0; }
        int i = 0;
        for (Node* cur = top; cur != NULL; cur = cur->tail(), ++i){}
        return i;
    }
};

void Stack::push(int value)
{ 
    Node* currentTop = top;
    top = new Node(value, currentTop);
}

int Stack::peek() const
{
    if (empty()){
        throw std::exception("Stack is empty");
    }
    return top->head();
}

int Stack::pop()
{    
    if (empty()){
        throw std::exception("Stack is empty");
    }

    Node* tail = top->tail();
    int result = top->head();
    if (top != NULL){
        top->tail() = NULL; // detach top from the rest of the list
        delete top;
    }

    top = tail;

    return result;
}

RAII v.2

To solve the 25 problems mentioned above, I decided to change 24 my strategy a bit. Node now does all the heavy 23 lifting, including the push/pop/peek operations. Stack is 22 simply a thin wrapper around these. This 21 turned out to solve most of the problems. Stack no 20 longer needs to mess around with private 19 members of Node, and we have some clearer rules 18 for ownership. The stack owns the top node, and 17 every non-top node is owned by its parent 16 -- and this time, the owner both creates, copies 15 and destroys the node. Much more consistent.

To 14 implement this, I had to add an isLast function 13 on the Node class because otherwise, Stack.pop had 12 no way of knowing whether or not it was 11 time to delete top. I'm not 100% happy with 10 this solution either (and if I hadn't removed 9 the size member from the stack, I could 8 have used that to solve the problem)

But 7 overall, this one is both cleaner and simpler 6 than the above attempts. (It's the only 5 one I spent less than an hour debugging, for 4 one thing. ;))

#include <stdexcept>

class Node {
public:
    Node(int value, Node* prev = 0) : head(value), tail(prev) { ++live;}
    ~Node() { 
        --live;
        delete tail;
    }

    Node(const Node& other) : head(other.head), tail(0) {
        ++live;
        if (other.tail != 0){
            tail = new Node(*other.tail);
        }
    }

    Node& operator= (const Node& other){
        if (this == &other){
            return *this;
        }

        Node* oldTail = tail;
        tail = new Node(*other.tail);
        delete oldTail;

        head = other.head;

        return *this;
    }

    void push(int val){
        tail = new Node(head, tail);
        head = val;
    }

    int peek(){
        return head;
    }
    void pop(){
        Node* oldTail = tail;
        head = tail->head;
        tail = tail->tail; // lol
        oldTail->tail = 0;
        delete oldTail;
    }

    bool isLast() { return tail == NULL; }

    int getSize() const{
        int i = 0;
        for (const Node* cur = this; cur != NULL; cur = cur->tail, ++i){}
        return i;
    }


private:
    Node* tail;
    int head;
};

class Stack {
public:
    Stack() : top(){}
    ~Stack() { delete top; }
    Stack(const Stack& other) : top() {
        if (other.empty()){
            return;
        }

        top = new Node(*other.top);
    }

    Stack& operator= (const Stack& other){
        if (this == &other){
            return *this;
        }

        Node* newTop = NULL;
        if (!other.empty()){
            newTop = new Node(*other.top);
        }
        delete top;
        top = newTop;

        return *this;
    }

    void push(int val){
        if (empty()) {
            top = new Node(val);
        }
        else {
            top->push(val); 
        }
    }

    int peek(){
        if (empty()){
            throw std::exception("Empty stack");
        }
        return top->peek();
    }
    int pop(){
        int result = peek();

        if (top->isLast()){
            delete top;
            top = NULL;
        }
        else {
            top->pop();
        }


        return result;
    }

    int getSize() const{
        if (empty()){ return 0; }
        return top->getSize(); 
    }

private:
    bool empty() const { return top == NULL; }
    Node* top;
};

Since all this started as 3 an attempt to show you why C++ isn't a very 2 nice beginners language, I think I can safely 1 say mission accomplished!

:)

Score: 4

Alright - so here's a quick review. Keep 25 in mind that somethings will be my personal 24 opinion (just like the comment I wrote.)

1 23 - whenever accessing a value or method that 22 you have a pointer into, check if the pointer 21 is valid first! This will cause you to seg-fault 20 otherwise. For example, if you peek before 19 pushing a node in, you call NULL->returnValue(). This 18 is no good.

2 - you don't need the temp pointer 17 you are using in the push & you should 16 check if you are being able to successfully 15 allocate memory.

3 - you need a copy constructor 14 / destructor because your object manages 13 dynamically allocated data. So what happens 12 is that by default, c++ only copies your 11 static values when copying an object & only 10 dealocates memory for static variables when 9 destructing the object. A copy constructor 8 & a destructor makes sure you go through 7 your dynamic memory & take care of it. (IE: for 6 the destructor you want to delete each node.)

4 5 - returnTopPointer is a horrible idea - it 4 gives people access to your internal data 3 & lets them do whatever they want.

If 2 you need help with the copy constructor 1 & destructor just let us know.

Score: 3

In Stack::push(), new can fail (out of memory), but 8 you have already incremented size. It's 7 unlikely to happen, but would lead to an 6 inconsistent state.

You initialize top to 5 NULL, so if you call peek() before pushing 4 anything, you will crash. You should handle 3 that. Similar bad things happen if you 2 call pop() before calling push().

Consider 1 using constructor initializer lists, e.g.:

   Node(int val, Node* ptrToLast) : value(val), prev(ptrToLast) {}
Score: 3

There are many style issues that warrant 23 discussion - but the biggest issue is that 22 whenever you explicitly manage dynamic memory 21 within your class, at a minimum you need 20 a user defined destructor, a copy constructor 19 and an assignment operator to handle all 18 the dynamic memory issues appropriately 17 - or else you will have memory leaks and 16 undefined deletions. The reason you need 15 to explicitly define these functions is 14 because you need a copy or an assignment 13 to make copies of the structures that your 12 head pointer and subsequent nodes point 11 to and not just copy the address that they 10 point to (which is the default behavior 9 of the implementations provided by the compiler) - and 8 the default destructor does not ever delete 7 dynamically allocated memory - which is 6 why you need to define a destructor that 5 does.

Here is a reasonable implementation 4 that you can play with - but more importantly, contrast 3 it with an approach (included at the end) that 2 uses vector and does not have to deal at 1 all with explicit memory management:

    
class Stack
{
  // a nested implementation class that the client needs to know nothing about
  struct Node
  {
     Node* prev;
     int value;
     Node(Node* prev, int value) : prev(prev), value(value) { }
     Node() : prev(0), value(0) { } 
     ~Node() { delete prev; }  // clean up after yourself

     // copy recursively until you hit a null pointer
     Node(const Node& o) : value(o.value), prev( prev ? new Node(*prev) : 0 ) { }
  };

  Node* head_;
  int size_;

public:  

  Stack() : head_(0), size_(0) { }
  ~Stack() { delete head_; }

  // copy recursively until null
  Stack(const Stack& o) : head_(o.head_ ? new Node(*o.head_) : 0) { }

  // use copy constructor to do assignment
  Stack& operator=(const Stack& o)
  {
    Stack copy(o);
    Node* cur = head_;

    head_ = copy.head_;
    size_ = copy.size_;

    copy.head_ = cur;  // copy's destructor will delete
    return *this;
  }

  void push(int value)
  {
    head_ = new Node(head_,value);
    ++size_;
  }
  int peek() const
  {
    if (!head_) throw "Attempting to peek off an empty stack!";
    return head_->value;
  }
  int pop()
  {
    if (!head_) throw "Attempting to pop off an empty stack!";
    int ret = head_->value;

    Node* cur = head_;    // hold on to it so we can delete it
    head_ = head_->prev;  // adjust my pointer
    cur->prev = 0;        // if this is not set to 0, all nodes will be deleted

    delete cur;
    --size_;
    return ret;
  }
  int size() const { return size_; }
};



// -- an easier way to write a stack of ints ;)
struct VecStack
{
    std::vector<int> vec;

    void push(int x)
    {
        vec.push_back(x);
    }
    int peek() const
    {
        if(vec.empty()) throw "Is Empty";
        return *--vec.end(); // you may prefer vec[vec.size() - 1];
    }
    int pop() 
    { 
        if (vec.empty()) throw "Is Empty";
        int ret = *--vec.end();
        vec.pop_back();
        return ret;
    }
    int size() const { return vec.size(); }
};

Score: 2

Here's a minor suggestion - this code:

Node* tempPtr = top;
top = new Node(value, tempPtr);

can 4 be replaced with

top = new Node(value, top); 

unless you wanted the extra 3 assignment statement to make the code more 2 clear. If that's the case you could do 1 this:

Node* oldTopPtr = top;
top = new Node(value, oldTopPtr);  
Score: 1

In case you want a slightly different approach, here's 19 how I'd (probably) do it. The main difference 18 is the copy-and-swap idiom for operator=, which 17 I don't think anyone else has mentioned, so 16 you might be interested to see. If jalf 15 is allowed to demand a copy constructor 14 and operator=, even though they aren't in 13 the original spec, then I'm allowed to demand 12 std::swap ;-)

This passes jalf's test code. And 11 for anyone who prefers dynamic to static 10 typing - the first version which compiled, passed 9 ;-).

I have used only limited RAII, because 8 as I mention in a comment on jalf's answer, I 7 don't want recursive con/destructors. There 6 are a few places which are "unsafe" in the 5 sense that certain lines of code must be 4 nothrow, and are. But the copy constructor 3 on SafeNode is exception-safe without having 2 to try-catch, so the part which actually 1 might throw is covered.

#include <stdexcept>
#include <algorithm>

class Stack {
    private:
    struct Node {
        Node *prev;
        int value;
        Node(int v, Node *p = 0): value(v), prev(p) { ++live; }
        ~Node() { --live; }
    };

    public:
    Stack() : top(0), size(0) { }
    Stack &operator=(const Stack &rhs) {
        if (this != &rhs) {
            Stack s(rhs);
            swap(s);
        }
        return *this;
    }

    public:
    void push(int value) {
        top.node = new Node(value, top.node);
        ++size;
    }

    int pop() {
        // get node and value at the top of the stack
        Node *thisnode = top.get();
        int retval = thisnode->value;

        // remove top node from the stack and delete it
        top.node = thisnode->prev;
        --size;
        delete thisnode;

        return retval;
    }

    int peek() const {
        return top.get()->value;
    }

    size_t getSize() {
        return size;
    }

    void swap(Stack &rhs) {
        top.swap(rhs.top);
        std::swap(size, rhs.size);
    }

    private:
    struct SafeNode {
        Node *node;
        SafeNode(Node *n) : node(n) {}
        SafeNode(const SafeNode &rhs_) : node(0) {
            const Node *rhs = rhs_.node;
            if (rhs == 0) return;
            SafeNode top(new Node(rhs->value));
            Node *thisnode = top.node;
            while(rhs = rhs->prev) {
                thisnode->prev = new Node(rhs->value);
                thisnode = thisnode->prev;
            }
            swap(top);
        }
        ~SafeNode() {
            while (node != 0) {
                Node *nextnode = node->prev;
                delete node;
                node = nextnode;
            }
        }
        void swap(SafeNode &rhs) { std::swap(node, rhs.node); }
        Node *get() const {
            if (node == 0) throw std::logic_error("Empty stack");
            return node;
        }
        private: SafeNode &operator=(const SafeNode &);
    };

    private:
    SafeNode top;
    size_t size;

};

namespace std {
    template <>
    void swap<Stack>(Stack &lhs, Stack &rhs) {
        lhs.swap(rhs);
    }
}
Score: 0

After learning some lessons from the answers, developing 5 a style of getter functions, making a proper 4 copy ctor and dtor, I think this latest 3 code is way better than my first attempt.

Here 2 is some less crappy, better memory managed 1 code:

/*stack class

Background: the specs for this are, verbatim: 

"Write a node-based stack class smile.gif

The stack is one of the most fundamental data structures used in computer science.

A stack has three basic operations:

push(value) - puts a value on the top of the stack
pop() - removes and returns the value that's on the top of the stack
peek() - return (but does not remove) the value off the top of the stack

Before creating the stack, you first have to create a Node class, which is a 
very basic class with just two member variables: the value of the node, and a 
pointer to the previous node in the stack.

Your stack should have only one member variable: the top node of the stack. 

ADDENDUM: also a size variable is allowed.

When you push, you add a node with the new value, with it's previous pointer 
pointing towards the current stack top item. When you pop, you delete the top 
node and then set the top of the stack to whatever that node's previous node 
pointer was.

push, pop, and peek must all run in constant time.

You should write it so that it can only push (and pop/peek) ints."
*/

#include <string>
#include <iostream>


class Stack
{
    private:
        struct Node
        {
            public:
               /* constructors and destructors */        
               Node(int value, Node* prev) : value_(value), prev_(prev) { }
               Node(Node const& other) { value_ = other.value_; prev_ = other.prev_; }
               //there is no ~Node, because the Stack does all the manual management

            /* private data members */
            private:
               /* the value of the node */
               int value_;
               /* a pointer to the previous node on the stack */
               Node* prev_;

            /* getter functions */
            public:
               int value() { return value_; }
               Node* prev() { return prev_; }
        };

    public:
        /* constructors and destructors */
        Stack() : size_(0), top_(0) { }
        ~Stack();     


    private:
        /* pointer to the very top node; important to LIFO phil */
        Node* top_;
        /* size of the stack (main value is whether stack is empty */
        int size_;

    public: 
        //not for public use
        void setTop(Node *top) { top_  = top;  }
        void setSize(int size) { size_ = size; }
        Node* top() { return top_;  }
        int size()  { return size_; }


    public:
        /* insertion, deletion, and traversal functions */
        void push(int);
        int pop();
        int peek();
};

Stack::~Stack() 
{ 
    while (top() != NULL)
    { 
        Node* tempPtr = top()->prev();
        delete top_;
        setTop(tempPtr);
    }
} 

void Stack::push(int value)
{ 
    setSize(size() + 1);
    Node *newTop = new Node(value, top());
    setTop(newTop);
}

int Stack::peek()
{
    return top()->value();
}


int Stack::pop()
{    
    if (size() == 0)
    {
        throw; //up
    }

    setSize(size() - 1);

    Node* tempPtr = top()->prev();
    int tempVal = top()->value();
    delete top();
    setTop(tempPtr);

    return tempVal;    
}
Score: 0
  • push(value) - puts a value on the top of the stack
  • pop() - removes and returns the value that's on the top of the stack
  • peek() - return (but does not remove) the value off the top of the stack

0

More Related questions