找回密码
 立即注册
  • QQ空间
  • 回复
  • 收藏

C++实现队列【Queue】数据结构(链表描述)

admin 2019-9-11 10:58 83人围观 C++相关

队列是一种先进先出(FIFO)的线性表,可以使用链表或数组进行描述。一个队列应该具备如下功能:
    1. 创建一个队列; 2. 检查队列是否非空; 3. 得到队列的长度; 4. 得到新入队的元素; 5. 得到准备出队的元素; 6. 执行一次出队操作; 7. 执行一次入队操作; 8. 清空一个队列,并将其元素入队至另外一个队列(下文称“剪贴操作”); 9. 将一个队列中的所有元素入队至另外一个队列,但该队列元素不变动(下文称“复制操作”);
    本程序使用C++构建了这样一个队列,使用Xcode编译。一共由三个文件构成。头文件,函数定义文件以及测试文件。本程序还使用了C++异常检查、友元函数等方法。其中,头文件如下:
      //// queuedefine.hpp// queue//// Created by lq on 2019/9/10.// Copyright © 2019 Mr.liang. All rights reserved.//
      #ifndef queuedefine_hpp#define queuedefine_hpp//定义链表节点structnode{ node* next; node* last;int data;};//定义队列(Queue)类classqueuedefine{private: node* queue_in;//入队(队尾) node* queue_out;//出队(队头)int length;//队列长度public: queuedefine();//构造函数 ~queuedefine();//析构函数intempty_check();//检查队列是否非空intget_size();//得到队列长度int & front();//返回队头元素int & back();//返回队尾元素voidpop();//执行一次出队voidpush(constint & element);//入队elementvoidshow()const;//遍历队列//将一个队列中的所有元素入队至另外一个队列,但该队列元素不变动;queuedefine queuecopy(queuedefine & q);//清空一个队列,并将其元素入队至另外一个队列;friend queuedefine & clip_paste(queuedefine & target,queuedefine & q);};
      #endif/* queuedefine_hpp */

      函数定义文件如下:
        //// queuedefine.cpp// queue//// Created by lq on 2019/9/10.// Copyright © 2019 Mr.liang. All rights reserved.//
        #include"queuedefine.hpp"#include<iostream>usingnamespacestd;
        queuedefine::queuedefine(){ queue_in = new node; queue_out = new node; queue_in->next = queue_out; queue_in->last = nullptr; queue_out->next = nullptr; queue_out->last = queue_in; length = 0;}
        queuedefine::~queuedefine(){cout<<"bye"<<endl;}
        int queuedefine::empty_check(){if(length == 0) {returntrue; }else {returnfalse; }}
        int queuedefine::get_size(){return length;}
        int & queuedefine::front(){ node* temp = queue_out->last;return temp->data;}
        int& queuedefine::back(){ node* temp = queue_in->next;return temp->data;}
        void queuedefine::pop(){ node* temp = queue_out->last; node* p = temp->last; p->next = queue_out; queue_out->last = p; length--;delete temp;}
        void queuedefine::push(constint & element){ queue_in->last = new node; node* temp = queue_in; queue_in = queue_in->last; queue_in->next = temp; queue_in->last = nullptr; temp->data = element; length++;}
        void queuedefine::show() const{if(length == 0) {throw"empty queue";//C++异常之throw方法 } node* temp = queue_out;while(temp->last != queue_in) { temp = temp->last;cout<<temp->data<<" "; }cout<<endl;}
        //target前的引用符号不能丢,否则会导致push失败queuedefine & clip_paste(queuedefine & target, queuedefine & q){while(q.get_size()) {cout<<"element: "<<q.front()<<" is operated"<<endl; target.push(q.front()); q.pop(); }return target;}
        queuedefine queuedefine::queuecopy(queuedefine & q){int len = q.get_size();while(!(len == 0)) {cout<<"element: "<<q.front()<<" is operated"<<endl; push(q.front()); q.push(q.front()); q.pop(); len--; }return *this;}

        测试文件如下:(执行剪贴操作,不执行复制操作)
          //// main.cpp// queue//// Created by lq on 2019/9/10.// Copyright © 2019 Mr.liang. All rights reserved.//
          #include<iostream>#include"queuedefine.hpp"usingnamespacestd;
          intmain(int argc, constchar * argv[]){// insert code here... queuedefine myqueue,myqueue_copy; myqueue.push(1); myqueue.push(2); myqueue.push(3); myqueue.push(4); myqueue.push(5); myqueue.push(6); myqueue_copy.push(10); myqueue.show(); myqueue.pop(); myqueue.show(); clip_paste(myqueue_copy,myqueue);//myqueue_copy.queuecopy(myqueue); myqueue_copy.show();//C++异常之try—catch方法try { myqueue.show(); } catch (constchar *s) {cout<<s<<", myqueue is empty"<<endl; }return0;}

          运行结果如下:

            12 3 4 5 6 23 4 5 6 element: 2 is operatedelement: 3 is operatedelement: 4 is operatedelement: 5 is operatedelement: 6 is operated102 3 4 5 6 emptyqueue, myqueue is emptybyebyeProgramended with exit code: 0

            测试文件如下:(执行复制操作,不执行剪贴操作)
              //// main.cpp// queue//// Created by lq on 2019/9/10.// Copyright © 2019 Mr.liang. All rights reserved.//
              #include<iostream>#include"queuedefine.hpp"usingnamespacestd;
              intmain(int argc, constchar * argv[]){// insert code here... queuedefine myqueue,myqueue_copy; myqueue.push(1); myqueue.push(2); myqueue.push(3); myqueue.push(4); myqueue.push(5); myqueue.push(6); myqueue_copy.push(10); myqueue.show(); myqueue.pop(); myqueue.show();//clip_paste(myqueue_copy,myqueue); myqueue_copy.queuecopy(myqueue); myqueue_copy.show();//C++异常之try—catch方法try { myqueue.show(); } catch (constchar *s) {cout<<s<<", myqueue is empty"<<endl; }return0;}

              运行结果如下:

                12 3 4 5 6 23 4 5 6 element: 2 is operatedelement: 3 is operatedelement: 4 is operatedelement: 5 is operatedelement: 6 is operatedbye102 3 4 5 6 23 4 5 6 byebyeProgram ended with exit code: 0
                全文完。


                ----------------------------------------------------------------------------------------------------------------------
                我们尊重原创,也注重分享,文章来源于微信公众号:梁公子的备忘录,建议关注公众号查看原文。如若侵权请联系qter@qter.org。
                ----------------------------------------------------------------------------------------------------------------------

                鲜花

                握手

                雷人

                路过

                鸡蛋

                yafeilinux和他的朋友们微信公众号二维码

                微信公众号

                专注于Qt嵌入式Linux开发等。扫一扫立即关注。

                Qt开源社区官方QQ群二维码

                QQ交流群

                欢迎加入QQ群大家庭,一起讨论学习!

                我有话说......