数据结构探险——环形队列篇

    xiaoxiao2022-07-05  168

    @这篇文档是由C++代码实现的环形队列

    数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。队列就是先进先出的一种数据结构,环形队列只是将队尾元素与队头元素连接在了一起,要记住的就是队头指针永远指向的是存放队头的那个数组的下标,而队尾指针指向的是队尾元素的下一个数组的下标。

    本文是以Visual Studio中新建的C++win32的控制台应用程序实现的,其中建立了头文件和源文件以及实现main()的demo文件,分别是MyQueue.h和MyQueue.cpp和demo.cpp文件。

    Customer.h文件

    #ifndef CUSTOMER_H #define CUSTOMER_H #include <iostream> 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 "Customer.h" #include <iostream> #include <string> 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文件

    #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(int element); //bool DeQueue(int &element); bool EnQueue(Customer element); bool DeQueue(Customer &element); bool QueueTraverse(); private: //int *m_pQueue; //队列数组指针 Customer *m_pQueue; int m_iQueueLen; //队列元素个数 int m_iQueueCapacity; //队列数组容量 int m_iHead; //队列头指针 int m_iTail; //队列尾指针 }; #endif

    MyQueue.cpp

    #include "MyQueue.h" #include "Customer.h" #include <iostream> using namespace std; //队列的构造函数 MyQueue::MyQueue(int queueCapacity) { m_iQueueCapacity = queueCapacity; //初始化队列的容量 //m_iHead = 0; //初始化队列的头指针指向位置 //m_iTail = 0; //初始化队列的尾指针指向位置 //m_iQueueLen = 0; //初始化队列的长度 ClearQueue(); //调用ClearQueue()的方法初始化队列,相当于上面的三行代码的操作 m_pQueue = new Customer[queueCapacity]; //初始化存放队列的数组 } //队列的析构函数 MyQueue::~MyQueue() { delete []m_pQueue; m_pQueue = NULL; } //队列的清空函数 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; } //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()) { cout << "队列已满,不能再插入元素!" << endl; return false; } else { //m_pQueue[QueueLength()-1] = element; //个人的想法,其实QueueLength()-1和m_iTail的值是相同的。 //再思考之后发现他们的值不一样,还是用m_iTail要好一些。因为有可能m_iHead=2,m_iTail=0。 //而此时的QueueLength()-1=m_iQueueCapacity-2(环形队列),所以不能用QueueLength()-1。 m_pQueue[m_iTail] = element; m_iTail++; m_iTail = m_iTail%m_iQueueCapacity; m_iQueueLen++; //cout << m_iHead << "," << m_iTail << endl; return true; } } //队列删除元素的函数 bool MyQueue::DeQueue(Customer &element) { if(QueueEmpty()) { cout << "队列为空,不能再取元素!" << endl; return false; } else { element = m_pQueue[m_iHead]; m_iHead++; m_iHead = m_iHead%m_iQueueCapacity; m_iQueueLen--; //cout << m_iHead << "," << m_iTail << endl; return true; } } //遍历队列的成员的函数 bool MyQueue::QueueTraverse() { if(QueueEmpty()) { cout << "队列为空,遍历不出任何元素!" << endl; return false; } else { //存在一个问题就是当m_iHead=3,而m_iQueueLen=2,m_iQueueCapacity=4的时候,i肯定是不小于m_iQueueLen的值的,所以不能打印出来队列的成员。此时的m_iTail=1, for(int i=m_iHead; i<m_iHead+m_iQueueLen;i++) { //cout << m_pQueue[i%m_iQueueCapacity] << endl; m_pQueue[i%m_iQueueCapacity].printInfo(); cout << "前面还有" << (i-m_iHead) << "人" << endl; cout << endl; } //cout << m_iHead << "," << m_iTail << endl; return true; } }

    demo.cpp文件

    #include <iostream> #include <stdlib.h> #include "Customer.h" #include "MyQueue.h" using namespace std; int main(void) { //MyQueue *p = new MyQueue(4); //p->EnQueue(10); //p->EnQueue(12); //p->EnQueue(16); //p->EnQueue(18); //p->EnQueue(20); //cout << "循环遍历队列:" << endl; //p->QueueTraverse(); cout << p->m_iHead << "," << p->m_iTail << endl; // //int e = 1; //p->DeQueue(e); //cout << endl; //cout << "删除的元素:" << endl; //cout << e <<endl; //cout << endl; // //cout << "删除元素后循环遍历队列:" << endl; //p->QueueTraverse(); //cout << endl; // //cout << "清空队列后循环遍历队列:" << endl; //p->ClearQueue(); //p->QueueTraverse(); //cout << endl; //p->EnQueue(50); //p->EnQueue(60); //cout << "重新插入元素后遍历队列:" << endl; //p->QueueTraverse(); //delete [4]p; //p=NULL; MyQueue *p = new MyQueue(100); Customer c1("张三", 18); Customer c2("李四", 19); Customer c3("王五", 20); Customer c4("赵六", 21); p->EnQueue(c1); p->EnQueue(c2); p->EnQueue(c3); p->EnQueue(c4); //cout << "循环遍历队列:" << endl; cout << endl; p->QueueTraverse(); cout << endl; Customer c5("",0); p->DeQueue(c5); Customer c6("",0); p->DeQueue(c6); Customer c7("郑七", 22); Customer c8("黄八", 23); p->EnQueue(c7); p->EnQueue(c8); //cout << "打印出删除的元素:" << endl; //cout << endl; //c4.printInfo(); cout << endl; cout << "循环遍历队列:" << endl; cout << endl; p->QueueTraverse(); delete p; p = NULL; system("pause"); return 0; }

    这个操作让我想到删除硬盘上的东西是不是只是移动了指针,而没有真正的删除已存储的东西。如果再次往里面存东西只是说覆盖了之前存储的东西,所以说如果硬盘上的东西如果不小心删除了,只要再不往里面存东西,是可以有办法恢复之前存储的东西的,当然硬盘存储可能根本不是队列,但原理应该差不多。

    最新回复(0)