【STL】stack和queue的实现原理

编程入门行业动态更新时间:2024-10-12 05:44:00

【STL】stack和queue的实现<a href=https://www.elefans.com/category/jswz/34/1770123.html style= 原理"/>

【STL】stack和queue的实现原理

stack

一、概述

stack是一个先进后出（FILO）的数据结构，它只有一个出口，如图所示：

stack允许新增元素（push）、移除元素（pop）、取得最顶端的元素，但没有任何办法取得其他元素。stack不允许有遍历行为。

本章所采用list版本为 SGI STL 2.91版本。

二、stack完整定义

以某种既有容器作为底部结构，将其接口改变，使之符合“先进后出”的特性，形成一个 stack，是很容易做到的。deque 是双向开口的数据结构，若以 deque 为底部结构并封闭其头端开口，便轻而易举地形成了一个 stack。因此，STL便以 deque 作为缺省情况下的 stack 底部结构。

由于 stack 系以底部容器完成其所有工作，而具有这种“修改某物接口，形成另一种风貌”之性质者，称为 adapter（配接器）（其他博客后续会讲到），因此 stack 往往被归类为容器配接器。

#define __STL_NULL_TMPL_ARGS <> 
//模板传入的是一个类
template <class T, class Sequence = deque<T> >//deque<T>默认选择deque，并且使用alloc内存分配，缓冲区大小为512字节
class stack {friend bool operator== __STL_NULL_TMPL_ARGS (const stack&, const stack&);//声明友元friend bool operator< __STL_NULL_TMPL_ARGS (const stack&, const stack&);//声明友元
public:typedef typename Sequence::value_type value_type;//typedef typename Sequence::size_type size_type;typedef typename Sequence::reference reference;typedef typename Sequence::const_reference const_reference;
protected:Sequence c;//定义一个deque对象
public:bool empty() const { return c.empty(); }size_type size() const { return c.size(); }reference top() { return c.back(); }//返回栈顶元素的引用，可以读也可以写。const_reference top() const { return c.back(); }void push(const value_type& x) { c.push_back(x); }//压栈void pop() { c.pop_back(); }//出栈
};template <class T, class Sequence>
bool operator==(const stack<T, Sequence>& x, const stack<T, Sequence>& y) {//定义友元return x.c == y.c;
}template <class T, class Sequence>
bool operator<(const stack<T, Sequence>& x, const stack<T, Sequence>& y) {//定义友元return x.c < y.c;
}//至于为什么这里需要用友元，可以参考effective c++

三、stack的迭代器

因为stack不提供遍历功能，所以并不支持迭代器。

四、以其他容器作为stack的底层容器

我们通过观察stack容器代码得知，使用的底层容器函数有empty，size，back，push_back，pop_back。而这些函数，list和vector都具备，所以可以用list和vector来代替deque。

#include <iostream>
#include <stack>
#include <list>
#include <vector>
#include <algorithm>using namespace std;int main() {cout << "using vector:" << endl;stack<int, vector<int>> vector_stack;vector_stack.push(1);vector_stack.push(2);vector_stack.push(3);vector_stack.push(4);cout << vector_stack.size() << endl;cout << vector_stack.top() << endl;vector_stack.pop();cout << vector_stack.top() << endl;vector_stack.pop();cout << vector_stack.top() << endl;vector_stack.pop();cout << vector_stack.top() << endl;cout << vector_stack.size() << endl;cout << "using list:" << endl;stack<int, list<int>> list_stack;list_stack.push(1);list_stack.push(2);list_stack.push(3);list_stack.push(4);cout << list_stack.size() << endl;cout << list_stack.top() << endl;list_stack.pop();cout << list_stack.top() << endl;list_stack.pop();cout << list_stack.top() << endl;list_stack.pop();cout << list_stack.top() << endl;cout << list_stack.size() << endl;
}

当我们换用其他容器时，例如set：

#include <iostream>
#include <stack>
#include <list>
#include <vector>
#include <set>
#include <algorithm>using namespace std;int main() {cout << "using set:" << endl;stack<int, set<int>> set_stack;//代码运行到这里没问题set_stack.push(1);cout << set_stack.top() << endl;
}

如果只是单纯声明一个容器 set_stack，并不会报错。但是如果使用某些函数，编译器会进行报错。

queue

一、概述

queue是一种先进先出（FIFO）的结构，他有两个出口，允许从低端加入元素（push）、取得顶端元素、移除元素（pop）。除了这两种方法，没有其他办法取得queue其他元素，所以，queue也是不允许遍历行为。如下图所示：

二、queue完整定义

对于queue结构来说，deque是很容易满足的。deque是双向开口的数据结构，所以加以封装，就可以轻而易举完成一个queue。

由于 queue 系以底部容器完成其所有工作，而具有这种“修改某物接口，形成另一种风貌”之性质者，称为 adapter（配接器）（其他博客后续会讲到），因此 stack 往往被归类为容器配接器。

template <class T, class Sequence = deque<T> >
class queue {friend bool operator== __STL_NULL_TMPL_ARGS (const queue& x, const queue& y);friend bool operator< __STL_NULL_TMPL_ARGS (const queue& x, const queue& y);
public:typedef typename Sequence::value_type value_type;typedef typename Sequence::size_type size_type;typedef typename Sequence::reference reference;typedef typename Sequence::const_reference const_reference;
protected:Sequence c;
public:bool empty() const { return c.empty(); }size_type size() const { return c.size(); }reference front() { return c.front(); }const_reference front() const { return c.front(); }reference back() { return c.back(); }const_reference back() const { return c.back(); }void push(const value_type& x) { c.push_back(x); }void pop() { c.pop_front(); }
};template <class T, class Sequence>
bool operator==(const queue<T, Sequence>& x, const queue<T, Sequence>& y) {return x.c == y.c;
}template <class T, class Sequence>
bool operator<(const queue<T, Sequence>& x, const queue<T, Sequence>& y) {return x.c < y.c;
}

三、queue的迭代器

因为queue不提供遍历功能，所以并不支持迭代器。

四、以其他容器作为queue的底层容器

我们通过观察queue容器代码得知，使用的底层容器函数有empty，size，back，push_back，pop_front。而这些函数，list都具备，所以可以用list来代替deque。

#include <iostream>
#include <queue>
#include <list>
#include <vector>
#include <set>
#include <algorithm>using namespace std;int main() {cout << "using list:" << endl;queue<int, list<int>> list_queue;list_queue.push(1);list_queue.push(2);list_queue.push(3);list_queue.push(4);cout << list_queue.size() << endl;cout << list_queue.front() << endl;list_queue.pop();cout << list_queue.front() << endl;list_queue.pop();cout << list_queue.front() << endl;list_queue.pop();cout << list_queue.front() << endl;cout << list_queue.size() << endl;
}

我们发现list是可以的，并且符合先进先出的规则。

当我们用vector时：

#include <iostream>
#include <queue>
#include <list>
#include <vector>
#include <set>
#include <algorithm>using namespace std;int main() {cout << "using vector:" << endl;queue<int, vector<int>> vector_queue;vector_queue.push(1);vector_queue.push(2);vector_queue.push(3);vector_queue.push(4);cout << vector_queue.size() << endl;cout << vector_queue.front() << endl;vector_queue.pop();cout << vector_queue.front() << endl;vector_queue.pop();cout << vector_queue.front() << endl;vector_queue.pop();cout << vector_queue.front() << endl;cout << vector_queue.size() << endl;
}

由于，vector并没有头部删除，读取函数，所以并不能像stack一样使用vector作为底层容器。

当我们换用其他容器，例如set时：

#include <iostream>
#include <queue>
#include <list>
#include <vector>
#include <set>
#include <algorithm>using namespace std;int main() {cout << "using set:" << endl;queue<int, set<int>> set_queue;//代码运行到这里没问题set_queue.push(1);cout << set_queue.front() << endl;
}

如果只是单纯声明一个容器 set_queue，并不会报错。但是如果使用某些函数，编译器会进行报错。