数据结构-队列

队列是一种先进先出(FIFO)的数据结构,与栈(后进先出LIFO)不同,但两者都是线性结构,因此可以用线性表去描述队列,本文主要是用数组去实现一个简单的队列

队列

对一个队列操作,只能从队首删除元素,队尾插入元素,因此我们可以定义两个队列元素指针front,back,用于跟踪队列首尾元素。
C++ STL实现了队列数据结构,我们用时不可能立即手写一个队列,因而只需include头文件即可,不过对于队列这一数据结构原理还是要理解的

我们知道,队列可以用数组或链表实现,不过本文是以数组来讲述的因此较为简单

插入

队列插入一个元素时,先将队尾指针back+1,使其指向下一个空闲区
域,然后在插入元素。复杂度为O(1)

删除

删除队首元素有两种策略

  1. 直接整个数组左移一位,front不变,back向前移动一位。复杂度O(n)
  2. 数组不移动,front移动到下一位,back不变。复杂度O(1)

显然删除操作情况1不能接受,然而对于删除操作情况2,会导致数组空间浪费,这是因为front指针之前的区域未能被利用,而back指针之后的区域显然不够(这里在没有考虑数组变增的情况下)。

如果将数组“串”起来怎样?事实上确实可以,这种数组叫环形数组,用此类型数组实现的队列称为循环队列 且其插入删除复杂度均为O(1)

环形数组表示队列通过下面公式实现:

location(i)=(location(front)+i)%arrayLength

如下图一个空队列,此时 front=back

当插入一个元素时,也有两种策略

1.先移动back,后插入元素。那么front指向元素为"空"
2.先插入元素,后移动back。那么back指向元素为"空"

每次插入都需要判断 (back+1)%size == front ,为什么?我们知道,初始时front=back表示空队列,那么当插入元素数量达到数组长度此时front=back!这表示这个队列满的还是空的?因此我们预留一个位置,也就是队列不能插满。即

front=back 空队列
(back+1)%size = front 满队列

如何获取队列中第n个元素在数组中的下标?
假设front=10,back=4。

因此我们用C++实现该循环队列

队列实现

队列抽象数据类型

1
2
3
4
5
6
7
8
9
10
11
template<class T>
class QueueBase{
public:
virtual ~QueueBase(){}
virtual void push_back(const T &)=0;
virtual void pop_front()=0;
virtual T & front()=0;
virtual T & back()=0;
virtual bool empty()=0;
virtual int size()=0;
};

之后在另外定义一个派生类继承QueueBase接口。
我是按照策略2来插入元素的,代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
template<class T>
class arrayQueue{
private:
T *m_array;
int m_capacity;
int front;
int back;
public:
arrayQueue(int initCapacity=10){
m_capacity=initCapacity;
m_array=new T[m_capacity];
front=0;
back=0;
}
~arrayQueue(){delete []m_array;}
void push_back(const T &);
void pop_front();
T & Front(){
return m_array[front];
}
T & Back(){
return m_array[back-1];
}
bool empty(){return front==back;}
int size(){
if(front<back)
return back-front;
else
return back+m_capacity-front;
}
void changeLength(T* &,int,int);
void output(){
if(empty())return;
// 情况1
if(front<back){
for (int i = front; i < back; i++){
cout<<"["<<i<<"] "<<m_array[i]<<"\n";
}
// 情况2
}else{
for (int i = front; i < m_capacity; i++){
cout<<"["<<i<<"] "<<m_array[i]<<"\n";
}
for (int i = 0; i < back; i++){
cout<<"["<<i<<"] "<<m_array[i]<<"\n";
}
}
}
};

template<class T>
void arrayQueue<T>::push_back(const T &element){
// 满队列
if((back+1)%m_capacity==front){
// 数组倍增
changeLength(m_array,m_capacity,m_capacity*2);
m_capacity*=2;
}
// 按照策略2插入: 先插入元素,后移动back
m_array[back]=element;
// 注意,此处不能直接 back++,这样做会使back超出数组长度从而导致数组访问越界
// 相反,(back+1)%m_capacity 会使back指针回到数组起始处继续插入
back=(back+1)%m_capacity;
}
template<class T>
void arrayQueue<T>::pop_front(){
// 判空
if(back==front)return;
m_array[front].~T();
// 同样这里也是控制front只能处于数组之间
front=(front+1)%this->m_capacity;
}
template<class T>
void arrayQueue<T>::changeLength(T* &array,int oldLength,int newLength){
if(newLength<0)return;
T* temp=new T[newLength];
// 从有效元素开始复制
if(front<back)
// 没有形成环
std::copy(array+front,array+back,temp);
else{
// 形成环
std::copy(array+front,array+oldLength,temp);
std::copy(array,array+back,temp+oldLength-front);
// 重新设置front,back
front=0;
back=oldLength-1;
}
delete []array;
array=temp;
}

我认为比较难理解的是changeLength改变数组长度函数,其实用一张图表示就很简单了

测试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<iostream>
using namespace std;
int main(){
arrayQueue<int>q(5);
q.push_back(1);
q.push_back(2);
q.push_back(3);
q.push_back(4);
q.push_back(40);
q.push_back(400);
q.push_back(4000);
q.push_back(40000);

q.pop_front();
q.pop_front();
q.pop_front();
q.pop_front();
q.pop_front();
q.pop_front();

q.push_back(5);
q.push_back(6);
q.push_back(7);
q.push_back(8);
q.push_back(9);

q.output();
cout<<"size: "<<q.size()<<endl;
cout<<"front: "<<q.Front()<<endl;
cout<<"back: "<<q.Back()<<endl;
return 0;
}

输出

1
2
3
4
5
6
7
8
9
10
[6] 4000
[7] 40000
[8] 5
[9] 6
[0] 7
[1] 8
[2] 9
size: 7
front: 4000
back: 9

STL queue

将自己写的arrayQueue和STL queue分别测试,看看谁快些,这里我仅仅测试了先插入完成后再删除。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
int main(){
arrayQueue<int>q2;
int n=100000000;
CClock::start_timeclock();
for (int i = 0; i < n; i++){
q2.push_back(i);
}
for (int i = 0; i < n; i++){
q2.pop_front();
}
q2.output();
CClock::stop_timeclock();
auto t1=CClock::time_duration();

CClock::start_timeclock();
queue<int>q3;
for (int i = 0; i < n; i++){
q3.push(i);
}
for (int i = 0; i < n; i++){
q3.pop();
}
CClock::stop_timeclock();
auto t2=CClock::time_duration();

cout<<"arrayQueue: "<<t1<<endl;
cout<<"queue: "<<t2<<endl;
}

输出结果,单位秒

1
2
arrayQueue: 2.32446
queue: 2.63278

不知道该如何表达…
(⊙o⊙)…

结尾

bye~