[关闭]
@bintou 2017-11-29T13:42:48.000000Z 字数 2743 阅读 644

Queue in C/C++

未分类


  1. // C program for array implementation of queue
  2. /*
  3. Enqueue: Adds an item to the queue. If the queue is full, then it is said to be an Overflow condition.
  4. Dequeue: Removes an item from the queue. The items are popped in the same order in which they are pushed. If the queue is empty, then it is said to be an Underflow condition.
  5. Front: Get the front item from queue.
  6. Rear: Get the last item from queue.
  7. */
  8. #include <stdio.h>
  9. #include <stdlib.h>
  10. #include <limits.h>
  11. // A structure to represent a queue
  12. struct Queue
  13. {
  14. int front, rear, size;
  15. unsigned capacity;
  16. int* array;
  17. };
  18. // function to create a queue of given capacity.
  19. // It initializes size of queue as 0
  20. struct Queue* createQueue(unsigned capacity)
  21. {
  22. struct Queue* queue = (struct Queue*) malloc(sizeof(struct Queue));
  23. queue->capacity = capacity;
  24. queue->front = queue->size = 0;
  25. queue->rear = capacity - 1; // This is important, see the enqueue
  26. queue->array = (int*) malloc(queue->capacity * sizeof(int));
  27. return queue;
  28. }
  29. // Queue is full when size becomes equal to the capacity
  30. int isFull(struct Queue* queue)
  31. { return (queue->size == queue->capacity); }
  32. // Queue is empty when size is 0
  33. int isEmpty(struct Queue* queue)
  34. { return (queue->size == 0); }
  35. // Function to add an item to the queue.
  36. // It changes rear and size
  37. void enqueue(struct Queue* queue, int item)
  38. {
  39. if (isFull(queue))
  40. return;
  41. queue->rear = (queue->rear + 1)%queue->capacity;
  42. queue->array[queue->rear] = item;
  43. queue->size = queue->size + 1;
  44. printf("%d enqueued to queue\n", item);
  45. }
  46. // Function to remove an item from queue.
  47. // It changes front and size
  48. int dequeue(struct Queue* queue)
  49. {
  50. if (isEmpty(queue))
  51. return INT_MIN;
  52. int item = queue->array[queue->front];
  53. queue->front = (queue->front + 1)%queue->capacity;
  54. queue->size = queue->size - 1;
  55. return item;
  56. }
  57. // Function to get front of queue
  58. int front(struct Queue* queue)
  59. {
  60. if (isEmpty(queue))
  61. return INT_MIN;
  62. return queue->array[queue->front];
  63. }
  64. // Function to get rear of queue
  65. int rear(struct Queue* queue)
  66. {
  67. if (isEmpty(queue))
  68. return INT_MIN;
  69. return queue->array[queue->rear];
  70. }
  71. // Driver program to test above functions./
  72. int main()
  73. {
  74. struct Queue* queue = createQueue(1000);
  75. enqueue(queue, 10);
  76. enqueue(queue, 20);
  77. enqueue(queue, 30);
  78. enqueue(queue, 40);
  79. printf("%d dequeued from queue\n", dequeue(queue));
  80. printf("Front item is %d\n", front(queue));
  81. printf("Rear item is %d\n", rear(queue));
  82. return 0;
  83. }
  1. /*
  2. The functions supported by queue are :
  3. empty() – Returns whether the queue is empty
  4. size() – Returns the size of the queue
  5. front() – Returns a reference to the first element of the queue
  6. back() – Returns a reference to the last element of the queue
  7. push(g) – Adds the element ‘g’ at the end of the queue
  8. pop() – Deletes the first element of the queue
  9. */
  10. #include <iostream>
  11. #include <queue>
  12. using namespace std;
  13. void showq(queue <int> gq)
  14. {
  15. queue <int> g = gq;
  16. while (!g.empty())
  17. {
  18. cout << '\t' << g.front();
  19. g.pop();
  20. }
  21. cout << '\n';
  22. }
  23. int main()
  24. {
  25. queue <int> gquiz;
  26. gquiz.push(10);
  27. gquiz.push(20);
  28. cout << "The queue gquiz is : ";
  29. showq(gquiz);
  30. cout << "\ngquiz.size() : " << gquiz.size();
  31. cout << "\ngquiz.front() : " << gquiz.front();
  32. cout << "\ngquiz.back() : " << gquiz.back();
  33. cout << "\ngquiz.pop() : ";
  34. gquiz.pop();
  35. showq(gquiz);
  36. return 0;
  37. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注