博客

一、学习要点：

1.队列的特点：

a.先进先出

b.插入只能从队尾插入

c.删除只能从对头删除

d.双向操作

2.队头指针与队尾指针的区别，队头指针指向实际队首，还是队首空位，以及队尾指针是指向实际队尾，还是实际队尾的下一个空位都是事先约定的，之所以这样，是因为如果队首和队尾都指向实际指针时，当队列为空和队列为1个元素时，队首指针和队尾指针完全一样，故其中必有一个指向实际队尾的后一位。

3.队列为满时，


队列的最后一位必为空，而且不存放元素


。

4.队列和栈一样是一种线性结构，其底层基础都是线性数组和链表，基于数组队列的缺点是由于一端插入一端删除，当不断从头部删除数据，头部会大量留有空闲内存，无法插入，造成空间流失，如果将队头指针在每次删除之后往前移动一个位置，这是一个时间复杂度为O(n)的操作.为解决这个要么空间浪费要么时间浪费的问题，使用循环队列，所谓循环队列，是将一个数组看出首尾相连的圆环，删除元素时将队首标志往后移动，添加元素时若数组尾部已经没有空间，则考虑数组头部的空间是否空闲，如果是，则在数组头部插入。

二、代码：

demo092003.cpp

#include<iostream>
#include<stdlib.h>
using namespace std;
template<class T>
class Loopqueque{
public:
Loopqueque(int c);
~Loopqueque();
bool isEmpty();
bool isFull();
int size();
bool push(T t);
bool pop();
T front();//队首指向的元素
private:
int begin;//队首指针
int end;//队尾指针
T *queque;//队列底层数组
int capacity;//队列容量
}
template<class T>
Loopqueque<T>::Loopqueque(int c):begin(0),end(0),capacity(c){
	queque=new T[capacity];
}
template<class T>
Loopqueque<T>::~Loopqueque(){
	delete []queque;
}
template<class T>
bool Loopqueque<T>::isEmpty(){
	if(begin==end){
		return true;
	}else{
		return false;
	}
}
template<class T>
bool Loopqueque<T>::isFull(){
	if(((end+1)%capacity)==begin){
		return true;
	}else{
		return false;
	}
}
template<class T>
int Loopqueque<T>::size(){
	return((end-begin+capacity)%capacity);
}
template<class T>
bool Loopqueque<T>::push(T t){
	if((end+1)%capacity==begin){
		return false;
	}else{
		queque[end]=t;
		end=(end+1)%capacity;
		return true;
	}
}
template<class T>
bool Loopqueque<T>::pop(){
	if(first==end){
		return false;
	}else{
		begin=(begin+1)%capacity;
		return true;
	}
}
template<class T>
T Loopqueque<T>::front(){
	if(begin==end){
	return false;
	}else{
	return queque[begin];
	}
}

调用代码：

#include<iostream>
#include<stdlib.h>
#include<string>
#include"demo092303.cpp";
using namespace std;
int main(){
	Loopqueque<string> queque(6);
	queque.push("one");
	queque.push("two");
	queque.push("three");
	queque.push("four");
	queque.push("five");
	cout<<"队列长度:"<<queque.size()<<endl;
	cout<<queque.isFull()<<endl;
	while(!queque.isEmpty()){
		queque.pop;
	}
	cout<<queque.isEmpty()<<endl;
	system("pause");
	return 0;
}

三、运行结果：