1
Posted March 5, 2011 by Spyros in C/C++ Programming
 
 

Explaining How Stacks Work in C++

stack
stack

Today i will talk more deeply about Stacks in C++. In the previous tutorial we just declared some methods of this class, so now let’s see their content and in future tutorials we will use Stacks in an application in C++. Let’s start with a look at the template of the class Stack one more time.

 

 

template< class T >
class Stack
{
    private:
        Node< T> *top;
        void destroyStack();
        const Stack< T>& reverse();
    public:
        Stack();
        Stack(const Stack< T>& s);
        virtual ~Stack();
        void push(const T &elem);
        void pop(T &x);
        const T& top() const;
        bool empty() const;
        int lenght() const;
        const Stack< T>& operator = (const Stack< T> &s);
        void write(ostream & ostr) const;
};

Now let’s see the content. First the constructors and the default constructor:

template < class T> Stack< T>::Stack() { top = NULL; }

Let’s now check the copy constructor. As we can see, it’s far more complex than the default constructor, but if you pay attention closely, its not much difficult to understand. What we see is just the copy from the content of the stack passed by reference in the “argument bar”, to another stack.

template < class T> Stack< T>::Stack(const Stack< T> &s)
{
    Node< T> * apnode = new Node< T>;
    if(s.top)
        top=apnode;
    else
        top=NULL;
    Node< T> *ap = s.top;
    while (ap != NULL) {
        apnode->info=ap->info;
        if(ap->next == NULL)
            apnode->next=NULL;
        else {
            apnode->next=new Node< T>;
            apnode=apnode->next;
        }
        ap=ap->next;
     }
}

Now, for the destructors. This one is not the typical destructor we normally see and you now why? Because this is not the “true” destructor”. This method is called by the real destructor (below). This one is just a safety method to ensure the clearance of the Stack, element by element in the top of the Stack.

template < class T>
void Stack< T>::destroyStack() {
    Node< T> * temp; while (top)
    {
        temp=top->next;
        delete top;
        top=temp;
    }
}

The real destructor (the one who calls the method above):

template < class T> Stack< T>::~Stack() { destroyStack(); }

The empty method returns a bool(True or False), which means that it tells us if a selected stack is empty or not.

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

This one is easy to judge by its name; it returns the length of a stack. It’s very useful when we use a for structure or other data structures.

template< class T>
    int Stack< T>::lenght() const
    {
        Node< T> *temp;
        int leng=0;
        temp=top;
        while (temp) {
            leng++;
            temp=temp->next;
        }
        return leng;
     }

Another easy and short implementation. It gives us the element in the top of the stack, which is the only possibility. As you remember, in Stacks, we just have access at the top element.

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

A method to pop out the element in the top of the stack. Of course, it just pops out if the stack isn’t empty. That’s what the if((empty()) is for.

template< class T>
    void Stack::pop(T & x)
    {
        if (!empty()) {
            x=top->info;
            Node< T>* temp;
            temp=top;
            top=top->next;
            delete temp ;
         }
     }

Push is the opposite of the Pop operation. It is there to insert an element in a stack and will stay in the top of the stack. Last in First Out (LIFO), remember?

template< class T>
    void Stack< T>::push(const T &elem)
    {
        Node< T>* apnode= new Node< T>;
        apnode->info=elem;
        apnode->next=top;
        top=apnode;
    }

Sometimes, it is useful to reverse the content of a stack. The element on the top should be in the bottom and the one in the bottom should be at the top, for easy access. That’s why we need this method, to reverse the stack. The stack is “destroyed/cleared” and through an auxiliary stack with the same content, we pass the elements to the empty stack (the one who was cleared). Since it’s a LIFO, the element on the top will now be on the bottom.

template< class T>
    const Stack< T>& Stack< T>::reverse()
    {
        Stack< T> aux(*this) ;
        T x ;
        destroyStack();
        while (!aux.empty()) {
            aux.pop(x) ;
            push(x) ;
        }
        return *this ;
     }

The attribution method is the one responsible to turn a stack to another one. Pay attention to the “aux.reverse()” line. It’s very important to ensure the elements will not be reversed. Remember again, it’s a LIFO structure. So, to make a “copy” stack we need to reverse the one that will be copied .

template < class T>
    const Stack< T>& Stack< T>::operator = (const Stack< T> & s) {
        Stack< T> aux(s) ;
        T item ;
        destroyStack();
        aux.reverse();
        while (!aux.empty()) {
            aux.pop(item) ;
            push(item) ;
        }
        return *this;
     }

Nothing special here. We do the writing to an ostream and write to it later.

template< class T>
    void Stack::write(ostream & ostr) const {
        Node< T>* temp=top;
        while (temp) {
            ostr << temp->info << " " ; temp=temp->next;
        }
    }

“Hey, this one is not in the class definition!” You’re right, but it’s not necessary. It calls the method above (write) to write the content, so that in the main class we just need to do this: <<”name_of_the_class’s_instance”. It’s another very important practice in C++ called “Operator Overloading”.

template< class T>
    ostream & operator << (ostream & ostr, const Stack< T> & s) {
        s.write(ostr);
        return ostr;
}

That’s all for today. Hope you like it. Next time we can maybe apply this class in a C++ Application.

This was a guest post, thank you !


Spyros