【慕课-数据结构-C++语言】队列篇

2018-04-21 本文已影响10人苍云横渡

原文链接：https://www.cloudcrossing.xyz/post/28/

最近在复习数据结构，看的是慕课的数据结构探险—队列篇，写写笔记自用。代码放到github上。

队列原理

FIFO（first in first out），先进先出。

普通队列

环形队列

相比普通队列，环形队列可以在固定大小的内存空间中反复使用。环形队列有顺时针和逆时针之分。

面向对象的队列设计

#MyQueue.h
#ifndef MYQUEUE_H
#define MYQUEUE_H

class MyQueue
{
public:
    MyQueue(int queueCapacity);  //创建队列
    virtual ~MyQueue();          //销毁队列
    void ClearQueue();           //清空队列
    bool QueueEmpty() const;     //判空队列
    bool QueueFull() const;      //判满队列
    int QueueLength() const;     //队列长度
    bool EnQueue(int element);   //新元素入队
    bool DeQueue(int &element);  //首元素出队
    void QueueTraverse();        //遍历队列
private:
    int *m_pQueue;               //队列数组指针
    int m_iQueueLen;             //队列元素个数
    int m_iQueueCapacity;        //队列数组容量
    int m_iHead;
    int m_iTail;
};

#endif

其中，判断和队列长度无需修改队列，加上const可以声明为const成员函数，保护对象的数据不会被修改，而且编译更快。

环形队列的实现

#MyQueue.cpp
#include "stdafx.h"
#include "MyQueue.h"
#include "iostream"

using namespace std;

MyQueue::MyQueue(int queueCapacity)
{
    m_iQueueCapacity = queueCapacity;
    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
{
    return m_iQueueLen == 0 ? true : false;
}

bool MyQueue::QueueFull() const
{
    return m_iQueueLen == m_iQueueCapacity ? true : 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_iTail = m_iTail % m_iQueueCapacity;
        m_iQueueLen--;
        return true;
    }
}

void MyQueue::QueueTraverse()
{
    for (int i = m_iHead; i < m_iQueueLen + m_iHead; i++)  //保证循环次数为m_iQueueLen
    {
        cout << m_pQueue[i%m_iQueueCapacity] << endl;
        cout << endl;
    }
}

PS：new()时，应注意判断内存是否分配成功，在这里只注重原理，所以不作判断。

清空队列的时候，将头尾指针赋值为0时，在这里并没有起到清空队列的作用。但是长度设置为0时，再次插入数值的时候长度重新从0计数，确保了遍历的时候不会输出旧值。

判断队列空或满的时候可以根据队列实际长度 len和最大长度capacity来判断的（因为存在例外的情况，当队列只包含一个元素时，队头和队尾也一样，所以判断长度更保险），每次入队一个len++，出队一个len--，保证len的大小就是队伍中所存在的元素个数，如果len==capacity，队满，len==0队空。

插入和取出操作时：

环形队列初始队头和队尾指向位置一致。
插入元素时，判断队满。如果队满，队头不变，队尾变，队尾指向插入的元素的下一个位置（即NULL）。先赋值，再移动队尾指针。
取出元素时，判断队空。如果非空，队头移动指向下一个元素，队尾不变。
在插入、取出元素时注意将m_iHead、m_iTail对QueueCapcity取余，防止数组下标越界。

其中：

bool MyQueue::DeQueue(int &element)传入引用是为了可以直接修改实参的值。
bool MyQueue::EnQueue(int element)只是将实参的值传递给形参。

例如：int e = 0;p->DeQueue(e);本来e的值是0，将e的引用传递之后，就可以通过此时队列头部的数据将e修改为一样的数据。

遍历环形队列时要注意循环变量应初始化为队首指针所指向的数组下标，输出时要对循环变量进行求余操作（i % capacity）以防数组下标越界。

实际应用

顾客排队取号。

增加Customer.h

#Customer.h
#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.cpp

#include "stdafx.h"
#include "Customer.h"
#include "iostream"

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;
}

修改MyQueue.h：

#MyQueue.h
#ifndef MYQUEUE_H
#define MYQUEUE_H

#include "Customer.h"

class MyQueue
{
public:
    MyQueue(int queueCapacity);  //创建队列
    virtual ~MyQueue();          //销毁队列
    void ClearQueue();           //清空队列
    bool QueueEmpty() const;     //判空队列
    bool QueueFull() const;      //判满队列
    int QueueLength() const;     //队列长度
    bool EnQueue(Customer element);   //新元素入队   #<-here
    bool DeQueue(Customer &element);  //首元素出队  #<-here
    void QueueTraverse();        //遍历队列
private:
    Customer *m_pQueue;               //队列数组指针  #<-here
    int m_iQueueLen;             //队列元素个数
    int m_iQueueCapacity;        //队列数组容量
    int m_iHead;
    int m_iTail;
};

#endif

修改MyQueue.cpp

#include "stdafx.h"
#include "MyQueue.h"
#include "iostream"
#include "Customer.h"

using namespace std;

MyQueue::MyQueue(int queueCapacity)
{
    m_iQueueCapacity = queueCapacity;
    m_pQueue = new Customer[m_iQueueCapacity];  #<-here
    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
{
    return m_iQueueLen == 0 ? true : false;
}

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

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

bool MyQueue::EnQueue(Customer 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(Customer &element)
{
    if (QueueEmpty())
    {
        return false;
    }
    else
    {
        element = m_pQueue[m_iHead];
        m_iHead++;
        m_iTail = m_iTail % m_iQueueCapacity;
        m_iQueueLen--;
        return true;
    }
}

void MyQueue::QueueTraverse()
{
    for (int i = m_iHead; i < m_iQueueLen + m_iHead; i++)  //保证循环次数为m_iQueueLen
    {
        m_pQueue[i%m_iQueueCapacity].printInfo();  #<-here
        cout << "前面还有" << (i - m_iHead) << "人" << endl;  #<-here
        cout << endl;
    }
}

测试：

#demo_queue.cpp
#include "stdafx.h"
#include "stdlib.h"
#include <iostream>

#include "MyQueue.h"
#include "Customer.h"

using namespace std;

int main(void)
{
    MyQueue *p = new MyQueue(4);
    Customer c1("zhangsan", 20);
    Customer c2("lisi", 30);
    Customer c3("wangwu", 25);

    p->EnQueue(c1);
    p->EnQueue(c2);
    p->EnQueue(c3);
    p->QueueTraverse();

    Customer c4("", 0);
    p->DeQueue(c4);
    c4.printInfo();
    cout << endl;

    p->QueueTraverse();

    delete p;
    p = NULL;

    system("pause");
    return 0;
}

运行结果：

【慕课-数据结构-C++语言】队列篇

队列原理

面向对象的队列设计

环形队列的实现

实际应用

猜你喜欢

热点阅读