c++用vector实现定长队列

目录

• • queue实现
  • vector实现

我们可以用queue或vector实现定长队列，但是如果我们有遍历定长队列的需求的话，使用queue不是一个好的选择，因为queue本身不支持直接访问元素。

queue实现

C++中的queue标准库提供了一个简单易用的队列容器，可以用来实现定长队列。下面是一段示例代码：

#include <iostream>
#include <queue>

using namespace std;

int main()
{
    queue<int> q;
    int maxlen = 5; // 队列最大长度

    for(int i = 1; i <= 10; i++)
    {
        if(q.size() == maxlen)
        {
            q.pop();
        }
        q.push(i);

        cout << "队列元素：";
        while(!q.empty())
        {
            cout << q.front() << " ";
            q.pop();
        }
        cout << endl;
    }

    return 0;
}

上述代码中，我们定义了一个queue容器，然后通过循环向队列中添加元素。当队列长度达到最大长度时，就要删除队首元素以保持队列长度不变。最后，我们遍历队列输出所有元素。

vector实现

这里也是用模板泛化一下

#include <iostream>
#include <vector>

using namespace std;

template<typename T>
class FixedQueue {
private:
    vector<T> q;
    size_t size;
public:
    FixedQueue(size_t s) : size(s) {
        q.reserve(size);
    }

    void push(const T& t) {
        if (q.size() >= size) {
            q.erase(q.begin());
        }
        q.push_back(t);
    }

    T pop() {
        T t = q.front();
        q.erase(q.begin());
        return t;
    }

    T& front() {
        return q.front();
    }

    T& back() {
        return q.back();
    }

    bool empty() const {
        return q.empty();
    }

    size_t getSize() const {
        return q.size();
    }

    void clear() {
        q.clear();
    }
};

int main() {
    FixedQueue<int> fq(5);
    fq.push(1);
    fq.push(2);
    fq.push(3);
    fq.push(4);
    fq.push(5);
    fq.push(6);
    fq.push(7);
    cout << fq.front() << endl;
    cout << fq.back() << endl;
    fq.pop();
    cout << fq.front() << endl;
    cout << fq.back() << endl;
    cout << fq.empty() << endl;
    cout << fq.getSize() << endl;
    fq.clear();
    cout << fq.empty() << endl;
    cout << fq.getSize() << endl;
    return 0;
}

在这个FixedQueue类中，pop操作的时间复杂度比较高，因为它需要将队列的头部元素删除，然后将后面的元素向前移动一格，以保持元素的连续性。当队列中的元素较多时，这个操作的时间复杂度会比较高，可能会影响程序的性能。
下面给出一个优化版本：

#include <iostream>
#include <vector>

using namespace std;

template <typename T>
class CircularQueue {
private:
    vector<T> data;
    int head;
    int tail;
    int size;
    int count;
public:
    CircularQueue(int k) {
        data.resize(k);
        head = -1;
        tail = -1;
        size = k;
        count = 0;
    }

    bool enQueue(T value) {
        if (isFull()) {
            deQueue();
        }
        if (isEmpty()) {
            head = 0;
        }
        tail = (tail + 1) % size;
        data[tail] = value;
        count++;
        return true;
    }

    bool deQueue() {
        if (isEmpty()) {
            return false;
        }
        if (head == tail) {
            head = -1;
            tail = -1;
            count = 0;
            return true;
        }
        head = (head + 1) % size;
        count--;
        return true;
    }

    T Front() {
        if (isEmpty()) {
            return T();
        }
        return data[head];
    }

    T Rear() {
        if (isEmpty()) {
            return T();
        }
        return data[tail];
    }

    bool isEmpty() {
        return head == -1;
    }

    bool isFull() {
        return count == size;
    }

    void Print() {
        if (isEmpty()) {
            cout << "Queue is empty." << endl;
            return;
        }
        int i = head;
        cout << "Queue: ";
        while (i != tail) {
            cout << data[i] << " ";
            i = (i + 1) % size;
        }
        cout << data[tail] << endl;
    }

    T Get(int index) {
        if (isEmpty() || index < 0 || index >= count) {
            return T();
        }
        return data[(head + index) % size];
    }
};

测试用例

int main() {
    CircularQueue<int> q(5);
    q.enQueue(1);
    q.enQueue(2);
    q.enQueue(3);
    q.enQueue(4);
    q.enQueue(5);
    q.Print();  // should print "Queue: 1 2 3 4 5"
    q.enQueue(6);
    q.Print();  // should print "Queue: 2 3 4 5 6"
    cout << q.Rear() << endl;  // should return 6
    q.deQueue();
    q.deQueue();
    cout << q.Front() << endl;  // should return 4
    cout << q.isFull() << endl;  // should return false
    cout << q.isEmpty() << endl;  // should return false
    q.Print();  // should print "Queue: 4 5 6"
    cout << q.Get(0) << endl;  // should return 4
    cout << q.Get(1) << endl;  // should return 5
    cout << q.Get(2) << endl;  // should return 6
    cout << q.Get(3) << endl;  // should return 0
    return 0;
}