哈哈

不错66

你要一直

不错

先入先出

普通队列：浪费内存（不移动），处理速度慢（各位都前移一位）

环形队列：充分利用内存空间

普通队列示例

环形队列示意图，弥补普通队列的缺点，可充分利用每个内存空间

#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

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::QueueFull() const
{
 if (m_iQueueLen == m_iQueueCapacity)
 {
  return true;
 }
 else
 {
  return false;
 }
}
bool MyQueue::QueueEmpty() const
{
 if (m_iQueueLen == 0)
 {
  return true;
 }
 else
 {
  return 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_iHead %= m_iQueueCapacity;
  m_iQueueLen--;
  return true;
 }
}
void MyQueue::QueueTraverse()
{
 for (int i = m_iHead; i < m_iQueueLen+ m_iHead; i++)
 {
  cout << m_pQueue[i%m_iQueueCapacity]<<endl;
 }
}

int main()
{
 MyQueue *p = new MyQueue(20);

 p->EnQueue(10);
 p->EnQueue(12);
 p->EnQueue(14);
 p->EnQueue(16);
 p->EnQueue(18);

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

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

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

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

 delete p;
 p = NULL;

 system("pause");
    return 0;
}

#include "Customer.h"
class MyQueue{
public:
    ...
    bool EnQueue(Customer element);
    bool DeQueue(Customer &element);
    ...
private:
    Customer *m_pQueue;
    ...
};
//在MyQueue.cpp中
void MyQueue::QueueTraverse(){
    for(int i=m_iHead;i<m_iQueueLen + m_iHead;i++){
        m_pQueue[i%m_iQueueCapacity].printInfo();
        //printInfo是Customer中的成员函数，打印出Customer的数据成员
    }
}
//使用
MyQueue *p=new MyQueue[4];
Customer c1("zhangsan",20);
p->EnQueue(c1);

队列：先入先出。

#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();
}

Demo.cpp #include "MyQueue.h" #include <iostream> using namespace std; int main() { MyQueue *p = new MyQueue(4); p->EnQueue(10); p->EnQueue(12); p->EnQueue(8); p->EnQueue(3); p->EnQueue(5); p->QueueTravese(); int e = 0; p->DeQueue(e); cout << e << endl; p->DeQueue(e); cout << e << endl; p->QueueTravese(); p->ClearQueue(); p->QueueTravese(); p->EnQueue(20); p->EnQueue(5); int len = p->QueueLength(); cout << len << endl; p->QueueTravese(); delete p; p = NULL; return 0; }

MyQueue.cpp bool MyQueue::DeQueue(int &element) { if (QueueEmpty()) return false; element = m_pQueue[m_iHead]; m_iHead++; m_iHead = m_iHead % m_iQueueCapacity; m_iQueueLen--; return true; } void MyQueue::QueueTravese() { for (int i = m_iHead; i < m_iHead + m_iQueueLen; i++) { cout << m_pQueue[i % m_iQueueCapacity] << " "; } cout << endl; }

MyQueue.cpp #include<iostream> #include "MyQueue.h" using namespace std; MyQueue::MyQueue(int queueCapacity) { m_iQueueCapacity = queueCapacity; m_iHead = 0; m_iTail = 0; m_iQueueLen = 0; m_pQueue = new int[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 { return m_iQueueLen == 0 ? true : false; } bool MyQueue::QueueFull() const { return m_iQueueCapacity == m_iQueueLen ? true : false; } int MyQueue::QueueLength() const { return m_iQueueLen; } bool MyQueue::EnQueue(int element) { if (QueueFull()) return false; m_pQueue[m_iTail] = element; m_iTail++; m_iTail = m_iTail % m_iQueueCapacity; m_iQueueLen++; return true; }

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 QueueTravese(); // 遍历队列 private: int *m_pQueue; // 队列数组指针 int m_iQueueLen; // 队列元素个数 int m_iQueueCapacity; // 队列数组容量 int m_iHead; // 队列头指针 int m_iTail; // 队列尾指针 };