Single Linked List Question

[eggsandbacon]

Hey everyone,

I'm writing a program that uses a single-linked list and I'm running into two hiccups that I can't figure out. The first is that my pop() method pops from the bottom of the stack and not the top. The second is that when I copy stack, they are copied backwards. Anyone have any idea why this is occuring?

#ifndef STACK_H
#define STACK_H
#include <iostream>
#include <stdexcept>

using namespace std;
using std::ostream;

template <class T>
struct SNode
       {
            T value;
            SNode<T> *next;
            
//Constructor, copies argument into stack node and sets node's pointer to NULL
            SNode(T newData)
            {
                        value = newData;
                        next = NULL;
            }
       };
       
// Forward declaration of the Stack template class
template <class T> 
class Stack;

// Forward declaration of the operator<< template function
template <class T>
std::ostream& operator<<(std::ostream &os,const Stack<T>&st);

template <class T>
class Stack
{
      private:
             SNode<T>* head;
             void copyList(const Stack<T>&);
      public:
     	     friend std::ostream& operator<< <>(std::ostream&, const Stack<T>&);
             Stack();
             ~Stack();
             Stack(const Stack<T> & q);
             Stack<T>& operator=(const Stack<T>&); 
             int size() const;
             int top() const;
             bool empty() const;
             void push(T newValue);
             void pop();
             void clear();
             
};

// Method definitions for the Stack class


/****************************************************************
   FUNCTION:   Stack()
   ARGUMENTS:  none
   RETURNS:    nothing
   NOTES:      Default contructor that takes no arguments. The constructor
               sets head to NULL.
****************************************************************/
template <class T>
Stack<T>::Stack()
{
         head = NULL;
}

/****************************************************************
   FUNCTION:   ~Stack()
   ARGUMENTS:  none
   RETURNS:    nothing
   NOTES:      Destructor. Simply calls the clear() method..
****************************************************************/
template <class T>
Stack<T>::~Stack()
{
       clear();
}

/****************************************************************
   FUNCTION:   copyList()
   ARGUMENTS:  template parameter
   RETURNS:    nothing
   NOTES:      Copy method used in = operator and copy constructor.
               Copies one object to another.
****************************************************************/
template <class T>
void Stack<T>::copyList(const Stack<T>& listToCopy)
   {
   SNode<T>* p;
   
   for (p = listToCopy.head; p != NULL; p = p->next)
      push(p->value);
   }
/****************************************************************
   FUNCTION:   Stack(const Stack<T>& g)
   ARGUMENTS:  Template parameter
   RETURNS:    nothing
   NOTES:      Copy constructor.
****************************************************************/
template <class T>
Stack<T>::Stack(const Stack<T> & q)
{                     

                    head = NULL;
                    copyList(q);
}

/****************************************************************
   FUNCTION:   Stack<T>& operator=(const Stack<T>& s)
   ARGUMENTS:  ?
   RETURNS:    ?
   NOTES:      The assignment operator should be properly overloaded
****************************************************************/
template <class T>
Stack<T>& Stack<T>::operator=(const Stack<T>& rightOp)
{
   if (this != &rightOp)
      {
      clear();
      copyList(rightOp);
      }
         
   return *this; 
}


/****************************************************************
   FUNCTION:   overloaded << operator
   ARGUMENTS:  ?
   RETURNS:    ?
   NOTES:      The output operator should be properly overloaded.
****************************************************************/
template <class T>
ostream& operator<<(ostream& leftOp, const Stack<T>& rightOp)
{
SNode<T>* ptr = rightOp.head;
while (ptr)
{
    leftOp << ptr->value << " ";
    ptr = ptr -> next;
}
return leftOp;
}

/****************************************************************
   FUNCTION:   size()
   ARGUMENTS:  none
   RETURNS:    an integer
   NOTES:      Returns the current size of the stack (the number of data
               items currently stored in the stack. Traverses the linked
               list and counts the nodes.
****************************************************************/
template <class T>
int Stack<T>::size() const
{
    int count = 0;
    for (SNode<T>* ptr = head; ptr != NULL; ptr = ptr->next)
    count++;
    
    return count;
}

/****************************************************************
   FUNCTION:   top()
   ARGUMENTS:  none
   RETURNS:    an integer
   NOTES:      Returns the data stored in the top node of the stack (the
               front node in the linked list). Assume this method will
               not be called if the stack is empty.
****************************************************************/
template <class T>
int Stack<T>::top() const
{
    T final;
    SNode<T>* nodePtr = head;
    while(nodePtr != NULL)
                  {
                  final = nodePtr->value;
                  nodePtr = nodePtr->next;
                  };
    return final;
         
}

/****************************************************************
   FUNCTION:   empty()
   ARGUMENTS:  none
   RETURNS:    nothing
   NOTES:      Returns true if there are no data items currently stored in
               the stack, otherwise returns false.
****************************************************************/
template <class T>
bool Stack<T>::empty() const
{
     if(head == NULL)
     return true;
     
     else 
     return false;
}

/****************************************************************
   FUNCTION:   push(T newValue)
   ARGUMENTS:  Reference to a constant item of the template parameter type?
   RETURNS:    nothing
   NOTES:      Inserts the item at the top[ of the stack (the front of the 
               linked list.
****************************************************************/
template <class T>
void Stack<T>::push(T newValue)
{
     SNode<T> * newNode = new SNode<T>(newValue);    
     newNode->next = head;
     head = newNode;
}

/****************************************************************
   FUNCTION:   pop()
   ARGUMENTS:  none
   RETURNS:    nothing
   NOTES:      Removes the node at the top of the stack. Assumes that 
               this method will not be called if the stack is empty.
****************************************************************/
template <class T>
void Stack<T>::pop()
{
    SNode<T>* delNode = head;
    if (!empty())
    {
       head = delNode -> next;
       delete delNode;
}
}

/****************************************************************
   FUNCTION:   clear()
   ARGUMENTS:  none
   RETURNS:    nothing
   NOTES:      Properly set the stack back to the empty state. Delete
               all of the nodes in the stack and set the top pointer 
               back to NULL.
****************************************************************/
template <class T>
void Stack<T>::clear()
{
     while (!empty())
     {
           pop();
           }
           head = NULL;
}

#endif 

[Zhuge]

Your top() method seems to indicate that the top of your stack is the last node in the list. But the pop() method deletes the first node in the list, which is the bottom of your stack.

Your copy() method goes the the internal list of the second stack (which, from before, is in reverse order compared to the stack it represents), but instead of appending to the internal list of the first stack, it pushes on the first stack (which prepends to the internal list). Does that make sense?

[eggsandbacon]

I understand what you mean about the pop() method, but I'm not sure exactly how to implement it. How do I go about about removing the top of my stack instead of the bottom? I just can't figure out the logic to do it.

Your explanation of the copy method just went right over my head. I'm not quite sure what you meant by it, what internal list of the second stack? Could you rephrase it in easier terms?

Thanks for your help.

[Zhuge]

Instead of setting the head of the list to head->next and then deleting the old head, iterate to the end of the list, set prev->next to NULL (making it the new end) and delete the old end.

I apologize, I made a mistake analyzing your copy() method. The algorithm there is fine; the problem likes in push().

In your implementation, the head of the list is the bottom of the stack, and the end of the list is the top of the stack.

In push(), however, you place the inserted element at the head of the list (the bottom of the stack). This is the opposite of the behavior you want, I think.

[eggsandbacon]

Well with a stack I can only access the top element of the stack, so the top element must be copied first (right?). When I push it into a new stack, it is automatically on the bottom (since there is nothing in the stack). How can I possibly copy it so it is not reversed? Can I used recursion in the copylist() method to copy it again and reverse it again into proper order?

I really just don't even know how to implement this at all. If you could provide code to demonstrate your explanation it would make it much easier.

Thanks for your help again, Zhuge.

[Zhuge]

Well with a stack I can only access the top element of the stack, so the top element must be copied first (right?).

This is correct, but you forget that in your copy function, you're copying from the internal list structure, which gives you access from the head (stack bottom) to end (stack top).

When I push it into a new stack, it is automatically on the bottom (since there is nothing in the stack).

This is correct as well, but you shouldn't think of it this way. When you push() you place things on the top of the stack; this first push() is just a special case where the top and the bottom are the same element.

How can I possibly copy it so it is not reversed?

When doing the copy, remember you have access to your underlying list that is being using for your stack. The process is just to copy one linked list to the other; start at the head of one, and keep appending each successive element to the list.

I don't really want to give you code here because I think it's important you understand the algorithm you need to implement and why that algorithm works.