当前位置:   article > 正文

队列的入队出队操作(C++循环链表)_c++出队

c++出队

队列:只允许在一端进行插入操作,在另一端进行删除操作。允许插入(入队、进队)的一段端称为队尾,允许删除(出队)的一端称为队首(队头)。

队列具有

先进先出的特点。

题目:设计以不带头结点的循环链表表示队列,并且只设置一个指针指向队尾结点,但不设头指针。设计相应的入队和出队操作的算法。

C++的实现:

  1. #include<iostream>
  2. using namespace std;
  3. struct note
  4. {
  5. int data;
  6. note *next;
  7. };
  8. class LinkQueue
  9. {
  10. public:
  11. LinkQueue(int a[],int n);//初始化链队列
  12. ~LinkQueue() {};
  13. void EnQueue(int x);//将x入队
  14. int DeQueue();//出队操作
  15. void print();//遍历链队列
  16. private:
  17. note *rear;
  18. };
  19. LinkQueue::LinkQueue(int a[],int n)
  20. {
  21. note *first;
  22. first = new note;//生成头结点
  23. rear = first;//尾指针初始化
  24. for (int i = 0; i < n; i++)
  25. {
  26. note *s;
  27. s = new note; s->data = a[i];//为每个数组元素建立一个结点
  28. rear->next = s; rear = s;//将结点s插入到终端结点之后
  29. }//与尾插法建立单链表类似
  30. rear->next = first->next;//数据初始化结束后,尾指针指向存有数据的第一个结点,删除first指针指向的数据域为空的头结点
  31. delete first;//尾插法建立循环链表
  32. }
  33. void LinkQueue::EnQueue(int x)
  34. {
  35. note *s;
  36. s = new note; s->data = x;//生成新结点
  37. s->next = rear->next;
  38. rear->next = s;//入队操作,将新建的结点插入队尾,和在单链表中任意位置插入结点一样
  39. rear = s;//尾指针后移
  40. }
  41. int LinkQueue::DeQueue()
  42. {
  43. note *p;
  44. int x;
  45. p = rear->next;//工作指针指向队首
  46. x = p->data;
  47. rear->next = p->next;
  48. delete p;//队首元素出队,和单链表中删除任意结点一样
  49. return x;//返回出队的队首元素
  50. }
  51. void LinkQueue::print()
  52. {
  53. note *q,*p;
  54. q=p=rear->next;
  55. do
  56. {
  57. cout << q->data<<'\t';//输出当前数据
  58. q = q->next;//指针后移
  59. } while (p != q);//p,q指针指向同一结点时遍历结束
  60. cout << endl;
  61. }
  62. int main()
  63. {
  64. int a[] = { 1,2,3,4,5 };
  65. int x = 6;
  66. LinkQueue test(a, 5);
  67. cout << "输出链队列:" << endl;
  68. test.print();
  69. cout <<"将 x="<<x<<" 入队并取出队首元素 a="<<test.DeQueue()<<endl;
  70. test.EnQueue(x);
  71. cout << "输出链队列:" << endl;
  72. test.print();
  73. return 0;
  74. }


 

 

 

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

闽ICP备14008679号