0

I have created this program for priority queue and I am having a problem. I am getting the wrong output.

Here is the input:

Insert 10000 2
Insert 10000 2
Insert 10000 3
Insert 19444 9
Pop
Insert 10331 3
Pop
Pop
Pop
Pop
Pop

Here's what the output should be:

19444
10000
10331
10000
10000
-1

Here's the output which I get:

19444
10000
10000
10000
10331
-1

SOLVED !

idanyal
  • 13
  • 4
  • You need to be a lot more specific about what behavior you're expecting. You call it a queue, but you seem to want stack semantics (especially due to use of "Pop" and having some global(?) called stacktopPop). – Tibrogargan Mar 20 '16 at 21:26
  • When the user enters Insert num priority (e.g. Insert 10000 3) it will be placed in the queue with priority 3. When Pop is typed and the user presses enter it will output the item being removed from the queue and remove it. – idanyal Mar 20 '16 at 21:34
  • You don't update stacktopPop when the queue is non-empty (your else clause) but an item with a priority larger than anything else in the queue is inserted. Inserted item should be the new stacktopPop when this happens. – Tugrul Ates Mar 20 '16 at 21:51
  • @idanyal: can you accept one of the answers by clicking on the grey check mark below the answer score? – chqrlie Mar 20 '16 at 22:19

2 Answers2

0

I believe your priority checking logic is incorrect:

while (queue->next != NULL && queue->next->prior >= /* not <= */ priorty)

or better yet

while (queue->next != NULL && priorty <= queue->next->prior)

Not sure how you intend to handle the case where two elements have the same priority, but since your insert uses "greater than" to replace the head of the queue you probably want to keep the same logic.

Tibrogargan
  • 4,508
  • 3
  • 19
  • 38
  • It's in the answer :). `<` not `<=` – Tibrogargan Mar 20 '16 at 21:52
  • Still getting same problem :/ – idanyal Mar 20 '16 at 21:59
  • You are pointing to the correct line, but the fix is incorrect. It should be `>=` instead of `<=` – chqrlie Mar 20 '16 at 22:04
  • 1
    Sorry, my bad. should be `>=`, not `<`. You probably want to reverse the order of the arguments so you can keep the same logic between code sections. I'll update the answer – Tibrogargan Mar 20 '16 at 22:05
  • Thank you guys :D its all working – idanyal Mar 20 '16 at 22:08
  • I might be getting way too anal, but perhaps think about not using the name "prior". I think it's short for "priority", but it also means "previous" - which can start to add elements of confusion when you're talking about linked lists. (Getting REALLY anal, you should maybe refactor the whole thing and stop using "queue" and/or "que" entirely, since this is really a stack) – Tibrogargan Mar 20 '16 at 22:16
  • okay i have changed the names, is there an alternative way i can write this code? to change it up bit more – idanyal Mar 20 '16 at 22:20
  • @idanyal Apart from getting rid of the "unchanging first node" comment on the temp variable? lol, I think you're getting into code style and that's a can of worms – Tibrogargan Mar 20 '16 at 22:23
  • @Tibrogargan is there anyway i can rewrite it so the layout is more easier to understand, because i will be graded on this – idanyal Mar 20 '16 at 22:32
  • I think you've done a reasonable job, but I'm not your teacher. You might want to more clearly document the conditions of each of your code branches (i.e. "checks if stacktop is empty" is not complete) - and there's no comment on the branch that you had the most trouble with. Also, maybe your structure member naming still maybe needs work, "status" has implications, maybe "value" might be better - but that really depends on your requirements. – Tibrogargan Mar 20 '16 at 22:48
  • @idanyal: you should use English words, not dubious abbreviations or misspelled identifiers: `priorty` should be `priority`. The struct field should be change too, if that is within your attributions. – chqrlie Mar 20 '16 at 23:13
  • Getting anal/pedantic again. Your first branch essentially does this: tests if the existing stack is null or the first entry has a lower priority and if either condition is true, replaces the head of the stack. Your code cleverly makes no distinction between the stack being null and the new entry having a higher priority because in both cases the new stack head has the "next" pointer set to the old stack. Clever (while maybe more satisfying) may not be clear. Be sure to document. – Tibrogargan Mar 20 '16 at 23:14
  • Is there a way to change the while into a for loop? – idanyal Mar 20 '16 at 23:29
  • yes, but why? While is appropriate here. "While I don't have an insert position" ... `for(queue = stacktopPop; queue->next != NULL && priorty <= queue->next->prior; queue = queue->next) { ; // this is an ugly for loop }` – Tibrogargan Mar 20 '16 at 23:33
  • With for loop i get Error:Segmentation fault – idanyal Mar 20 '16 at 23:40
  • Sort of not surprised. The point is that the while loop could be called "more natural". Seriously, why do you want to use a for loop here? – Tibrogargan Mar 20 '16 at 23:50
  • i just wanna know how it would work with for loop – idanyal Mar 20 '16 at 23:51
  • I just did that code in Javascript with no issues, but JS is not C. Can't think why you would be getting a seg fault here and I really don't want to try and install a C compiler on my phone – Tibrogargan Mar 20 '16 at 23:59
  • its okay, thankyou anyway – idanyal Mar 21 '16 at 00:01
  • i implented the input by comparing the first char entered, either "i" or "p", is there an alternative way to do this. is there a way i can do it so it compares by string rather then char – idanyal Mar 21 '16 at 00:02
  • I just got back to my desktop and copied and pasted that for loop and it works ok. Something else is going on. String comparison functions: http://www.tutorialspoint.com/c_standard_library/c_function_strcmp.htm or http://stackoverflow.com/questions/8004237/how-do-i-properly-compare-strings-in-c (also strncmp and a whole bunch of other possibilities). Maybe just stick with 'i' and 'p' – Tibrogargan Mar 21 '16 at 00:30
0

You loop for inserting the node is incorrect, it should read:

while (queue->next != NULL && queue->next->prior >= priorty)
   queue = queue->next;
chqrlie
  • 131,814
  • 10
  • 121
  • 189