Implementing Push function in Queue

Question

I'm not entirely sure where I'm going wrong here but I keep getting weird values for Push. I don't know if my error is in Push itself or in the Display, but I assume it is in Push. Note that Push here is supposed to be similar to "std::deque::push_back".

Here is the related implementation code:

fsu::Queue <char> q;
q.Push('a');
q.Display(std::cout, '\0');

Here is what I get:

0x100100a20
0x100100a20
0x0

Related definitions:

void      Push    (const T& t); // push t onto queue
void      Display (std::ostream& os, char ofc = '\0') const; // output contents
                                    //through os
queue             ();              // default constructor
Queue             (const Queue&);  // copy constructor
~Queue            ();              // destructor
Queue& operator = (const Queue&);  // assignment operator

private:
    class Link
    {
        Link ( const T& t );  // 1-parameter constructor
        T      element_;
        Link * nextLink_;
        friend class Queue<T>;
    };
Link * firstLink_;
Link * lastLink_;

void         Copy   (const Queue<T>& q);
static Link* NewLink(const T& t);

And here is what I have to for the implementation:

template < typename T >
fsu::Queue<T>::Queue () : firstLink_(0), lastLink_(0)              // default constructor
{
  //empty
}

template < typename T >
fsu::Queue<T>::Queue (const Queue& q) : firstLink_(0), lastLink_(0)
{
  Copy(q);
}

template < typename T >
fsu::Queue<T>& fsu::Queue<T>::operator = (const Queue& q) // assignment operator
{
  if (this != &q)
  {
    Clear();
    Copy(q);
  }
  return *this;
}

template < typename T >
fsu::Queue<T>::Link::Link ( const T& t ) : element_(t), nextLink_(0)  // 1-parameter     constructor
{
};

template < typename T >
typename fsu::Queue<T>::Link* fsu::Queue<T>::NewLink (const T& t)
{
  Link * newLink = new(std::nothrow) Link (t);
  if (0 == newLink)
  {
    // exception handler
    std::cerr << "** Queue error: memory allocation failure\n";
    return 0;
  }
  return newLink;
}

template < typename T >
void fsu::Queue<T>::Copy (const Queue<T>& q)
{
  if (firstLink_ != 0)
  {
    std::cerr << "** Error: Queue::Copy called by non-empty object\n";
    //  exit(EXIT_FAILURE);
  }
  if (q.firstLink_ == 0)
    return;
  Link* qlink = q.firstLink_;
  while (qlink != 0)
  {
    Push(qlink -> element_);
    qlink = qlink -> nextLink_;
  }
  }

template < typename T >
void fsu::Queue<T>::Push (const T& t) // push t onto queue
{
if (Empty())
{
    Link * newLink = new Link(t);
    newLink -> nextLink_ = NULL;
    firstLink_ = newLink;
    lastLink_ = newLink;
}
else
{
    //to be implemented
}
}

template < typename T >
void fsu::Queue<T>::Display (std::ostream& os, char ofc) const // output contents
// through os
{
  os << firstLink_ << std::endl;
  os << lastLink_ << std::endl;
  Link * currLink = firstLink_;
  while (currLink)
  {
    currLink = currLink -> nextLink_;
    os << currLink << std::endl;
  }
 }

In the function Display, is that you want to print out the pointer address, instead of its value? — Daniel
– Daniel, Commented Dec 6, 2013 at 8:33
I am trying to print the value, but the ostream is apparently not accepting my type when I try dereferencing the pointers? — RandomPleb
– RandomPleb, Commented Dec 6, 2013 at 8:54
It tries to print a Link object when you dereference the pointer, define an overload operator >> for the Link class (specify what you want to print out). — Daniel
– Daniel, Commented Dec 6, 2013 at 8:56

JohnB · Accepted Answer · 2013-12-06 09:14:35Z

1

  os << firstLink_ << std::endl;
  os << lastLink_ << std::endl;

Prints the addresses pointed to (i.e. the value the variable carries) rather than the item pointed to.

You must dereference the pointers! And then you get a Link structure, and from that you have to select the _element member, which you want to print:

  os << (*firstLink_)._element << std::endl;
  os << (*lastLink_).element << std::endl;

shorter and more common:

  os << firstLink_->_element << std::endl;
  os << lastLink_->_element << std::endl;

The need to explicitly dereference is a difference to, e.g. Java and C#, where references are "hidden" from the programmer and dealt with by the language. In C and C++, a pointer variable simply holds a memory address. You can manipulate memory addresses directly (google for "pointer arithmetic"); hence it is necessary to distinguish the pointer value (i.e. the address) from the value pointed to, which is located at this address.

Hope this is not too confusing.

edited Dec 6, 2013 at 9:14

answered Dec 6, 2013 at 8:33

JohnB

13.8k6 gold badges42 silver badges67 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

RichardPlunkett Over a year ago

same in os << currLink << std::endl;

RandomPleb Over a year ago

@JohnB I tried this but I get "invalid operands to binary expression ('std::ostream' and 'fsu::Queue<char>::Link')" p.s. Not confusing at all by the way.

JohnB Over a year ago

Oh, sorry, your Link is a structure containing an _element. So you must first dereference the Link pointer to get to the structure and then select the member, i.e. os << (*firstLink_)._element, or, shorter, os << firstLink_->_element.

RandomPleb Over a year ago

element_! I tried like every variation of "firstLink_ ->" besides that one. It's so obvious now. Thank you! You are a godsend!

Collectives™ on Stack Overflow

Implementing Push function in Queue

1 Answer 1

4 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

4 Comments

Your Answer

Sign up or log in

Post as a guest

Related