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_;
-
}
-
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.
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 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.
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
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.
Sign in to post your reply or Sign up for a free account.
Similar topics
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,...
|
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...
|
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':...
|
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...
|
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...
|
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...
|
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...
|
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...
|
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...
|
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...
|
by: ryjfgjl |
last post by:
ExcelToDatabase: batch import excel into database automatically...
|
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...
|
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...
|
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)...
|
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...
|
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....
|
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
|
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...
| |