寒假来了,把这学期学习的东西总结一下吧。
队列的基本性质就不说了,主要讲一下在静态数组实现中的入队出队操作以及最基本的构造函数等。
目录
一、主要问题:
由于数组大小是固定的,在一系列的入队、出队操作后,队尾可能已经到数组的最后了,而队头前面还有位置,这时我们就应该把新入对的元素放在前面,形成一个环一样的结构,如下图所示。
1.将70、80、50入队:
2.将70、80出队:
3.将90、60入队:
这时队尾已经到最后了,接下来再入队时要把元素放在前面的空位,这样就像一个圆环一样。
二、代码实现:
2.1 概述:
#pragma once
#include<iostream>
using namespace std;
#define CAPACITY 16//数组的大小
class Queue
{
private:
int *myqueue;//数组实现的队列
int front;//队列头下标
int back;//队列尾的下一个可以插入数据的地方的下标
public:
Queue() :front(0), back(0),myqueue(new int[CAPACITY]) {};//无参构造函数
Queue(const Queue& origin);//复制构造函数
~Queue();
bool empty() const;//判空
bool full() const;//判满
void display();//打印数据
bool enqueue(int newdata);//入队
bool dequeue();//出队
};
实现的功能已在代码中注释。
2.2 构造函数:
1.无参构造函数:
该函数在概述中已写出,将头和尾都置为0,并为数组开辟一个[CAPACITY]这么大的空间。
2.复制构造函数:
Queue::Queue(const Queue& origin)
{
if (!origin.empty())
{
int index = origin.front;//用于遍历的下标
myqueue = new int[CAPACITY]();//开辟空间
while (index != origin.back)//遍历赋值
{
this->myqueue[index] = origin.myqueue[index];//赋值
index = (index + 1) % CAPACITY;
}
}
}
在复制构造函数中我们将原数组的值一个一个赋给新数组,要注意的是在origin的back在front前面的情况下当遍历的下标index达到数组的最后时就要回到数组的0下标处接着继续赋值,而这一步通过代码
index = (index + 1) % CAPACITY;
实现,当index在增加后超出了数组的大小时就要回到数组的0下标处,这个操作在之后的入队出队中也有出现。
2.3 析构函数:
很简单的析构,当数组有开辟的空间时把该空间delete就可以了。
Queue::~Queue()
{
if(myqueue != NULL)
delete []myqueue;
myqueue = NULL;
front = 0;
back = 0;
}
2.4 判空:
定义队列为空的条件为front和back相同。
bool Queue::empty() const
{
return (front == back);
}
2.5 判满:
为了不和判空的条件冲突,定义队列为满的条件为back的下一个位置为front。
bool Queue::full() const
{
return ((back + 1) % CAPACITY == front);
}
这里也涉及到了静态数组的循环,如果back已经在最后的位置了,那么back的下一个位置就是0下标处,所以这里需要做一个取余操作。
2.6 入队:
bool Queue::enqueue(int newdata)
{
if (full()) return false;//已经满了就返回false
myqueue[back] = newdata;//在back处加入新数据
if (++back == CAPACITY) back %= CAPACITY;//back向后移,
//如果移动后back到数组的最后那就将back放在开始的0下标处
return true;
}
这里同样有取余操作。
2.7 出队:
bool Queue::dequeue()
{
if (empty()) return false;//如果队列为空就返回false
if (++front == CAPACITY) front %= CAPACITY;
return true;
}
因为是数组实现,出队的操作只是简单地把front增大1,在这里同样当front到数组的最后时要把front重新放在0下标处。