473,320 Members | 1,977 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,320 software developers and data experts.

Making a Queue

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?

Expand|Select|Wrap|Line Numbers
  1. template <typename T>
  2. class TQueue
  3. {
  4. public:
  5.   TQueue();
  6.   ~TQueue();
  7.   void     Push     (const T& t); //push t onto queue
  8.   T        Pop      ();           //pop queue and return removed element; error if empty
  9.   T&       Front    ();           //return front element of stack; error if empty
  10.   const T& Front    () const;     //const version
  11.   size_t   Size     () const;     //return number of elements in queue
  12.   int      Empty    () const;     //return 1 if queue is empty, 0 if not empty
  13.   void     Clear    ();           //make the queue empty
  14.   void     Display  (std::ostream& os, char ofc) const; //outputs contents through os
  15. private:
  16.   class Link
  17.   {
  18.     Link (const T& t) : element_(t), nextLink_(0) {}
  19.     T     element_;
  20.     Link * nextLink_;
  21.     friend class TQueue<T>;
  22.   };
  23.   Link * firstLink_;
  24.   Link * lastLink_;
  25. };
  26.  
  27. template <typename T>
  28. std::ostream& operator << (std::ostream& os, const TQueue<T>& S)
  29. {
  30.   S.Display(os, '\0');
  31.   return os;
  32. }
  33.  
  34. template <typename T>
  35. TQueue<T>::TQueue():firstLink_(0), lastLink_(0){;}
  36.  
  37. template <typename T>
  38. TQueue<T>::~TQueue()
  39. {
  40.   Clear();
  41. }
  42.  
  43. template <typename T>
  44. void TQueue<T>::Push(const T& t)
  45. {
  46.   Link * newLink = new Link (t);
  47.   if(firstLink_ == 0)
  48.   {
  49.     firstLink_ = lastLink_ = newLink;
  50.   }
  51.   else
  52.   {
  53.     lastLink_ -> nextLink_ = newLink;
  54.     lastLink_ = newLink;
  55.   }
  56. }
  57.  
  58. template <typename T>
  59. T TQueue<T>::Pop()
  60. {
  61.   firstLink_ = firstLink_ -> nextLink_;
  62.   if (firstLink_ == 0)
  63.     firstLink_ = lastLink_;
  64.   return firstLink_ -> element_;
  65.   delete firstLink_;
  66. }
  67.  
  68. template <typename T>
  69. T& TQueue<T>::Front()
  70. {
  71.   return firstLink_ -> element_; 
  72. }
  73.  
Jan 2 '10 #1
5 2790
Banfa
9,065 Expert Mod 8TB
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.
Jan 2 '10 #2
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
Jan 2 '10 #3
Banfa
9,065 Expert Mod 8TB
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.
Jan 3 '10 #4
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
Expand|Select|Wrap|Line Numbers
  1. std::cout << firstLink_ -> element_;
  2. do
  3. {
  4. std::cout << firstLink_ -> nextlink_;
  5. }
  6. while (firstLink_ -> nextLink_ != 0);
  7.  
It outputs the first element fine, then outputs garbage in an endless loop
Jan 3 '10 #5
weaknessforcats
9,208 Expert Mod 8TB
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.
Jan 3 '10 #6

Sign in to post your reply or Sign up for a free account.

Similar topics

9
by: phil | last post by:
And sorry I got ticked, frustrating week >And I could help more, being fairly experienced with >threading issues and race conditions and such, but >as I tried to indicate in the first place,...
2
by: lucifer | last post by:
hi i am making an http server it has following functions main() { if option is "-?", output the hints and stop check the directory supplied is sensible and not a security risk become a daemon...
3
by: Kceiw | last post by:
Dear all, When I use #include "queue.h", I can't link it. The error message follows: Linking... G:\Projects\Datastructure\Queue\Debug\main.o(.text+0x136): In function `main':...
4
by: rzimerman | last post by:
I'm hoping to write a program that will read any number of urls from stdin (1 per line), download them, and process them. So far my script (below) works well for small numbers of urls. However, it...
2
by: lavender | last post by:
When define a maxQueue is 10, means it able to store 10 items in circular queue,but when I key in the 10 items, it show "Queue Full" in items number 10. Where is the wrong in my code? Why it cannot...
3
by: jrpfinch | last post by:
I have a script which is based on the following code. Unfortunately, it only works on Python 2.3 and not 2.5 because there is no esema or fsema attribute in the 2.5 Queue. I am hunting through...
4
by: j_depp_99 | last post by:
Thanks to those guys who helped me out yesterday. I have one more problem; my print function for the queue program doesnt work and goes into an endless loop. Also I am unable to calculate the...
2
by: ecestd | last post by:
how do you implement a copy constructor for this pointer-based ADT queue #include <cassert // for assert #include <new // for bad_alloc using namespace std; //private:{Queue::Queue(const...
0
by: ecestd | last post by:
I did implement the copy constructor but still have a problem with it. It is not working. What could be wrong? #include "QueueP.h" #include <cassert // for assert #include <new // for...
0
by: DolphinDB | last post by:
Tired of spending countless mintues downsampling your data? Look no further! In this article, you’ll learn how to efficiently downsample 6.48 billion high-frequency records to 61 million...
0
by: ryjfgjl | last post by:
ExcelToDatabase: batch import excel into database automatically...
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: jfyes | last post by:
As a hardware engineer, after seeing that CEIWEI recently released a new tool for Modbus RTU Over TCP/UDP filtering and monitoring, I actively went to its official website to take a look. It turned...
1
by: PapaRatzi | last post by:
Hello, I am teaching myself MS Access forms design and Visual Basic. I've created a table to capture a list of Top 30 singles and forms to capture new entries. The final step is a form (unbound)...
0
by: CloudSolutions | last post by:
Introduction: For many beginners and individual users, requiring a credit card and email registration may pose a barrier when starting to use cloud servers. However, some cloud server providers now...
1
by: Shællîpôpï 09 | last post by:
If u are using a keypad phone, how do u turn on JavaScript, to access features like WhatsApp, Facebook, Instagram....
0
by: af34tf | last post by:
Hi Guys, I have a domain whose name is BytesLimited.com, and I want to sell it. Does anyone know about platforms that allow me to list my domain in auction for free. Thank you
0
by: Faith0G | last post by:
I am starting a new it consulting business and it's been a while since I setup a new website. Is wordpress still the best web based software for hosting a 5 page website? The webpages will be...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.