数据结构与算法-循环队列

在顺序队列出队列的时候，数组前面会有空余的空间，我们可以将数据往前搬移，提高空余空间的使用，但是效率比较低；我们可以使用循环队列来提高效率。

Head代表队列头，Tail代表队列尾，n代表队列的长度，如果Head与Tail大于等于n的时候就是到了循环点，可以将Head或者Tail余n来代表当前n内的位置。

一开始空余的循环队列，Head和Tail的位置

当有四个元素(a,b,c,d)入队，Head和Tail的位置

当所有元素出队后，Head与Tail是相等的，就是空队列

当满队列，Head和Tail的位置，可以看到Tail的位置是空余的，如果再加入一个元素的话就导致head与tail相等，判断条件是(Tail + 1) % n==Head

代码实现

template<class T>
class MyCircularQueue {
public:
    MyCircularQueue(int nQueueSize);
    ~MyCircularQueue();

    bool empty() const;
    int size() const;
    void pop();
    T front() const;
    T back() const;
    bool push(T const&);

protected:
    T* m_pArrayQueue;
    int m_nQueueSize;
    int m_nHead;
    int m_nTail;
    int m_nNumSize;
};

template<class T>
MyCircularQueue<T>::MyCircularQueue(int nQueueSize) {
    m_nQueueSize = nQueueSize;
    m_pArrayQueue = new T[nQueueSize];
    m_nHead = 0;
    m_nTail = 0;
    m_nNumSize = 0;
}

template<class T>
MyCircularQueue<T>::~MyCircularQueue() {
    delete[] m_pArrayQueue;
}

template<class T>
bool MyCircularQueue<T>::empty() const {
    if(m_nHead == m_nTail) {
        return true;
    }
    return false;
}

template<class T>
int MyCircularQueue<T>::size() const {
    return m_nNumSize;
}

template<class T>
void MyCircularQueue<T>::pop() {
    if(m_nHead == m_nTail) {
        return ;
    }
    m_nHead = (m_nHead + 1) % m_nQueueSize;
    m_nNumSize--;
}

template<class T>
T MyCircularQueue<T>::front() const {
    return m_pArrayQueue[m_nHead];
}

template<class T>
T MyCircularQueue<T>::back() const {
    return m_pArrayQueue[(m_nHead + m_nNumSize - 1) % m_nQueueSize];
}

template<class T>
bool MyCircularQueue<T>::push(T const& param) {
    if((m_nTail + 1) % m_nQueueSize == m_nHead) {
        return false;
    }
    m_pArrayQueue[m_nTail] = param;
    m_nTail = (m_nTail + 1) % m_nQueueSize;
    m_nNumSize++;
    return true;
}

可关注公众号"程序员的面试题",了解更多的面试技巧

数据结构与算法-循环队列

推荐阅读