Creating Your Own Library of Data Structures

[mlholder]

Hi all,

I am trying to implement a few of the basic data structures such as stack, queue, deque, singly/double linked lists. I would like to make these structures templated. For example,

template <typename T>
class Stack
{
   public:
      //member functions
   private:
      struct Node
      {

      };
};

I plan on creating each data structure in its own header file and implementing the member functions in the header file itself, because of the template. However, I would like to use class Node instead of a struct. Also, if I use a class Node for the underlying implementation, I would like to be able to place class Node outside of the declaration of class Stack. For example,

Stack.h

#ifndef STACK_H
#define STACK_H

class Node
{
    public:
        //member functions
    private:
        //member variables
};

class Stack
{
    public:
        //member functions for class Stack
        //Node* search(T item);
    private:
        Node *top;
};
#endif 

The main questions I have are:
1. Should I just use a struct and keep the code fairly straightforward instead of having class Node on its own?

2. If I use a a class for the Nodes, should I place the declaration inside of class Stack or can I place it outside of class Stack? If I place it outside of class Stack, can a user of the class Stack gain access to the private data by creating an instance of the Node class and modify the class Stack. One example I can think of is

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

int main()
{
    Stack<int> stack;

    for(int i = 1; i <= 10; i++)
        stack.push(i);

    Node *position;
    position = search(5);
    position->data += 5;

    //Or something to this effect...
}

Can someone point me in the right direction as to how to go about this. I am sure that I will have further questions, however, these are the main ones for now. I would like to be able to search the list, however, I do not want to give a user of the class the ability to modify the data of the Stack class. Any and all help is greatly appreciated. Thank you for your time.

[jlb]

1. Should I just use a struct and keep the code fairly straightforward instead of having class Node on its own?

In C++ there is really not much difference between a class and a struct, other than the default access specifiers.

2. If I use a a class for the Nodes, should I place the declaration inside of class Stack or can I place it outside of class Stack?

This is really a design question, either will work. But remember if you place the declaration of Node inside of your Stack class only the Stack class will be able to use the code. If the Node is declared outside the Stack class you can reuse the code in your other classes.

If I place it outside of class Stack, can a user of the class Stack gain access to the private data by creating an instance of the Node class and modify the class Stack.

This depends on how you declared the Node instance in your Stack class. If you declare the Node instance in the private section of the Stack class then only that Stack instance can access the Node instance. But if you declare the Node in the global section of the Stack class then the Node can be accessed outside of the Stack class.

In your example that Node instance has nothing to do with the Node instance that is contained within the class.

Since you seem to be trying to use a pointer to your Node you need to be very careful about how you handle your Node class. Don't pass the pointer out of your Stack class unless it is const qualified. Passing a pointer to a non-class variable will allow modification of the item pointed to outside of the class.

By the way I recommend you get your classes working for one type of variable before you add the complexity of templates. Once you get the class working for one type of variable it should be fairly easy to template the class.

I would like to be able to search the list

Normally when dealing with stacks and queues you only access the "top" or "bottom" elements depending on the type of data structure. Normally these data structures don't have the ability to search the list. And both stacks and queues can be implemented with vectors/arrays instead of a list.

I do not want to give a user of the class the ability to modify the data of the Stack class

If the user of the Stack class can't modify the data what is the purpose of the container?

[mlholder]

Thank you for the quick response jlb. My main concern for not being able to modify the contents of the stack is that I don't want someone to be able to go to the bottom of the stack and change the value located there, since technically I should only be able to modify the top of the stack. My thoughts were that someone could make an instance of Node in the main function, traverse down to some location in the stack and change a value if they so desired. From your recommendations and my understanding I should do something like the following

Version 1: Stack.h

#ifndef STACK_H
#define STACK_H

template <typename T>
class Node
{
    public:
        Node();
        Node(T newItem, Node *newLink);
        T getData() const;
        Node* getLink() const;
        void setData(T newItem);
        void setLink(Node *newLink);
    private:
        T item;
        Node *link;
};

template <typename T>
class Stack
{
    public:
        Stack();
        ~Stack();
        bool empty() const;
        T& top();
        void pop();
        void push(T newItem);
    private:
        Node *top;
};

//Definitions will go here
#endif 

Version 2: Stack.h

#ifndef STACK_H
#define STACK_H
 
template <typename T>
class Stack
{
    public:
        Stack();
        ~Stack();
        bool empty() const;
        T& top();
        void pop();
        void push(T newItem);
    private:
        class Node
        {
             //Same as declared in Version 1
        };

        Node *top;
};

//Definitions will go here
#endif 

If I understand correctly, by using Version 1, a user of Stack will not be able to traverse through a Stack object and modify the data. However, they should be able to modify the top of the stack. Could you go into more detail about what you meant by "Don't pass the pointer out of your Stack class unless it is const qualified"? Again, thank you for your time and help.

[jlb]

However, they should be able to modify the top of the stack.

Why should the be able to modify the top of the stack? The only thing they should be able to do is push an item into the stack, pop the last item from the stack, and get the value of the top item of the stack, you may also want to provide a method to determine the number of elements in your stack.

Could you go into more detail about what you meant by "Don't pass the pointer out of your Stack class unless it is const qualified"?

If you pass a pointer to the user the user now has the address of the item in memory. If not const qualified the user can modify this memory any time the so desire.