Re: [newbie] stack with templates

From: B. v Ingen Schenau (bart_at_ingen.ddns.info)
Date: 06/12/04


Date: Sat, 12 Jun 2004 11:52:10 +0200

Helder Inacio wrote:

> Hi. I am trying to learn C++. I think
> i know C pretty well.
>
> I tried to write o test program to implement
> a simple stack using some of the new features
> in C++.
> The test program is the following :
>
> $$$$$$$$$$ stack2.cc $$$$$$$$$$$$$$$$$
> // i'm tring to do the classic stack example, using classes
>
> #include <iostream>
>
> // try to define a stack using templates
> // and a linked list
>
> template <class TYPE>
> class Stack {
> public :
> Stack(void); // Constructor : create the empty stack
> ~Stack(void); // Destructor : Free the space used by the Stack

If you need a destructor in your class, you generally also need a
copy-constructor and copy-assignment operator, because the ones generated
by the compiler will not do the proper thing.
  Stack(const Stack&); // Copy-constructor
  Stack& operator=(const Stack&); // Copy-assignment operator

> void Push(const TYPE Elem); // push elem into the stack

You might want to make this:
  void Push(const TYPE& Elem); /* Pass Elem by reference instead of by value
*/
That would save you a copy, which could be costly if TYPE == vector<string>
for example.

> TYPE Pop(void); // pop an element
> bool Full(void); // check if the stack is full

In a typical stack implementation, there is no way to query if the stack is
full, because that happens very rarely, but there is a member to query if
the stack is empty.

> private :
> int n_elems; // number of elements in the stack
> class node {
> TYPE elem;
> class node * prox;
> };
This class node is completely useless, because it does not have any public
members, and thus after you have created an object of class node, you can't
do anything with it because you don't have access to the internals.
Change the declaration to 'struct node', and you have access to the
internals.

In C++, the only difference between class and struct are the default access
rights for members and base classes/structs.
Unless explicitly specified otherwise, C++ marks all members/bases of a
class as private, and all members/bases of a struct as public.

> typedef class node * Node;

Please do not hide pointers behind a typedef. There is no gain in clarity.
On the contrary, it makes the code harder to read, especially for the more
experienced programmers, because the declaration and use of a variable seem
to have a mismatch.

> Node root;
> }; // class Stack
>
> template <class TYPE>
> Stack<TYPE>::Stack(void) {
> root = 0; // initialize the pointer to null
> n_elems = 0;
> } // Stack()
>
> template <class TYPE>
> void Stack<TYPE>::Push(const TYPE Elem) {
If you want to pass by reference, this becomes:
  void Stack<TYPE>::Push(const TYPE& Elem) {
> if (root == 0) { // empty list
> root = new class node;

You don't have to use the keyword class here.
Unlike C, in C++ you can write code like this:

struct node {
  // some members
};

node Node_var; // Create a variable of the type 'struct node'.

> root->elem = Elem;
> root->prox = 0;
> n_elems = 1;
> }
> else {
> Node paux = root;
> Node new_node;
> while (paux->prox != 0) {
> paux = paux -> prox;
> }
> new_node = new class node;
> new_node->elem = Elem;
> new_node->prox = 0;
> n_elems++;
> paux->prox = new_node;

Note: This seems to me the kind of algorithm to push an element to a queue
(FIFO), not for a stack (LIFO).

> }
> } // Stack<TYPE>::Push
>
> template <class TYPE>
> bool Stack<TYPE>::Full(void) {
>
> return false; // the stack never overflows :)
> } // Stack Full
>
> template <class TYPE>
> Stack<TYPE>::~Stack(void) {
> // put here code for cleaning the stack
> }
>
> int main(void) {
>
> Stack<int> s_i();
> Stack<char> s_c();

These two line do not what you think they do.
Interestingly enough, they tell the compiler that there will be, somewhere,
a function called s_i that takes no arguments and that returns a Stack<int>
object.
The same holds for the declaration of s_c.

To define an object of Stack<int> that is default-constructed you have to
leave out the parentheses:
  Stack<int> s_i;
  Stack<char> s_c;

>
> std::cout << "The Stack is Full == " << s_i.Full() << std::endl;
>
> std::cout << "this program is terminating...";
> std::cout << std::endl;
> return 0;
>
> } // end main
> $$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$
>
> When i try to compile it with (g++ linux) :
> c++ -g -Wall stack2.cc -o stack2
>
> i get the following error:
> stack2.cc: In function `int main()':
> stack2.cc:70: error: request for member `Full' in `s_i()', which is of
> non-aggregate type `Stack<int> ()()'

Here the compiler tries to tell you that the (pointer to) function 's_i'
does not have any members, and thus certainly not one called 'Full'.

> make: *** [stack2] Error 1
>
> Can someone figure out what i am doing wrong?
> The compiler wont complaint if i delete the line where
> the error is reported...
>
>
> Tkank you for any help that i may get.
>
Bart v Ingen Schenau

-- 
a.c.l.l.c-c++ FAQ: http://www.comeaucomputing.com/learn/faq
c.l.c FAQ: http://www.eskimo.com/~scs/C-faq/top.html
c.l.c++ FAQ: http://www.parashift.com/c++-faq-lite/


Relevant Pages

  • Re: better way to pass arguements to a function
    ... workthe members of the structure, ... // This will have three variables on the stack ... implementation very well and have good reason to worry. ... sample objects and you pass pointers to them around. ...
    (comp.lang.c)
  • Re: procedure parameter struct order
    ... the members of this struct would always have the same order on ... >> members in the order they are declared. ... Or if there even is a stack as such, ... > compiler would be quite correct if, behind the scenes, all it pushed on ...
    (comp.lang.c)
  • Re: procedure parameter struct order
    ... the members of this struct would always have the same order on ... > members in the order they are declared. ... not even know whether the arguments are passed on the stack in the first ... int heigth; ...
    (comp.lang.c)
  • ANN: mixfloat, rawfloat, hexfloat 0.9.0
    ... default floats on the floating-point stack. ... the raw formats to memory. ... The test program requires ttester.fs. ... sublibraries. ...
    (comp.lang.forth)
  • Re: Creating member vars on the heap, not the stack
    ... on the heap, not the stack. ... Other than declaring all the members of the class as static, ...
    (microsoft.public.vc.language)