首页 > 代码库 > 队列的实现：顺序队列
队列的实现：顺序队列
队列也是一种常见的线性表，它和栈相比有以下不同：
- 队列可以在表的两端进行操作。栈只能在栈顶进行插入和删除。
- 两端允许操作的类型不一样：可以进行删除的一端称为队头，这种操作也叫出队；可以进行插入的一端称为队尾，这种操作也叫入队。总的来说，队头只能出队，队尾只能入队。
队列的示意图：
模拟队列这种数据结构并不是什么难事，但会遇到一些问题，如：
假溢出
队列中明明还有空间，却因为rear已经指向最后，造成无法入队问题，这是假溢出。
解决办法是：使用链式存储，这显然可以。在顺序存储时，我们常见的解决办法是把它首尾相接，构成循环队列，这可以充分利用队列的存储空间。
循环队列示意图：
在上图中，front指向队列中第一个元素，rear指向队列队尾的下一个位置。
但依然存在一个问题：当front和rear指向同一个位置时，这代表的是队空还是队满呢？大家可以想象下这种情景。
解决这种问题的常见做法是这样的：
- 使用一标记，用以区分这种易混淆的情形。
- 牺牲一个元素空间。当front和rear相等时，为空；当rear的下一个位置是front时，为满。
如下图：
下面我们给出循环队列，并采用第二种方式，即牺牲一个元素空间来区分队空和队满的代码.
几个重点：
- front指向队头，rear指向队尾的下一个位置。
- 出队时，front=(front+1)%MAXSIZE；入队时，rear=(rear+1)%MAXSIZE。
- 队为空的判断：front==rear；队为满的判断：(rear+1)%MAXSIZE==front。
代码：
类定义
#include<iostream>
#include<queue>
#include<iomanip>
using namespace std;
#define MAXSIZE 10
typedef int ElemType;
//类定义
class SqQueue //顺序队列
{
private:
ElemType *base;
int front; //队头指针
int rear; //对尾指针
public:
SqQueue(); //构造函数
~SqQueue(); //析构函数
void clear(); //请空队列
bool empty(); //队列是否为空
int size(); //获取队列大小
bool push(const ElemType &); //入队，队为满，返回false
bool pop(); //出队，队为空，返回false
const ElemType top(); //获取队头元素
const ElemType back(); //获取队尾元素
void queueTraverse(); //队列的遍历
};
//类实现
SqQueue::SqQueue() //构造函数
{
base=new ElemType[MAXSIZE];
front=rear=0;
}
SqQueue::~SqQueue() //析构函数
{
delete[]base;
}
void SqQueue::clear() //请空队列
{
rear=front;
}
bool SqQueue::empty() //队列是否为空
{
return front==rear;
}
int SqQueue::size() //获取队列大小
{
return (rear-front+MAXSIZE)%MAXSIZE;
}
bool SqQueue::push(const ElemType &data) //入队，队为满，返回false
{
/*
另一种判断队满的方法
size() == MAXSIZE;
*/
if((rear+1)%MAXSIZE==front) //队满判断
return false;
base[rear]=data;
rear=(rear+1)%MAXSIZE;
return true;
}
bool SqQueue::pop() //出队，队为空，返回false
{
if(empty())
return false;
front=(front+1)%MAXSIZE;
return true;
}
const ElemType SqQueue::top() //获取队头元素
{
if(empty())
{
cerr<<"队空！"<<endl;
exit(0);
}
else
return base[front];
}
const ElemType SqQueue::back() //获取队尾元素
{
if(empty())
{
cerr<<"队空！"<<endl;
exit(0);
}
return
base[(rear-1+MAXSIZE)%MAXSIZE];
}
void SqQueue::queueTraverse() //队列的遍历
{
if(empty())
cout<<"队空，无法遍历！"<<endl;
else
{
int p=front;
while(p!=rear)
{
cout<<setw(4)<<base[p];
p=(p+1)%MAXSIZE;
}
cout<<endl;
}
}主函数int main()
{
cout<<"循环顺序队列演练"<<endl;
SqQueue queue;
ElemType data;
printf("入队，输入0结束！\n");
while(cin>>data && data)
{
if(!queue.push(data))
{
printf("队已满，无法入队了!\n");
break;
}
}
cout<<"遍历"<<endl;
queue.queueTraverse();
cout<<"获取队头元素 "<<queue.top()<<endl;
cout<<"获取队尾元素 "<<queue.back()<<endl;
data=http://www.mamicode.com/77;>运行：
完整代码下载：队列的实现：顺序队列
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。