By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
446,234 Members | 1,889 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 446,234 IT Pros & Developers. It's quick & easy.

Circular queue

P: 12
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 store up to 10 items?

Output from my code:

Enter you choice: 1
Enter ID document to print : 21

Enter you choice: 1
Enter ID document to print : 22

Enter you choice: 1
Enter ID document to print : 23

Enter you choice: 1
Enter ID document to print : 24

Enter you choice: 1
Enter ID document to print : 25

Enter you choice: 1
Enter ID document to print : 26

Enter you choice: 1
Enter ID document to print : 27

Enter you choice: 1
Enter ID document to print : 28

Enter you choice: 1
Enter ID document to print : 29

Enter you choice: 1
Enter ID document to print : 30
Error: Queue Full




Here is my code;
Expand|Select|Wrap|Line Numbers
  1. #include <stdio.h>
  2. #define maxQueue 10
  3.  
  4. typedef char BOOL;
  5. typedef int itemType;
  6. typedef struct QUEUE
  7. {
  8.     int head;
  9.     int tail;
  10.     int items[maxQueue];
  11. }queue;
  12.  
  13. void initQueue(queue *);
  14. BOOL emptyQueue(queue *);
  15. BOOL fullQueue(queue *);
  16. void insertQueue(itemType ,queue *);
  17. void deleteQueue(itemType *,queue *);
  18. void menu();
  19. void SendToPrint(queue *);
  20. void Print(queue *);
  21.  
  22.  
  23. int main()
  24. {
  25.     queue nQ;
  26.     int i = 0;
  27.     //clrscr();
  28.     initQueue(&nQ);
  29.     do
  30.     {
  31.         menu();
  32.         scanf("%d",&i);
  33.         switch (i)
  34.         {
  35.             case 1:SendToPrint(&nQ);break;
  36.  
  37.             case 2:Print(&nQ);break;
  38.  
  39.             case 3:Exit(0);break;
  40.  
  41.             default:printf("\nERROR");break;
  42.         }
  43.     }while (i!=3);
  44. }
  45.  
  46. void SendToPrint(queue *q)
  47. {
  48.     itemType nItem;
  49.     printf("\n\nEnter ID document to print :");
  50.     scanf("\t%d",&nItem);
  51.     insertQueue(nItem,q);
  52.  
  53.     return;
  54. }
  55.  
  56. void Print(queue *q)
  57. {
  58.     int i;
  59.     BOOL state;
  60.     printf("\n\nCheck printer buffer...");
  61.  
  62.  
  63.     if(q->tail < q->head) 
  64.         state = ((BOOL)(q->head - q->tail) > 4);
  65.     else
  66.         state = ((BOOL)(q->tail - q->head) > 4);
  67.     if (state)
  68.     {
  69.         for (i = 0;i<5 ;i++)
  70.         {
  71.             printf("\nID Document print  %d",q->items[q->head]);
  72.             deleteQueue(q->items[q->head],q);
  73.  
  74.         }
  75.     }
  76.     else
  77.         printf("\nError Printer buffer no enough\n");
  78.     return;
  79. }
  80.  
  81. void menu()
  82. {
  83.     printf("\n****Printer Spooling****\n");
  84.     printf("1 - Sent document to print\n");
  85.     printf("2 - Print document\n");
  86.     printf("3 - Exit\n");
  87.     printf("Please enter your choice :");
  88. }
  89.  
  90. void initQueue(queue *q)
  91. {
  92.    q->head = 0;
  93.    q->tail = 0;
  94. }
  95.  
  96. BOOL emptyQueue(queue *q)
  97. {
  98.     return ((BOOL)(q->head == q->tail));
  99. }
  100.  
  101. BOOL fullQueue(queue *q)
  102. {
  103.     return ((BOOL)(((q->tail-1) % maxQueue) == q->head));
  104.  
  105. }
  106.  
  107. void insertQueue(itemType nItem,queue *q)
  108. {
  109.     if (fullQueue(q))
  110.         printf(" Error : Queue Full\n");
  111.     else
  112.     {
  113.  
  114.             q->items[q->tail] = nItem;
  115.             q->tail = (q->tail+1)%maxQueue;
  116.  
  117.  
  118.     }
  119. }
  120.  
  121. void deleteQueue(itemType *nItem,queue *q)
  122. {
  123.     if (emptyQueue(q))
  124.         printf(" Error : Queue Empty\n");
  125.     else
  126.     {
  127.  
  128.         q->head = (q->head + 1) % maxQueue;
  129.  
  130.     }
  131. }
Mar 20 '07 #1
Share this Question
Share on Google+
2 Replies


DeMan
100+
P: 1,806
Have you tried setting up a function to display eveery item in the queue? This is always a very good way to see if something fishy is going on
Mar 20 '07 #2

Banfa
Expert Mod 5K+
P: 8,916
The way you have set up your circular buffer (which is fairly common as it gets round some other problems mainly distinguishing between an empty list and a full list) you have to have at least 1 empty entry in the list. So if the list is 10 items long it can only hold 9 items in it.

This comes from the maths in your fullQueue function, the queue is full if the tail is 1 item ahead of the head, since the tail points to the next item to write and not a filled in item it must therefore point to an empty slot so your queue must contain 1 unused slot.

It you changed the queue full definition by removing the -1 from fullQueue then you would find the maths in fullQueue resolve to exactly the same test as emptyQueue, you would not be able to distinguish between an empty queue and a full queue.

Often it is just accepted that the queue holds size-1 items as it makes the code a lot simpler for not too much memory overhead, especially since often if you are using a circular buffer you do not want to get to the situation of having a full queue anyway as this is often some sort of error.
Mar 20 '07 #3

Post your reply

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