STL队列：实现先进先出数据结构

发布时间：2023-05-13

STL（Standard Template Library）是C++标准库的一部分，提供了多种数据容器、算法和迭代器等重要组成部分。其中，队列（queue）是其中一种非常实用的数据容器，它提供了先进先出（First-In-First-Out，FIFO）的工作方式，通常用于多线程编程、网络编程、图形学等应用场合。

一、队列实现原理

队列是一种线性数据结构，它有两个基本操作：

  • Enqueue：将元素加入队列，也即将元素插入队列的尾部
  • Dequeue：将元素从队列头部取出并删除 队列的实现一般使用链表或连续的数组。将链表作为底层实现，可以在不限长度的情况下动态增加或删除队列元素，但是访问任意的元素需要进行遍历，访问速度较慢。使用数组实现的队列则具有更快的访问速度，但是容量一旦确定就不能增加或减少，可能造成内存浪费或者不足。 STL队列使用链表作为底层实现，实现了一个标准的FIFO队列，由于STL使用封装的指针以及动态分配内存的技术实现，所以它的实现既具有快速的访问速度，又能够动态调整每个元素的长度。

二、队列常用操作

C++ STL队列提供以下常用操作：

  • push()：将元素加入队列的尾部
  • pop()：将队列头部元素删除
  • front()：访问队列头部元素
  • back()：访问队列尾部元素
  • empty()：检查队列是否为空
  • size()：返回队列内元素个数

三、示例代码

#include <iostream>
#include <queue>
using namespace std;
int main()
{
    queue<int> q;
    q.push(1);
    q.push(2);
    q.push(3);
    q.push(4);
    cout << "队列当前元素个数: " << q.size() << endl;
    cout << "队列当前头部元素: " << q.front() << endl;
    cout << "队列当前尾部元素: " << q.back() << endl;
    q.pop();
    cout << "删除头部元素后，队列当前头部元素: " << q.front() << endl;
    return 0;
}

以上代码会输出以下结果：

队列当前元素个数: 4
队列当前头部元素: 1
队列当前尾部元素: 4
删除头部元素后，队列当前头部元素: 2

四、常见问题

1、STL队列的优缺点？

STL队列主要优点是容易使用和强大的性能表现。底层使用的链表和数组都提供了快速随机访问和快速插入删除的能力。 STL队列的缺点主要是它的实现方式可能造成内存浪费，而且插入和删除操作的复杂度为O(n)，对于大量元素的插入和删除操作会变得耗时。

2、如何实现一个基于数组的队列？

数组是一种简单有效的队列实现方式。创建一个数组并在其中保存队列元素，可以更快地存储和访问队列元素。例如：

#include <iostream>
using namespace std;
class Queue {
  public:
    Queue(int size) : max_size_(size), front_(-1), tail_(-1) {
      arr_ = new int[max_size_];
    }
    void enqueue(int val) {
      if (tail_ == max_size_ - 1) {
        cout << "queue is full" << endl;
        return;
      }
      arr_[++tail_] = val;
    }
    int dequeue() {
      if (front_ == tail_) {
        cout << "queue is empty" << endl;
        return -1;
      }
      return arr_[++front_];
    }
  private:
    int *arr_;
    int max_size_;
    int front_, tail_;
};
int main() {
  Queue q(100);
  q.enqueue(1);
  q.enqueue(2);
  q.enqueue(3);
  cout << q.dequeue() << endl;
  cout << q.dequeue() << endl;
  cout << q.dequeue() << endl;
  cout << q.dequeue() << endl;
  return 0;
}

以上代码会输出以下结果：

1
2
3
queue is empty

结束语

C++ STL队列提供了简单有效的实现方式，让开发者在处理FIFO数据时更为便利。在实际编程中，根据情况选择不同的队列实现方式会更好地解决问题。

推荐文章