队列是一种先进先出(FIFO)的数据结构,与栈(后进先出LIFO)不同,但两者都是线性结构,因此可以用线性表去描述队列,本文主要是用数组去实现一个简单的队列
队列
对一个队列操作,只能从队首删除元素,队尾插入元素,因此我们可以定义两个队列元素指针front,back,用于跟踪队列首尾元素。
C++ STL实现了队列数据结构,我们用时不可能立即手写一个队列,因而只需include头文件即可,不过对于队列这一数据结构原理还是要理解的
我们知道,队列可以用数组或链表实现,不过本文是以数组来讲述的因此较为简单
插入
队列插入一个元素时,先将队尾指针back+1,使其指向下一个空闲区
域,然后在插入元素。复杂度为O(1)
删除
删除队首元素有两种策略
直接整个数组左移一位,front不变,back向前移动一位。复杂度O(n)
数组不移动,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++实现该循环队列
队列实现
队列抽象数据类型
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 ; if (front<back){ for (int i = front; i < back; i++){ cout<<"[" <<i<<"] " <<m_array[i]<<"\n" ; } }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 ; } m_array[back]=element; back=(back+1 )%m_capacity; }template <class T >void arrayQueue<T>::pop_front (){ if (back==front)return ; m_array[front].~T (); 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=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 ; }
输出
[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; }
输出结果,单位秒
arrayQueue : 2 .32446 queue : 2 .63278
不知道该如何表达…
(⊙o⊙)…
结尾
bye~