顺序队列-------队头移动
队列概念:
队列允许在队尾插入,队头删除,具有先进先出的特性。
上一篇讲述了顺序队列中的队头不动,现在讲述队头移动的队列。
如上图所示,这是队头移动的,意味着这个顺序队列进行删除时,队头指向会越来越靠后,队头指向之前将会是空,意味着最终将会导致看似队列已满,实则有多余空间,但是已经无法入队。如下图所示
顺序队列之队头移动
优点:解决了数据搬移的耗时问题
缺点:会造成假溢出现象。
//顺序队列,队头移动,会 出现假溢出现象
#include<iostream>
#include<assert.h>
using namespace std;
typedef int typedata;
#define max_size 100
typedef class Seqlist2{
public:
Seqlist2(int front = 0, int rear = 0)
:_front(front),
_rear(rear)
{}
int Size()
{
return _rear - _front;
}
//入队列,队尾插入
bool push_back(typedata data)
{
if (_rear==max_size)
{
cout << "队列已满" << endl;
if (is_flase())
cout << "假溢出" << endl;
return false;
}
array[_rear++] = data;
return true;
}
//出队列,队头删除
bool pop_front()
{
if (Size() == 0)
return false;
_front++;
return true;
}
//判断是否假溢出
bool is_flase()
{
if (_rear == max_size && Size() < max_size)
return true;
return false;
}
~Seqlist2()
{
_front = 0;
_rear = 0;
}
void 打印()
{
int i = 0;
cout << "队头:";
int count = 0;
for (i = _front; i < _rear; ++i)
{
count++;
while (count == 10)
{
cout<<endl;
count = 0;
}
cout << array[i] << " ";
}
}
private:
int _front;
int _rear;
typedata array[max_size];
};
#include<time.h>
#include<iostream>
using namespace std;
void time_srandd(int array[], int n)
{
srand((unsigned)time(NULL)); //用当前时间设置种子
int i = 0;
for (; i < n; ++i)
{
array[i] = rand() % n;
}
}
void test()
{
Seqlist2 p;
int array[100];
time_srandd(array, 100);
int i = 0;
for (i = 0; i < 100; ++i)
p.push_back(array[i]);
cout << "Size:" << p.Size() << endl;
p.打印();
cout << endl;
for (i = 0; i < 40; ++i)
p.pop_front();
cout << "Size:" << p.Size() << endl;
p.打印();
for (i = 0; i < 20; ++i)
p.push_back(array[i]);
cout << "Size:" << p.Size() << endl;
p.打印();
}
int main()
{
test();
return 0;
}