队列

队列的模型

想象一下现实生活中的队列，排队先入先出，不允许插队，队头先出，队尾进入。（应用：营业厅自动排号机）

队列的编程实现方式

环形队列，数组实现，静态的，事先确定队列容量，人为取余，循环利用数组资源。

普通队列，

~~链表实现，动态的，有点浪费，因为插入删除只在队列头尾进行~~
。

队列的基本元素

要操纵队列，必须要有一个数组（指针），队列长度，队列容量；然后用队列头和队列尾操纵队列。

环形队列中队列头和队列尾到底意味着什么？对尾指向最后一个元素的下一个位置。

队列的基本操作

创建队列，销毁队列，清空队列，队列判空，队列判满，队列长度；元素入队，元素出对，遍历队列

基本操作的实现

创建队列：构造函数实现，函数参数为队列容量；此步需要完成的任务：形成数组实体，即分配内存，将一些队列基本元素初始化。

销毁队列：析构函数实现，释放内存，指针置空。

清空队列：指针不动，基本元素初始化

队列判空：通过长度判断

队列判满：通过长度和容量判断

队列长度：直接返回

元素入队：判断能否插入，能则插入，更新队列基本信息（技巧）

元素出对：判断是否有东西可以删除，更新队列基本信息

遍历队列：循环，从头到尾，遍历（输出）

大部分的操作都是针对队列基本元素的，会利用和改变它。（所以用C++其实是简化了，只需考虑类内数据元素）

写一个大型的数据结构很难，很容易就会出现某些细小的错误，如果无法控制这些细小的错误，那等程序大起来之后，就很难很难找错和调试了。

C++实现步骤

首先，把上面的流程走一遍，做到心中有数。

设计队列的接口（建议写在一个单独文档里，以便随时查阅），先不谈具体实现；（照着抄很容易，关键要会默写）

实现，核心功能，创建，插入，删除，遍历显示，调试成功

补充其他核心功能

代码要写好，还真是太难了，首先要正确的命名，其次大小写还不能搞错，在使用的时候还要一一对应。

函数的返回值、函数名、参数等等，都不允许有错误。（很难一次性写好，在实现时慢慢修正）

初次亲手敲代码的体会：队列的代码量确实很少，接口20多行；实现80多行，测试20多行，根本就不算多；但是写起来还是感觉很难，之前敲书本上的单个例题，感觉还没什么难度；队列元素太多，基本的5个元素，操作太多，9个基本操作，操作之间部分依赖；我对C++的语法也不算太熟悉，有些卡顿；东西太多，太杂，名称太长，导致我眼花缭乱。

课程笔记

这是之前C++的进阶课，数据结构：一群数据以及数据之间的关系（集合+关系），数据结构是前人经验的总结，所以你学习借鉴就好了，不要钻牛角尖。

队列是先入先出的数学模型，队列中很少用到位序，因为只能对首尾进行操作，载入元素默认实在队尾，删除元素默认是在队头。

队列分为普通队列和环形队列

普通队列：分两种情况，一是队头离开，后面全部前移；二是队头离开，不移，往后继续排，这两种结果都不好

环形队列：充分利用资源，也不牺牲效率；队头队尾重叠只有两种情况，要么为空，要么为满。

队列的C和C++实现方式是大为不同的

在C++中，队列被写成了类，每一个具体队列都是该类的实例；而C语言中，只是简单定义了个结构体，C语言函数的参数中一定要含有队列的地址，而C++因为写在了类中，则不用传参数。

标准C++代码

#pragma once//MyQueue.h//环形队列C++实现class MyQueue{public:    MyQueue(int queueCapacity);        //InitQueue(&Q)创建队列    virtual ~MyQueue();                //DestroyQueue(&Q)销毁队列    void ClearQueue();                //ClearQueue(&Q)清空队列    bool QueueEmpty() const;        //QueueEmpty(&Q)判空队列    int QueueLength() const;        //QueueLength(Q)队列长度    bool QueueFull() const;    bool EnQueue(int element);        //EnQueue(&Q, element)新元素入队    bool DeQueue(int &element);        //DeQueue(&Q, &element)首元素出队    void QueueTraverse();            //QueueTraverse(Q, visit())遍历队列private:    int *m_pQueue;                    //队列数组数组    int m_iQueueLen;                //队列元素个数    int m_iQueueCapacity;            //队列数组容量    int m_iHead;    int m_iTail;};

//MyQueue.cpp#include"MyQueue.h"#include
     
      using namespace std;MyQueue::MyQueue(int queueCapacity){    m_iQueueCapacity = queueCapacity;    m_iHead = 0;    m_iTail = 0;    m_iQueueLen = 0;    m_pQueue = new int[m_iQueueCapacity];}MyQueue::~MyQueue(){    delete[]m_pQueue;    m_pQueue = nullptr;}void MyQueue::ClearQueue(){    m_iHead = 0;    m_iTail = 0;    m_iQueueLen = 0;}bool MyQueue::QueueEmpty() const{    if (m_iQueueLen == 0)        return true;    else        return false;}bool MyQueue::QueueFull() const{    if (m_iQueueLen == m_iQueueCapacity)        return true;    else        return false;}int MyQueue::QueueLength() const{    return m_iQueueLen;}bool MyQueue::EnQueue(int element){    if (QueueFull())        return false;    else    {        m_pQueue[m_iTail] = element;        m_iTail++;        m_iTail = m_iTail % m_iQueueCapacity;        m_iQueueLen++;        return true;    }}bool MyQueue::DeQueue(int &element){    if (QueueEmpty())        return false;    else    {        element = m_pQueue[m_iHead];        m_iHead++;        m_iHead = m_iHead % m_iQueueCapacity;        m_iQueueLen--;        return true;    }}void MyQueue::QueueTraverse(){    for (int i = m_iHead; i < m_iQueueLen + m_iHead; i++)    {        cout << m_pQueue[i%m_iQueueCapacity] << endl;    }}

//demo.cpp#include
     
      #include"MyQueue.h"using namespace std;int main(){    MyQueue *p = new MyQueue(4);    p->EnQueue(1);    p->EnQueue(0);    p->EnQueue(11);    p->QueueTraverse();    p->ClearQueue();    cout << "after clear: " << endl;    p->QueueTraverse();    if (p->QueueEmpty())        cout << "Empty queue" << endl;    else        cout << "Not Empty" << endl;    p->EnQueue(5);    p->EnQueue(15);    p->EnQueue(25);    cout << p->QueueLength() << endl;    int tmp;    p->DeQueue(tmp);    cout << "tmp is " << tmp << endl;    cout << p->QueueLength() << endl;    return 0;}

实际应用

节点的数据可以是任意类型的数据，ElemType为Customer

//Customer.h#pragma once#include 
     
      using namespace std;class Customer{public:    Customer(string name = "", int age = 0);    void printInfo() const;private:    string m_strName;    int m_iAge;};

//Customer.cpp#include
     
      #include"Customer.h"using namespace std;Customer::Customer(string name, int age){    m_strName = name;    m_iAge = age;}void Customer::printInfo() const{    cout << "Name: " << m_strName << endl;    cout << "Age: " << m_iAge << endl;    cout << "=================" << endl;}

//demo.cpp#include
     
      #include"MyQueue.h"using namespace std;int main(){    MyQueue *p = new MyQueue(4);    Customer c1("zhangsan", 20);    Customer c2("lisi", 30);    Customer c3("wangwu", 24);    p->EnQueue(c1);    p->EnQueue(c2);    p->EnQueue(c3);    p->QueueTraverse();    cout << endl;    Customer c4;    p->DeQueue(c4);    cout << "this is c4: " << endl;    c4.printInfo();    cout << "this is QueueTraverse: " << endl;    p->QueueTraverse();    return 0;}

使用C++模板写一个队列

比较C和C++实现的不同

转载地址：http://yhfel.baihongyu.com/

你可能感兴趣的文章