【STL】stack与queue的底层原理及其实现

简介: 【STL】stack与queue的底层原理及其实现

stack的介绍

1.stack是一种容器适配器,模拟了栈的数据结构。数据只能从一端进去,另一端出来(先进后出)。

2.stack适配器默认是由deque容器实现的,也可以显示要求stack的底层封装的容器类型。由于栈的特性,array和forward_list不能用来构造stack适配器。

3.stack的底层容器必须需要支持以下几个操作:

(1) empty:判空操作

(2)back:获取尾部元素操作

(3)push_back:尾部插入元素操作

(4)pop_back:尾部删除元素操作

这也意味着,即使底层封装的容器可能不一样,但我们能以统一的视角去看待以及操作stack。

库中stack的使用

通过查看手册我们能看到stack有以下成员函数:

在c++98中,stack并没有显示设计自己的构造函数。作为适配器,使用编译器默认的构造函数即可,因为默认的构造函数会调用自定义类型成员的构造。析构也是如此。

empty()

stack是否为空取决于,底层封装容器对象是否为空。stack的empty()实际上是在调用底层容器的empty()。这一点在stack的其它成员函数也类似。

给出stack的常用函数功能:

栈的模拟实现

尝试用vector作为底层容器来模拟栈。

#define _CRT_SECURE_NO_WARNINGS 1
#include<vector>


template<class T,class Container = std::vector<T> >
class stack {
public:
  //默认构造函数会自动调用自定义类型成员变量的构造函数
  //默认析构函数会自动调用自定义类型成员变量的析构函数
  size_t size() {
    return _con.size();
  }
  bool empty() {
    return _con.empty();
  }
  void push(const T& val) {
    _con.push_back(val);
  }
  T top() {
    return _con[_con.size() - 1];
  }
  void pop() {
    _con.pop_back();
  }

  void swap(stack<T>& x) {
    _con.swap(x._con);
  }

private:
  Container _con;
};

我们可以发现,这种用一种现成的容器去实现另一种容器的方式是非常方便且灵活的!帮我们节省了非常多的代码。这同样也是容器适配器的作用之一!

queue的介绍

1.队列是一种容器适配器,专门用于在FIFO上下文(先进先出)中操作,其中从容器一端插入元素,另一端 提取元素(先进先出)。

2.队列作为容器适配器实现,容器适配器即将特定容器类封装作为其底层容器类,queue提供一组特定的成员函数来访问其元素。元素从队尾入队列,从队头出队列。

3.底层容器可以是标准容器类模板之一,也可以是其他专门设计的容器类。该底层容器应至少支持以下操作:

(1) empty:检测队列是否为空

(2)size:返回队列中有效元素的个数

(3)front:返回队头元素的引用

(4)back:返回队尾元素的引用

(5)push_back:在队列尾部入队列

(6)pop_front:在队列头部出队列

4.标准容器类deque和list满足了这些要求(不能构造于vector之上)。默认情况下,如果没有为queue实例化指定容器类,则使用标准容器deque。

库中queue的使用

queue的模拟实现

#include<deque>

template<class T, class Container = std::deque<T> >
class queue {
public:
  //默认构造函数会自动调用成员变量的构造函数
  //默认析构函数会自动调用成员变量的析构函数
  size_t size() {
    return _con.size();
  }
  bool empty() {
    return _con.empty();
  }
  void push(const T& val) {
    _con.push_back(val);
  }
  T front() {
    return _con.front();
  }
  T back() {
    return _con.back();
  }
  void pop() {
    _con.pop_front();
  }

  void swap(stack<T>& x) {
    _con.swap(x._con);
  }

private:
  Container _con;
};

相关文章
|
1月前
|
容器
STL_queue
STL_queue
23 1
|
30天前
|
存储 C++ 容器
【STL】priority_queue的底层原理及其实现
【STL】priority_queue的底层原理及其实现
|
1月前
|
C++ 容器
【C++初阶】STL详解(六)Stack与Queue的介绍与使用
【C++初阶】STL详解(六)Stack与Queue的介绍与使用
20 1
|
1月前
|
存储 C++ 容器
【C++初阶】STL详解(七)Stack与Queue的模拟实现
【C++初阶】STL详解(七)Stack与Queue的模拟实现
17 1
|
10月前
|
存储 设计模式 C++
C++ STL stack & queue
stack是一种容器适配器,专门用在具有后进先出操作的上下文环境中,其删除只能从容器的一端进行元素的插入与提取操作。
|
1月前
|
存储 C++ 容器
STL--stack、queue实现
STL--stack、queue实现
|
6月前
|
C++ 容器
STL中stack和queue的使用以及模拟实现
STL中stack和queue的使用以及模拟实现
42 0
|
12月前
|
设计模式 C++ 容器
C++【STL】之stack和queue学习
C++ STL stack和queue常用接口和模拟实现详细讲解,干货满满!
87 0
C++【STL】之stack和queue学习
|
设计模式 C++ 容器
C++STL——stack与queue
C++STL——stack与queue
|
设计模式 存储 C++
【C++初阶】十、STL---stack&&queue(总)
目录 一、stack介绍和使用 1.1 stack的介绍 1.2 stack的使用 二、queue的介绍和使用 2.1 queue的介绍 2.2 queue的使用 三、容器适配器 四、deque简单了解 五、stack模拟实现 六、queue模拟实现
104 0
【C++初阶】十、STL---stack&&queue(总)

热门文章

最新文章