循环队列Queue--使用顺序存储结构(数组)实现

时间:2022-07-17 17:38:14

本人之前总是看,但是上手写代码少。就是那种眼高手低的(汗)。这段时间有空,就来补补吧,从基础开始...

希望能够坚持下去。

数据成员:

头索引:front

尾索引:rear

判断条件:

判断队列“空”: front == rear

判断队列“满”:(rear + 1) % MAX_SIZE == front, 头和尾之间,保留一个元素空间;

计算队列长度:

(rear - front + MAX_SIZE) % MAX_SIZE


示例代码:

#include <limits>
#include <stdlib.h>
#include <time.h>


#define MAX_SIZE (10)
#define RAMDOM(x) (rand() % 100)
typedef int QElement;


class SqQueue
{
public:
SqQueue()
{
InitQueue();
}
~SqQueue() {}

void InitQueue()
{
front = 0;
rear = 0;

for (int i = 0; i < MAX_SIZE;++i)
{
data[i] = std::numeric_limits<int>::max();
}
}

int QueueLength()
{
return (rear - front + MAX_SIZE) % MAX_SIZE;
}

int InQueue(QElement e)
{
//判断队列满
if ((rear + 1) % MAX_SIZE == front)
{
return -1;
}

data[rear] = e;
rear = (rear + 1) % MAX_SIZE;

return 0;
}


int OutQueue(QElement *e)
{
//判断队列空
if (front == rear) return -1;

*e = data[front];
data[front] = std::numeric_limits<int>::max();
front = (front + 1) % MAX_SIZE;

return 0;
}


void PrintQueue()
{
if (rear > front)
{
for (int i = front; i < rear; ++i)
{
printf("data[%03d] : %d \n", i, data[i]);
}

else
{
for (int i = front; i < MAX_SIZE; ++i)
{
printf("data[%03d] : %d \n", i, data[i]);
}


for (int i = 0; i < rear; ++i)
{
printf("data[%03d] : %d \n", i, data[i]);
}
}

printf("---------------\n");
}
private:
QElement data[MAX_SIZE];
int front;
int rear;
};

int main()
{
SqQueue q;
srand(time(0));

//插入8个元素
for (int i = 0; i < 8; i++)
{
q.InQueue(RAMDOM(100));
}
q.PrintQueue();

//删除2个元素
QElement e;
q.OutQueue(&e);
q.OutQueue(&e);
q.PrintQueue();

//再插入3个元素
for (int i = 0; i < 3; i++)
{
q.InQueue(RAMDOM(100));
}
q.PrintQueue();

return 0;
}