普通队列费时间费空间

环形队列优先级比普通队列高，可以充分利用空间

两种队列处理方式，各有优劣，更具具体的情况处理

内存占用少，但是效率低下
内存占用多，效率较高。

使用环形队列处理，head/tail;采用顺时针或逆时针皆可，当队头队尾在使用是具有高效低内存的优点，不适用顺序队列。使用环形队列作为编码典范。（应用：自动排号机）

队列的用途

/********************************

********     环形队列     *******

*********************************/

#ifndef MYQUEUE_H_

#define MYQUEUE_H_

#include <iostream>

using namespace std;

const int DefaultCapacitySize = 20;

template <typename T>

class MyQueue

{

public:

MyQueue();

~MyQueue();

bool ClearQueue() ; // 清空队列

bool IsEmpty() ;  // 判断队列是否为空

bool IsFull(); // 判断队列是否为满

int QueueLen(); // 返回队列长度

bool InsertQueue(const T elem); // 插入元素

bool DeleteQueue(T & elem); // 删除元素

bool TraverseQueue() ;  // 遍历队列

private:

T * m_data;  // 存放数据

int iHead;   // 指向队列头部

int iTail;   // 指向队列尾部

int m_capacity; // 队列容量

int m_length;   // 队列长度

};

// 构造函数

template <typename T>

MyQueue<T>::MyQueue()

{

m_data = new T [DefaultCapacitySize];

iHead = 0;

iTail = 0;

m_capacity = DefaultCapacitySize;

m_length = 0;

}

// 析构函数

template <typename T>

MyQueue<T>::~MyQueue()

{

delete [] m_data;

m_data = NULL;

}

// 清空队列

template <typename T>

bool MyQueue<T>::ClearQueue() 

{

m_length = 0;

iHead = 0;

iTail = 0;

return true;

}

// 判断队列是否为空

template <typename T>

bool MyQueue<T>::IsEmpty() 

{

return (m_length == 0) ? true : false;

}

// 判断队列是否为满

template <typename T>

bool MyQueue<T>::IsFull() 

{

return (m_length == m_capacity) ? true : false;

}

// 返回队列长度

template <typename T>

int MyQueue<T>::QueueLen() 

{

return m_length;

}

// 插入元素

template <typename T>

bool MyQueue<T>::InsertQueue(const T elem) 

{

if (IsFull())

return false;

m_data[iTail] = elem;

iTail++;

iTail %= m_capacity;

m_length++;

return true;

}

// 删除元素

template <typename T>

bool MyQueue<T>::DeleteQueue(T & elem) 

{

if (IsEmpty())

return false;

elem = m_data[iHead];

iHead++;

iHead %= m_capacity;

m_length--;

return true;

}

// 遍历队列

template <typename T>

bool MyQueue<T>::TraverseQueue() 

{

if (IsEmpty())

return false;

for (int i = iHead; i < m_length + iHead; i++)

{

cout << m_data[i % m_capacity] << "   ";

}

cout << endl;

return true;

}

#endif

1.环形队列入队 head++; head = head % capacity; 2.环形队列出队 tail++; tail = tail % capacity; 3.遍历环形队列时要注意循环变量应初始化为队首指针所指向的数组下标，输出时要对循环变量进行求余操作(i % capacity)以防数组下标越界问题的发生 for(int i = head; i < length + head; i++)  cout<<QueueData[i % capacity]<<"  ";

class MyQueue { // 注释：讲解一些 C 语言用法 public: MyQueue(int queueCapacity); // InitQueue(&Q) 创建队列 virtual ~MyQueue(); // DestoryQueue(&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; // 队列数组容量 };

普通队列存在的缺点： 1、若是一个元素出队列后，其他元素统一前移，补充空位，则时间效率降低。 2、若是一个元素出队列后，其他元素位置保持不变，空位保留，则空间利用率低。

队列：先入先出。

#include <iostream>
#include <string>

using namespace std;


class Customer{
public:
	Customer(){
		//需要默认构造函数
	}
	
	Customer(string name, int age){
		m_strName = name;
		m_iAge = age;
	}

	void printInfo() const{
		cout << "姓名: " << m_strName << endl;
		cout << "年龄: " << m_iAge << endl;
		cout << endl;
	}
	
private:
	string m_strName;
	int m_iAge;
};




template <class T>
class MyQueue{
public:
	MyQueue(int queueCapacity){
		m_iQueueCapacity = queueCapacity;
		m_iQueueLen = 0;
		m_iHead = 0;
		m_iTail = 0;
		m_pQueue = new T[queueCapacity];
	}
	
	~MyQueue(){
		delete[] m_pQueue;
	}
	
	void QueueClear(){
		m_iQueueLen = 0;
		m_iHead = 0;
		m_iTail = 0;
	}
	
	bool QueueEmpty() const{
		if(m_iQueueLen==0){
			return true;
		}
		else{
			return false;
		}
	}
	
	bool QueueFull() const{
		if(m_iQueueLen==m_iQueueCapacity){
			return true;
		}
		else{
			return false;
		}
	}
	
	bool EnQueue(T element){
		if(QueueFull()){
			return false;
		}
		else{
			m_pQueue[m_iTail] = element;
			m_iTail ++;
			m_iTail = m_iTail % m_iQueueCapacity;
			m_iQueueLen ++;
			return true;
		}
	}
	
	bool DeQueue(T &element){
		if(QueueEmpty()){
			return false;
		}
		else{
			element = m_pQueue[m_iHead];
			m_iHead ++;
			m_iHead = m_iHead % m_iQueueCapacity;
			m_iQueueLen --;
			return true;
		}
	}
	
	void QueueTraverse(){
		for(int i = m_iHead; i < m_iHead + m_iQueueLen; i++){
			m_pQueue[i%m_iQueueCapacity].printInfo();
		}
	}
	
private:
	T* m_pQueue;
	int m_iHead;
	int m_iTail;
	int m_iQueueLen;
	int m_iQueueCapacity;
};





int main(int argc, char *argv[]) {
	MyQueue<Customer>* p = new MyQueue<Customer>(4);
	p->EnQueue(Customer("imooc", 20));
	p->QueueTraverse();
}

1

请输入笔记内容...