Linked List - Stack

Mar 23, 2012 at 12:49am
Maese909 (131)
Hey, I am testing a stack implemented as a linked list built backwards and for some reason, my program is outputting 
12 11
when it should be outputting 
11 12

I traced the program and got 11 12 so I am not sure what is wrong.
Anyway, here is the stack class (work in progress):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
 
#ifndef STACK_H_INCLUDED
#define STACK_H_INCLUDED
#include "node.h"

template <class Type>
class stack
{
public:
    void push(Type element);
    Type pop();
    bool empty() const;
    stack();

private:
    node<Type> *first;
};

template <class Type>
void stack<Type>::push(Type element)
{
    node<Type> *newNode;

    newNode = new node<Type>;
    newNode->info = element;
    newNode->link = first;
    first = newNode;
}

template <class Type>
Type stack<Type>::pop()
{
    node<Type> *current = first;
    Type element = current->info;

    first = first->link;
    delete current;

    return element;
}

template <class Type>
bool stack<Type>::empty() const
{
    return first == NULL;
}

template <class Type>
stack<Type>::stack()
{
    first = NULL;
}

#endif // STACK_H_INCLUDED


and the node header file:
1
2
3
4
5
6
7
8
9
10
11
 
#ifndef NODE_H_INCLUDED
#define NODE_H_INCLUDED

template <class Type>
struct node
{
    Type info;
    node *link;
};

#endif // NODE_H_INCLUDED


and finally main():
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 
#include <iostream>
#include "stack.h"

using namespace std;

int main()
{
    stack<int> stack;

    stack.push(12);
    stack.push(11);

    cout << stack.pop() << " " << stack.pop() << endl;

    return 0;
}
Edit & run on cpp.sh

Mar 23, 2012 at 1:56am
Pravesh Koirala (267)
Well, I tried it on my system and as you said, the o/p was wrong. So I too traced your program and turns out the code is right, but this printing part was the culprit
cout << stack.pop() << " " << stack.pop() << endl;

and so, I modified it too
1
2
3
 
    
cout << stack.pop() << " ";
   cout << stack.pop() << " ";


And now the program runs just fine. Now as for why it happened, I wrote a small program quickly. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
 
const char* Foo()
{
    static bool FirstTime = true;
    if (FirstTime)
    {
        FirstTime = false;
        return "This is First Time\n";
    }
    else
    {
        return "This is second time\n";
    }
}

int main()
{

    cout << Foo() <<Foo() << endl;
    return 0;
}


Expecting its output to be

This is first time
This is second time

But instead what it gave is, Bingo!

This is second time
This is first time


Turns out, the second function (in the bold) gets executed first. Wow!
Last edited on Mar 23, 2012 at 2:00am
Mar 23, 2012 at 4:04am
Maese909 (131)
Whoa. That's weird... I don't recall ever running into that before :p
Topic archived. No new replies allowed.