C++

Forum

 
Linked stack question

vxk (147)
I was working on solving questions for the linked stack implementation for the first time and I am running into problems and feeling under-confident about the knowledge of c++.
The question was to implement a function named bottom() that returns the bottom most element of the stack.I am able to see get the bottom most element and display it ,but the print function :
1
2
 
template <class T>
void print(Stack<T>);

that was created before is not working as it was working before,where am I missing?

I am also not able to properly understand the copy constructor of this Stack implementation.Can someone shed a light on it ...

Header file :

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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
 

template <class T>
class Stack
{ public:
    Stack();
    Stack(const Stack&);
    ~Stack();
    Stack& operator=(const Stack&);
    int size() const;     // returns number of elements
    bool empty() const;   // returns true iff this is empty
    T& top() const;       // returns the top element
    void push(const T&);  // inserts given element on top
    void pop();           // removes element from top
    
    T& bottom();
    
    
  protected:
    class Node
    { public:
        Node(const T& data, Node* next=0) : _data(data), _next(next) { }
        T _data;
        Node* _next;
    };
    Node* _top;
    int _size;
};

template <class T>
Stack<T>::Stack() : _top(0), _size(0)
{ 
}

template <class T>
Stack<T>::Stack(const Stack& s) : _top(0), _size(s._size)
{ if (_size==0) return;
  Node* pp=0;
  for (Node* p=s._top; p; p = p->_next)
    if (p==s._top) pp = _top = new Node(p->_data);
    else pp = pp->_next = new Node(p->_data);
}

template <class T>
Stack<T>::~Stack()
{ while (_top)
  { Node* p=_top;
    _top = _top->_next;
    delete p;
  }
}

template <class T>
int Stack<T>::size() const
{ return _size;
}

template <class T>
bool Stack<T>::empty() const
{ return _size == 0;
}

template <class T>
T& Stack<T>::top() const
{ return _top->_data;
}

template <class T>
void Stack<T>::pop()
{ Node* p=_top;
  _top = _top->_next;
  delete p;
  --_size;
}

template <class T>
void Stack<T>::push(const T& x)
{ if (_size==0) _top = new Node(x);
  else _top = new Node(x,_top);
  ++_size;
}


class stack : public Stack<char> {
public:
    char& bottom();
    
};
template<class T>
T& Stack<T>::bottom() {
    
    while(Stack<T>::size() != 1)  {
        Stack<T>::top();
        Stack<T>::pop();
    }

    return _top->_data;

}


The cpp file :

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
 

#include <iostream>
#include "Stack.h"
#include <string.h>


template <class T>
void print(Stack<T>);

int main(){
    Stack<std::string> s;
    
    s.push("first");     print(s);

    s.push("second")    ;     print(s);

    s.push("third")   ;     print(s);

    s.pop();     print(s);

    s.pop();        print(s);

    std::cout<<std::endl;
    
    
}


template<class T>
void print(Stack<T> s)
{
    std::cout<<"size= "<<s.size()<<std::endl;
   // std::cout<<"bottom= "<<s.bottom()<<std::endl;
    
    while (s.size()>0) {
        std::cout<< s.top()<<" ("<<s.top()<<", ";
        s.pop();
        
        while(!s.empty()){
            std::cout<< s.top()<<", ";
            s.pop();
        }
        
         std::cout<<" )"<<std::endl;
    }
}


Thanks !
Last edited on
JLBorges (13770)
> that was created before is not working as it was working before,where am I missing?

It seems to be working. Where is the problem?
http://coliru.stacked-crooked.com/a/6f2e761347bc8782

> copy constructor of this Stack implementation.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 
template <class T>
Stack<T>::Stack(const Stack& s) : _top(0), _size(s._size)
// initialise _top to a nullptr, _size to the size of the stack being copied
{ 
    if (_size==0) return; // empty; nothing more to be done

    Node* pp = 0; 
    
    for (Node* p=s._top; p; p = p->_next) // for each node in stack s
    {
            // special case for the very first node; 
            // this node becomes the _top of our stack
            if (p==s._top) pp = _top = new Node(p->_data);
            
            // not the first node; add this as the next node to pp, and bump pp
            else 
           {
                    pp->_next = new Node(p->_data);
                    pp = pp->next ;
           }
    }
}
vxk (147)
oh i forgot to remove the comment on line 33! on removing it only the first element is printed at all times, but the size of the stack is incremented .

http://coliru.stacked-crooked.com/a/fe623bd7504853c2
Last edited on
JLBorges (13770)
The current implementation of bottom() removes items from the stack.

1
2
3
4
5
6
7
8
9
10
11
12
13
 
template<class T>
T& Stack<T>::bottom()
{

    while( Stack<T>::size() != 1 )
    {
        Stack<T>::top();
        Stack<T>::pop(); // *** removes items from the stack
    }

    return _top->_data;

}


It should not modify the stack in any way.

1
2
3
4
5
6
7
8
9
10
11
12
 
template <class T>
class Stack
{
    public:

    // ...

    // T& bottom();
    const T& bottom() const ; // bottom of the stack is not modifiable
    
    // ...
};


1
2
3
4
5
6
7
 
template < typename T > 
const T& Stack<T>::bottom() const // invariant: !empty()
{
    auto n = _top ;
    for( int i = 1 ; i < size() ; ++i ) n = n->_next ;
    return n->_data ;
}

http://coliru.stacked-crooked.com/a/afb9301aa8c828b2
Topic archived. No new replies allowed.