Making a Queue

[randysimes]

I have to make a queue utilizing a linked list for an assignment. When I Push() an item to the queue, and try to Pop() or return the Front() element, it says the queue is empty. When I Push() another element to the queue and Pop() or return the Front(), the first entered element is returned.
Say I enter 4 element and then Pop(), it pops elements 2, 3, 4 and then says the queue is empty.
Somewhere along the line I am missing a key line to ensure the queue can see only 1 element.
Also, how would I determine the Size() of the queue based on what I have to go by?

template <typename T>
class TQueue
{
public:
  TQueue();
  ~TQueue();
  void     Push     (const T& t); //push t onto queue
  T        Pop      ();           //pop queue and return removed element; error if empty
  T&       Front    ();           //return front element of stack; error if empty
  const T& Front    () const;     //const version
  size_t   Size     () const;     //return number of elements in queue
  int      Empty    () const;     //return 1 if queue is empty, 0 if not empty
  void     Clear    ();           //make the queue empty
  void     Display  (std::ostream& os, char ofc) const; //outputs contents through os
private:
  class Link
  {
    Link (const T& t) : element_(t), nextLink_(0) {}
    T     element_;
    Link * nextLink_;
    friend class TQueue<T>;
  };
  Link * firstLink_;
  Link * lastLink_;
};
 
template <typename T>
std::ostream& operator << (std::ostream& os, const TQueue<T>& S)
{
  S.Display(os, '\0');
  return os;
}
 
template <typename T>
TQueue<T>::TQueue():firstLink_(0), lastLink_(0){;}
 
template <typename T>
TQueue<T>::~TQueue()
{
  Clear();
}
 
template <typename T>
void TQueue<T>::Push(const T& t)
{
  Link * newLink = new Link (t);
  if(firstLink_ == 0)
  {
    firstLink_ = lastLink_ = newLink;
  }
  else
  {
    lastLink_ -> nextLink_ = newLink;
    lastLink_ = newLink;
  }
}
 
template <typename T>
T TQueue<T>::Pop()
{
  firstLink_ = firstLink_ -> nextLink_;
  if (firstLink_ == 0)
    firstLink_ = lastLink_;
  return firstLink_ -> element_;
  delete firstLink_;
}
 
template <typename T>
T& TQueue<T>::Front()
{
  return firstLink_ -> element_; 
}
 

[Banfa]

Your description of the problem must be wrong because Front has no way of "saying the queue is empty" as you have stated.

However your pop function is full of errors, very nearly one per line.

Line 61, the code immediately replaces the element that needs to be returned with the next element of the list. Following this line firstLink_ is not valid for the rest of the function to use.

Line 62 is fine

Line 63, a logic error if firstLink_ is 0 then the list is empty but instead of clearing the value of lastLink_ to the empty value (0) you copy lastLink_ to firstLink_ ensuring that they both point to deallocated memory (or would if your code properly de-allocated memory).

Line 64, the code returns before the function has correctly perform all its required operations, also it uses firstLink_ which no longer points to the correct element to return.

Line 65, this line is never executed so you never deallocate any memory and your queue leaks memory like a sieve.

[randysimes]

I should have explained a little better; I have a .cpp file which has a menu to do all of the functions of the queue. In Pop() & Front(), I first check if the queue is Empty() and if so, display "Queue is empty"

I am away from my computer at the moment so I will look at your suggestions later.
Thanks Banfa

[Banfa]

Well then there may be an error in your implementation of Empty() but that is hard to tell as you never posted the implementation of that method.

[randysimes]

There was an error in Empty that was corrected last night after I made changes to Pop. I realized that Empty was wrong when I couldn't Pop the first value because it said it was empty.
I am still having difficulty trying to display all the elements of the queue. I have

std::cout << firstLink_ -> element_;
do
{
std::cout << firstLink_ -> nextlink_;
}
while (firstLink_ -> nextLink_ != 0);
 

It outputs the first element fine, then outputs garbage in an endless loop

[weaknessforcats]

Where in this loop are you changing firstLink to nextLink to advance in the list?

Also, if firstLink is zero, your loop will crash. The -> requires a non-null LVAL.