数据结构（C++实现）--队列

队列queue

• 先进先出FIFO
  数组描述

1. location(i) = i-1

   
   queue1

增加元素 rear+1 O(1)
空队列rear=-1
删除元素1~rear位置的元素全部左移1位 O(n)

2. location(i) = location(1)+i-1

   
   queue2

增删都是O(1)，空队列有rear<front

3. location(i) = ( location(1)+i-1)%MaxSize

   
   queue3

即环形队列
因为空和满时都有front=rear，所以队列不能满

给出3的实现

#include <iostream>
#include "err.h"

using namespace std;

template<class T>
class Queue
{
public:
    Queue(int MaxQueueSize = 10);
    ~Queue() {delete [] queue;}
    bool IsEmpty() const {return front==rear;}
    bool IsFull() const {return(((rear+1)%MaxSize==front)?1:0);}
    T First() const;
    T Last() const;
    Queue<T>& Add(const T&x);
    Queue<T>& Delete(T& x);
private:
    int front;
    int rear;
    int MaxSize;
    T *queue;
};
template<class T>
Queue<T>::Queue(int MaxQueueSize)
{
    MaxSize = MaxQueueSize + 1;   //多申请一个空间，保证队列不会满
    queue = new T[MaxSize];
    front = rear = 0;
}

template<class T>
T Queue<T>::First() const
{
    if (IsEmpty()) throw OutOfBounds();
    return queue[(front+1)%MaxSize];
}

template<class T>
T Queue<T>::Last() const
{
    if(IsEmpty()) throw OutOfBounds();
    return queue[rear];
}
template<class T>
Queue<T>& Queue<T>::Add(const T& x)
{
    if(IsFull()) throw NoMem();
    rear = (rear+1)%MaxSize;
    queue[rear] = x;
    return *this;
}
template<class T>
Queue<T>& Queue<T>::Delete(T& x)
{
    if(IsEmpty()) throw OutOfBounds();
    front = (front+1)%MaxSize;
    x = queue[front];
    return *this;

}
int main()
{
    Queue<int> q(10);
    cout << (q.IsEmpty()?"Empty":"Not Empty");
    cout << q.Last();
    return 0;
}