数据结构探险系列—队列篇-学习笔记

作者: 天涯明月笙 | 来源:发表于2017-09-02 12:19 被阅读429次

数据结构探险系列—队列篇

这是c++远征系列的进阶课程。

什么是数据结构？

一群数据集合和数据之间的关系。
是指相互之间存在一种或多种特定关系的数据元素集合，

我么将学到：

原理
c++实现编码

队列

特定：先入先出（FIFO）

火车站买票。队头队尾。售票员从头开始卖票。先到的人先买到票就可以离开。

队列的分类：

普通队列
环形队列

队列

左侧窗口想象为售票员。然后第一个人排队，它既是队列头，又是队列尾。之后再进来人。队列尾为最后一个人。内存限制。队列不可能无限长。

两种方式：

售票员卖完一个票往前走一位。浪费了已经走入的空间。
售票员不动。所有人走一位。速度慢。

环形队列

优缺点：

屏蔽了普通队列的缺点
不好理解

有队列头，有队列尾。只有一个元素，既是队列头，又是队列尾。

有顺时针排队和逆时针排队之说的。
贪吃蛇自己吃自己尾巴

队列的用途；自动排号机

单子：

拍号机单据

面向对象的队列设计

myqueue.h:

#ifndef MYQUEUE_H
#define MYQUEUE_H
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 EnQueue(int element); //EnQueue(&Q，&element) 新元素加入
    bool DeQueue(int &element);//DeQueue(&Q,&element) 首元素出队
    void QueueTraverse();      //QueueTraverse(Q,visit()) 遍历队列
    //简单类型不需要实现visit方法。
private:
    int *m_pQueue;             //队列数组指针
    int m_iQueueLen;           //队列元素个数
    int m_iQueueCapacity;      //队列数组容量
    int m_iHead;              //数组的下标：队头
    int m_iTail;              //数组的下标： 队尾
};
#endif

上述代码左侧为c++中队列实现所需要的函数。右侧注释部分为c语言。
一个队列的实现对于c++必须要有以下数据成员及成员函数：

创建队列的构造函数（传入队列容量）
销毁队列的析构函数
清空队列
判断队列是否为空
新元素加入
首元素出队
遍历队列
数据：容量、数组指针、容量

环形队列代码实现

一个只有4元素的环形队列

红色圈为指定插入点。插入第一个则。头尾均为0.队尾指向的位置就是要插入的位置，
每次插入之前判断有没有占满。每次从队头取。

myqueue.h:

#ifndef MYQUEUE_H
#define MYQUEUE_H
class MyQueue 
{
public:
    MyQueue(int queueCapacity);//InitQueue(&Q)创建队列
    virtual ~MyQueue();        //DestroyQueue(&Q)销毁队列
    void ClearQueue();         //ClearQueue(&Q)清空队列
    bool QueueEmpty() const;   //QueueEmpty(Q)判空队列
    bool QueueFull() const;    //判断满
    int  QueueLength() const;   //QueueLength(Q) 队列长度
    bool EnQueue(int element); //EnQueue(&Q，&element) 新元素加入
    bool DeQueue(int &element);//DeQueue(&Q,&element) 首元素出队
    void QueueTraverse();      //QueueTraverse(Q,visit()) 遍历队列
    //简单类型不需要实现visit方法。
private:
    int *m_pQueue;             //队列数组指针
    int m_iQueueLen;           //队列元素个数
    int m_iQueueCapacity;      //队列数组容量
    int m_iHead;               //数组的下标：队头
    int m_iTail;               //数组的下标： 队尾
};
#endif

myqueue.cpp:

#include "MyQueue.h"
#include <iostream>
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];
    ClearQueue();
}

MyQueue::~MyQueue()
{
    delete[]m_pQueue;
    m_pQueue = NULL;
}

void MyQueue::ClearQueue()
{
    //重置队头队尾
    m_iHead = 0;
    m_iTail = 0;
    //队列元素个数重置
    m_iQueueLen = 0;
}

bool MyQueue::QueueEmpty() const
{
    //长度为0为空，head和tail会移动。不一定等于0
    /*if (m_iQueueLen == 0)
    {
        return true;
    }
    else
    {
        return false;
    }*/
    return (m_iQueueLen == 0) ? true : false;
}

int MyQueue::QueueLength() const
{
    return m_iQueueLen;
}

bool MyQueue::QueueFull() const
{
    return (m_iQueueLen == m_iQueueCapacity) ? true : false;
}

bool MyQueue::EnQueue(int element)
{
    //先判断满
    if (QueueFull())
    {
        return false;
    }
    else
    {
        //插入尾部
        m_pQueue[m_iTail] = element;
        //队尾后移
        m_iTail++;
        m_iTail = m_iTail % m_iQueueCapacity;//循环
        //插入元素改变len
        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;
    }
}
//使用const函数是为了防止这个函数对数据成员进行改变，这个函数只可以读取数据成员，所以，当不希望函数对数据成员改变时就需要使用从const函数

void MyQueue::QueueTraverse()
{
    for (int i=m_iHead;i<m_iHead+m_iQueueLen;i++)
        //要加上头的数字。不然次数不够
        //当前i是3.len是满。则i++越界
    {
        cout << m_pQueue[i%m_iQueueCapacity] << endl;
    }
}

几点要注意的地方：

m_iTail = m_iTail % m_iQueueCapacity;//循环
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_iHead+m_iQueueLen;i++)
        //要加上头的数字。不然次数不够
        //当前i是3.len是满。则i++越界
    {
        cout << m_pQueue[i%m_iQueueCapacity] << endl;
    }
}

注意取余操作防止数组越界。注意循环终止条件添加m_ihead

main.cpp:

#include <iostream>
#include <stdlib.h>
#include "MyQueue.h"
using namespace std;
int main()
{
    MyQueue *p = new MyQueue(4);
    p->EnQueue(10);
    p->EnQueue(12);
    p->EnQueue(16);
    p->EnQueue(18);
    //p->EnQueue(20);
    p->QueueTraverse();

    int e = 0;
    p->DeQueue(e);
    cout << endl;
    cout << e << endl;

    p->DeQueue(e);
    cout << endl;
    cout << e << endl;
    cout << endl;
    p->QueueTraverse();

    p->ClearQueue();
    cout << endl;
    p->QueueTraverse();

    p->EnQueue(20);
    p->EnQueue(30);
    cout << endl;
    p->QueueTraverse();

    delete p;
    p = NULL;
    system("pause");
    return 0;
}

数组的实际应用

#ifndef CUSTOMER_H
#define CUSTOMER_H
#include <string>
using namespace std;

class Customer
{
public:
    Customer(string name=" ", int age=0);
    void printInfo() const;
private:
    string m_strName;
    int m_iAge;
};


#endif // !CUSTOMER_H

#include <iostream>
#include "Customer.h"
using namespace std;

Customer::Customer(string name, int age)
{
    m_strName = name;
    m_iAge = age;
}

void Customer::printInfo() const
{
    cout << "姓名：" << m_strName << endl;
    cout << "年龄：" << m_iAge << endl;
}

queue：

#ifndef MYQUEUE_H
#define MYQUEUE_H
#include "Customer.h"


class MyQueue
{
public:
    MyQueue(int queueCapacity);//InitQueue(&Q)创建队列
    virtual ~MyQueue();        //DestroyQueue(&Q)销毁队列
    void ClearQueue();         //ClearQueue(&Q)清空队列
    bool QueueEmpty() const;   //QueueEmpty(Q)判空队列
    bool QueueFull() const;    //判断满
    int  QueueLength() const;   //QueueLength(Q) 队列长度
    bool EnQueue(Customer element); //EnQueue(&Q，&element) 新元素加入
    bool DeQueue(Customer &element);//DeQueue(&Q,&element) 首元素出队
    void QueueTraverse();      //QueueTraverse(Q,visit()) 遍历队列
                               //简单类型不需要实现visit方法。
private:
    Customer *m_pQueue;             //队列数组指针
    int m_iQueueLen;           //队列元素个数
    int m_iQueueCapacity;      //队列数组容量
    int m_iHead;               //数组的下标：队头
    int m_iTail;               //数组的下标： 队尾
};
#endif


#include "MyQueue.h"
#include <iostream>
using namespace std;

MyQueue::MyQueue(int queueCapacity)
{
    m_iQueueCapacity = queueCapacity;//将容积传递
                                     ////初始化队头队尾
                                     //m_iHead = 0;
                                     //m_iTail = 0;
                                     ////队列元素个数初始化
                                     //m_iQueueLen = 0;
                                     //分配内存
    m_pQueue = new Customer[m_iQueueCapacity];
    ClearQueue();
}

MyQueue::~MyQueue()
{
    delete[]m_pQueue;
    m_pQueue = NULL;
}

void MyQueue::ClearQueue()
{
    //重置队头队尾
    m_iHead = 0;
    m_iTail = 0;
    //队列元素个数重置
    m_iQueueLen = 0;
}

bool MyQueue::QueueEmpty() const
{
    //长度为0为空，head和tail会移动。不一定等于0
    /*if (m_iQueueLen == 0)
    {
    return true;
    }
    else
    {
    return false;
    }*/
    return (m_iQueueLen == 0) ? true : false;
}

int MyQueue::QueueLength() const
{
    return m_iQueueLen;
}

bool MyQueue::QueueFull() const
{
    return (m_iQueueLen == m_iQueueCapacity) ? true : false;
}

bool MyQueue::EnQueue(Customer element)
{
    //先判断满
    if (QueueFull())
    {
        return false;
    }
    else
    {
        //插入尾部
        m_pQueue[m_iTail] = element;
        //队尾后移
        m_iTail++;
        m_iTail = m_iTail % m_iQueueCapacity;//循环
                                             //插入元素改变len
        m_iQueueLen++;
        return true;
    }

}

bool MyQueue::DeQueue(Customer &element)
{
    if (QueueEmpty())
    {
        return false;
    }
    else {
        element = m_pQueue[m_iHead];
        m_iHead++;
        m_iHead = m_iHead % m_iQueueCapacity;
        m_iQueueLen--;
        return true;
    }
}
//使用const函数是为了防止这个函数对数据成员进行改变，这个函数只可以读取数据成员，所以，当不希望函数对数据成员改变时就需要使用从const函数

void MyQueue::QueueTraverse()
{
    for (int i = m_iHead; i<m_iHead + m_iQueueLen; i++)
        //要加上头的数字。不然次数不够
        //当前i是3.len是满。则i++越界
    {
        m_pQueue[i%m_iQueueCapacity].printInfo();
        cout << "前面还有：" << (i - m_iHead) << "人" << endl;
        cout << endl;
    }
}

main.cpp:

#include <iostream>
#include <stdlib.h>
#include "MyQueue.h"
#include "Customer.h"//myqueue中包含过了
using namespace std;
int main()
{
    MyQueue *p = new MyQueue(4);
    Customer c1("zhangsan", 20);
    Customer c2("lisi", 30);
    Customer c3("wangwu", 40);
    p->EnQueue(c1);
    p->EnQueue(c2);
    p->EnQueue(c3);

    p->QueueTraverse();
    Customer c4("", 0);
    p->DeQueue(c4);
    c4.printInfo();

    p->QueueTraverse();
    
    system("pause");
    return 0;
}

运行结果：

运行结果

扩展知识：

队列的类模板实现：扩展出多种数据类型
插入具体其他信息的对象。编号。前面还有几个元素。（放在遍历）

数据结构探险系列—队列篇-学习笔记

数据结构探险系列—队列篇

队列

面向对象的队列设计

环形队列代码实现

数组的实际应用

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

work

数据结构

c++

数据结构与算法

数据结构与算法

程序员

C语言

C++