文章目录
?stack的介绍和使用? stack的使用?stack的模拟实现 ? queue的介绍和使用?queue的介绍? queue的使用 ?queue的模拟实现?总结
?stack的介绍和使用
stack官网文档链接：https://legacy.cplusplus.com/reference/stack/stack/?kw=stack
stack是一种容器适配器，专门用在具有后进先出的上下文环境中，其删除只能从容器的一端进行元素的插入与提取操作。
stack是作为容器适配器被发现的，容器适配器就是对特定类封装作为其底层的容器，并提供一组特定的成员函数来访问其元素，将其特定类作为最底层的，元素特定容器的尾部（即栈顶）被压入和弹出。
stack的底层容器可以是任何标准的容器类模版或者一些其他特定的容器类，这些容器应该支持以下的操作
empty：判空操作back：获取尾部元素操作push_back：尾部插入元素操作pop_back：尾部删除元素操作 标准容器vector，deque，list均符合这些需求，默认情况下，如果没有为stack指定特定的底层容器，默认情况下使用deque.
? stack的使用
| 函数说明 | 接口说明 |
|---|---|
| stack() | 构造空的栈 |
| empty() | 检测stack是否为空 |
| size() | 返回stack中元素的个数 |
| top() | 返回栈顶元素的引用 |
| push() | 讲元素val压入stack中 |
| pop() | 将stack中尾部的元素弹出 |
例题：
最小栈：https://leetcode.cn/problems/min-stack/class MinStack{public:void push(int x){// 只要是压栈，先将元素保存到_elem中_elem.push(x);// 如果x小于_min中栈顶的元素，将x再压入_min中if (_min.empty() || x <= _min.top())_min.push(x);}void pop(){// 如果_min栈顶的元素等于出栈的元素，_min顶的元素要移除if (_min.top() == _elem.top())_min.pop();_elem.pop();}int top() { return _elem.top(); }int getMin() { return _min.top(); }private:// 保存栈中的元素std::stack<int> _elem;// 保存栈的最小值std::stack<int> _min;};class Solution {public: bool IsPopOrder(vector<int>& pushV, vector<int>& popV) { // write code here if(pushV.size() != popV.size()) { return false; } //辅助栈 stack<int> in; int n = pushV.size(); //遍历进栈下标 int i = 0; //遍历出栈对比顺序下标 for(int j = 0; j < n; ++j) { //i是否遍历完 //辅助栈为空 //栈顶不等于出栈元素 while(i < n && (in.empty() || in.top() != popV[j])) { in.emplace(pushV[i++]); } //栈顶是否为出栈数组 if(in.top() == popV[j]) { in.pop(); } else { return false; } } return true; }class Solution {public: int evalRPN(vector<string>& tokens) { stack<int> s; for (size_t i = 0; i < tokens.size(); ++i) { string& str = tokens[i]; // str为数字 if (!("+" == str || "-" == str || "*" == str || "/" == str)) { s.push(atoi(str.c_str())); } else { // str为操作符 int right = s.top(); s.pop(); int left = s.top(); s.pop(); switch (str[0]) { case '+': s.push(left + right); break; case '-': s.push(left - right); break; case '*': s.push(left * right); break; case '/': // 题目说明了不存在除数为0的情况 s.push(left / right); break; } } } return s.top(); }};用两个栈实现队列：https://leetcode.cn/problems/implement-queue-using-stacks/submissions/564009874/
?stack的模拟实现
从栈的接口中可以看出，栈实际是一种特殊的vector，因此使用vector完全可以模拟实现stack。
stack.c
namespace own{template<class T>class stack{public:stack() {}void push(const T& x) { _c.push_back(x); }void pop() { _c.pop_back(); }T& top() { return _c.back(); }const T& top()const { return _c.back(); }size_t size()const { return _c.size(); }bool empty()const { return _c.empty(); }private:std::vector<T> _c;};}test.c
# define _CRT_SECURE_NO_WARNINGS 1#include "Stack.h"using namespace std;void test_stack(){own::stack<int> mystack;mystack.push(1);mystack.push(2);mystack.push(3);mystack.push(4);cout << mystack.size() << endl;while (!mystack.empty()){cout << mystack.top() << " ";mystack.pop();}cout << endl;}int main(){test_stack();return 0;}运行结果：
? queue的介绍和使用
?queue的介绍
提取元素。队列作为容器适配器实现，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特定的
成员函数来访问其元素。元素从队尾入队列，从队头出队列。底层容器可以是标准容器类模板之一，也可以是其他专门设计的容器类。该底层容器应至少支持以下操
作: empty：检测队列是否为空size：返回队列中有效元素的个数front：返回队头元素的引用back：返回队尾元素的引用push_back：在队列尾部入队列pop_front：在队列头部出队列 标准容器类deque和list满足了这些要求。默认情况下，如果没有为queue实例化指定容器类，则使用标
准容器deque。
? queue的使用
| 函数说明 | 接口说明 |
|---|---|
| queue() | 构造空的队列 |
| empty() | 检测queue是否为空 |
| size() | 返回queue中元素的个数 |
| front() | 返回队头元素的引用 |
| back() | 返回队尾元素的引用 |
| push() | 在队尾将元素val入队列 |
| pop() | 将队头元素出队列 |
OJ题目：
用队列实现栈：https://leetcode.cn/problems/implement-stack-using-queues/description/
?queue的模拟实现
因为queue的接口中存在头删和尾插，因此使用vector来封装效率太低，故可以借助list来模拟实现queue，
具体如下：
queue.c
#pragma once#include <iostream>#include <list>using namespace std;namespace own{template <class T>class queue{public:queue(){}void push(const T& x){_c.push_back(x);}void pop(){_c.pop_front();}T& front(){return _c.front();}T& back(){return _c.back();}const T& front() const {return _c.front();}const T& back() const {return _c.back();}bool empty(){return _c.empty();}size_t size(){return _c.size();}private:list<T> _c;};}test.c:
void test_queue(){own::queue<int> q;q.push(1);q.push(2);q.push(3);q.push(4);std::cout << "Front: " << q.front() << ", Back: " << q.back() << std::endl;q.pop();std::cout << "Front: " << q.front() << ", Back: " << q.back() << std::endl;// Test empty and size std::cout << "Empty: " << q.empty() << ", Size: " << q.size() << std::endl;}
?总结
