stack和queue底层是如何实现的?

参考回答:

在STL中,std::stackstd::queue都是容器适配器,它们都封装了其他容器来实现各自特定的行为。具体而言:

  • std::stack 通常使用一个双端队列(std::deque)或动态数组(std::vector)作为底层容器来实现“后进先出”(LIFO)的栈操作。栈操作只允许在容器的一端进行插入和删除元素,即“栈顶”。
  • std::queue 通常使用双端队列(std::deque)作为底层容器来实现“先进先出”(FIFO)的队列操作。队列操作允许在容器的一端进行插入(队尾)和在另一端进行删除(队头)。

详细讲解与拓展:

1. std::stack 的底层实现

std::stack适配器封装了一个底层容器来支持栈操作。默认情况下,std::stack使用std::deque作为底层容器,也可以通过模板参数指定其他容器类型,如std::vector

栈的操作主要有两个:
push:将元素插入栈顶。
pop:从栈顶移除元素。
top:访问栈顶元素。

底层实现
– 在std::stack的实现中,所有操作(pushpoptop)都只会影响容器的一端(栈顶),因此可以通过封装std::dequestd::vector来实现。std::deque提供了高效的在两端插入和删除操作,而std::vector提供了高效的随机访问和在末尾插入操作。

示例代码:

#include <stack>
#include <vector>

void example() {
    std::stack<int, std::vector<int>> stk;  // 使用 vector 作为底层容器
    stk.push(1);  // 压入元素 1
    stk.push(2);  // 压入元素 2
    stk.push(3);  // 压入元素 3
    std::cout << "栈顶元素: " << stk.top() << std::endl;  // 输出 3
    stk.pop();  // 弹出元素 3
    std::cout << "栈顶元素: " << stk.top() << std::endl;  // 输出 2
}

在这个例子中,std::stack使用std::vector作为底层容器,操作栈时通过pushpoptop来实现栈式的LIFO操作。

2. std::queue 的底层实现

std::queue适配器封装了一个底层容器,通常是std::deque,来实现队列操作。队列的操作主要有两个:
push:将元素插入队尾。
pop:从队头移除元素。
front:访问队头元素。
back:访问队尾元素。

底层实现
std::queue通常使用std::deque作为底层容器。std::deque是双端队列,能够在两端高效地进行插入和删除操作。因此,std::queue可以通过std::deque提供的接口,确保在队尾插入元素和在队头删除元素的高效操作。

示例代码:

#include <queue>
#include <deque>

void example() {
    std::queue<int, std::deque<int>> q;  // 使用 deque 作为底层容器
    q.push(1);  // 入队 1
    q.push(2);  // 入队 2
    q.push(3);  // 入队 3
    std::cout << "队头元素: " << q.front() << std::endl;  // 输出 1
    q.pop();  // 出队 1
    std::cout << "队头元素: " << q.front() << std::endl;  // 输出 2
}

在这个例子中,std::queue使用std::deque作为底层容器,队列操作通过pushpopfrontback方法进行,确保“先进先出”的队列行为。

为什么选择 std::deque 作为底层容器?

std::deque是一个双端队列,能够在两端高效地插入和删除元素。这使得它非常适合用于实现std::stackstd::queue,因为:
– 对于std::stack,我们只需要在容器的末端(栈顶)插入和删除元素。
– 对于std::queue,我们需要在容器的一端(队尾)插入元素,另一端(队头)删除元素。

std::deque的优势是它在这两端提供了高效的操作(O(1)时间复杂度),使得它成为这两个容器适配器的理想选择。

总结:

  • std::stack 通常使用 std::dequestd::vector 作为底层容器,提供栈式操作(后进先出 LIFO)。
  • std::queue 通常使用 std::deque 作为底层容器,提供队列操作(先进先出 FIFO)。

这些适配器容器通过封装底层容器,简化了栈和队列的实现,并隐藏了底层容器的细节,使得开发者能够更加专注于容器的行为而不是底层实现。

发表评论

后才能评论