数据结构03-队列(Queue)


一、什么是队列


队列是一种特殊的线性表,特殊之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作,和栈一样,队列是一种操作受限制的线性表。进行插入操作的端称为队尾,进行删除操作的端称为队头。队列中没有元素时,称为空队列(建立顺序队列结构必须为其静态分配或动态申请一片连续的存储空间,并设置两个指针进行管理。一个是队头指针front,它指向队头元素;另一个是队尾指针rear,它指向下一个入队元素的存储位置)。


二、队列具体实现 (C++)


用到了三个文件:MyQueue.hMyQueue.cppDemo.cpp,具体内容如下:


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;

};


MyQueue.cpp

#include "stdafx.h"
#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];
}

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

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

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

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_iQueueCapacity--;
		return true;
	}
}

void MyQueue::QueueTraverse() {
	cout << endl;
	for (int i = m_iHead; i < m_iQueueLen; i++) {
		cout << m_pQueue[i % m_iQueueCapacity] << endl;
	}
	cout << endl;
}



Demo.cpp

#include"stdafx.h"

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

// 实现环形队列

int main(void) {
	
	MyQueue *p = new MyQueue(4); // 队列长度为4

	p->EnQueue(10);
	p->EnQueue(12);
	p->EnQueue(14);
	p->EnQueue(16);
	//p->EnQueue(18);
	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();
	p->QueueTraverse();

	p->EnQueue(20);
	p->EnQueue(51);
	p->QueueTraverse();

	delete p;
	p = NULL;

	system("pause");
	return 0;
}

happysneaker.com

运行结果


三、队列的实际应用


目标就是让队列可以对任意类型的数据进行操作,新加了俩文件“Customer.h、Customer.cpp”,代码如下:


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


然后之前的三个文件有细节要对应修改:

1. demo.cpp这个测试文件的测试内容如下:

happysneaker.com


2. MyQueue.h

happysneaker.com


3.  MyQueue.cpp

#include "stdafx.h"
#include"MyQueue.h"

#include<iostream>
using namespace std;

MyQueue::MyQueue(int queueCapacity) {
	m_iQueueCapacity = queueCapacity;
	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 {
	if (m_iQueueLen == 0) {// 判断长度是否为零即可
		return true;
	} 
	else {
		return false;
	}
}

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

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

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_iHead = m_iHead % m_iQueueCapacity;
		m_iQueueCapacity--;
		return true;
	}
}

void MyQueue::QueueTraverse() {

	for (int i = m_iHead; i < m_iQueueLen + m_iHead; i++) {
		m_pQueue[i % m_iQueueCapacity].printInfo();
	}
	cout << endl;
}


happysneaker.com

运行结果


Unity那些事儿
请先登录后发表评论
  • 最新评论
  • 总共0条评论