当前位置:   article > 正文

队列的C++实现_队列c++实现

队列c++实现

 队列是FIFO型结构,即先进先出,即入队(队尾添加)和出队(队首删除)。一个队列,则分首尾。如何分?两个方法:动态数组和指向队列头部的索引。入队会向队列追加一个新元素,而出队会删除第一个元素。 所以我们需要一个索引来指出起点。

  1. #include<iostream>
  2. #include<vector>
  3. using namespace std;
  4. class MyQueue{
  5. private:
  6. vector<int> data; //存储元素
  7. int p_start; //起始位置的指针
  8. public:
  9. MyQueue(){p_start = 0;}
  10. //往队列插入一个元素,成功返回true
  11. bool inQueue(int x){
  12. data.push_back(x);
  13. return true;
  14. }
  15. //从队列删除一个元素,成功返回true
  16. bool delQueue(){
  17. if(isEmpty()){
  18. return false;
  19. }
  20. p_start++;
  21. return true;
  22. }
  23. //获取队列前面的元素
  24. int Front(){return data[p_start];}
  25. //检查队列是否为空
  26. bool isEmpty(){
  27. return p_start >= data.size();
  28. }
  29. };
  30. int main()
  31. {
  32. MyQueue q;
  33. q.inQueue(5);
  34. q.inQueue(1);
  35. q.inQueue(8);
  36. if(!q.isEmpty()){
  37. cout<<q.Front()<<endl;
  38. }
  39. q.delQueue();
  40. if(!q.isEmpty()){
  41. cout<<q.Front()<<endl;
  42. }
  43. q.delQueue();
  44. if(!q.isEmpty()){
  45. cout<<q.Front()<<endl;
  46. }
  47. }

 上面的实现适用于添加比较少的元素,随着起始指针p_start的移动,会浪费越来越多的空间。

 更有效的方法是使用循环队列。 具体来说,我们可以使用固定大小的数组两个指针来指示起始位置和结束位置。 目的是重用我们之前提到的被浪费的存储

在循环队列中,我们使用一个数组和两个指针(head 和 tail)。 head 表示队列的起始位置,tail 表示队列的结束位置。

  1. class MyCircularQueue {
  2. private:
  3. vector<int> data;
  4. int head;
  5. int tail;
  6. int size;
  7. public:
  8. //在此处初始化数据结构。将队列的大小设置为 k。
  9. MyCircularQueue(int k) {
  10. data.resize(k);
  11. head = -1;
  12. tail = -1;
  13. size = k;
  14. }
  15. //将元素插入循环队列。如果操作成功,则返回 true。
  16. bool enQueue(int value) {
  17. if (isFull()) {
  18. return false;
  19. }
  20. if (isEmpty()) {
  21. head = 0;
  22. }
  23. tail = (tail + 1) % size;
  24. data[tail] = value;
  25. return true;
  26. }
  27. //从循环队列中删除元素。如果操作成功,则返回 true。
  28. bool deQueue() {
  29. if (isEmpty()) {
  30. return false;
  31. }
  32. if (head == tail) {
  33. head = -1;
  34. tail = -1;
  35. return true;
  36. }
  37. head = (head + 1) % size;
  38. return true;
  39. }
  40. //从队列中获取首元素。
  41. int Front() {
  42. if (isEmpty()) {
  43. return -1;
  44. }
  45. return data[head];
  46. }
  47. //获取队列最后一个元素
  48. int Rear() {
  49. if (isEmpty()) {
  50. return -1;
  51. }
  52. return data[tail];
  53. }
  54. //检查循环队列是否为空。
  55. bool isEmpty() {
  56. return head == -1;
  57. }
  58. //检查循环队列是否已满。
  59. bool isFull() {
  60. return ((tail + 1) % size) == head;
  61. }
  62. };

大多数流行语言都提供内置的队列库,因此无需重新发明轮子。

如前所述,队列有两个重要的操作,入队 enqueue 和出队 dequeue。 此外,我们应该能够获得队列中的第一个元素,因为应该首先处理它。

下面是使用内置队列库及其常见操作的一些示例:

  1. #include <iostream>
  2. #include<queue>
  3. using namespace std;
  4. int main() {
  5. // 1. Initialize a queue.
  6. queue<int> q;
  7. // 2. Push new element.
  8. q.push(5);
  9. q.push(13);
  10. q.push(8);
  11. q.push(6);
  12. // 3. Check if queue is empty.
  13. if (q.empty()) {
  14. cout << "Queue is empty!" << endl;
  15. return 0;
  16. }
  17. // 4. Pop an element.
  18. q.pop();
  19. // 5. Get the first element.
  20. cout << "The first element is: " << q.front() << endl;
  21. // 6. Get the last element.
  22. cout << "The last element is: " << q.back() << endl;
  23. // 7. Get the size of the queue.
  24. cout << "The size is: " << q.size() << endl;
  25. }

 

 

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/正经夜光杯/article/detail/756373
推荐阅读
相关标签
  

闽ICP备14008679号