电 器建设网站目的及功能定位,网站程序设置主页面,重庆泡笋制作,网页qq登陆聊天个人主页~ Stack 一、Stack的介绍和使用1、stack的介绍2、stack的使用3、stack的模拟实现 二、容器适配器1、什么是适配器2、容器适配器的使用 三、deque1、原理介绍2、deque的使用3、deque的缺陷 一、Stack的介绍和使用
1、stack的介绍
stack详细解释
stack是一种容器适配器…
个人主页~ Stack 一、Stack的介绍和使用1、stack的介绍2、stack的使用3、stack的模拟实现 二、容器适配器1、什么是适配器2、容器适配器的使用 三、deque1、原理介绍2、deque的使用3、deque的缺陷 一、Stack的介绍和使用
1、stack的介绍
stack详细解释
stack是一种容器适配器专门用来处理后进先出操作其删除只能从容器的一端进行元素的插入和提取操作
stack是作为容器适配器被实现的容器适配器是对特定类封装为其底层的容器并提供一组特定的成员函数来访问其元素将特定类作为其底层的元素特定容器的尾部被压入和弹出
stack的底层容器可以是任何标准的容器类模版或者一些其他特定的容器类这些容器都要支持empty判空、back获取尾部元素、push_back尾部插入元素、pop_back尾部删除元素的操作这些是stack的基本接口
标准容器vector、list、deque均符合这些要求如果没有指定stack的底层容器默认为deque这其中只有deque没有学习过后面拿一个段落专门解释deque
2、stack的使用
函数说明接口说明stack构造空的栈empty检测stack是否为空size返回stack中的元素个数top返回栈顶元素的引用push将元素val压入stack中pop将stack中尾部的元素弹出
void test_stack()
{stackint st;st.push(1);st.push(2);st.push(3);st.push(4);while (!st.empty()){cout st.top() endl;st.pop();}
}手感火热做道题
最小栈 解题思路就是创建两个栈st和minstst栈存放数据minst栈存放最小值第一个入st栈的直接入minst栈每次入st栈都与minst栈的top比较一下是不是更小如果数小就入minst栈
class MinStack
{
public:MinStack() {}//空构造构造空栈void push(int val) {if(minst.empty() || val minst.top()){minst.push(val);}st.push(val);}//如果minst栈为空或者入栈的值小于等于minst的栈顶元素就入minst栈void pop() {if(st.top() minst.top()){minst.pop();}st.pop();}//如果删除st栈顶元素与minst栈顶的元素相等就连minst栈顶元素一块删除int top() {return st.top();}int getMin() {return minst.top();}
//因为minst是被比较出来的越往上的元素越小所以栈顶元素就是最小的元素stackint st;stackint minst;
};栈的压入、弹出序列 这个题就是写一个栈弹出顺序是否正确的函数传给两个vector然后pushV元素压入栈然后取栈顶元素与popV的第一个元素进行对比如果相同就出栈如果不同就继续入栈最后如果pushV遍历完后栈为空那么就正确否则就错误
bool IsPopOrder(vectorint pushV, vectorint popV)
{stackint st;size_t pushi 0,popi 0;//用于记录pushV、popV的下标while(pushi pushV.size())//如果下标小于size循环继续{st.push(pushV[pushi]);//pushV元素压入栈while(!st.empty() st.top() popV[popi]){st.pop();popi;}//然后取栈顶元素与popV的第一个元素进行对比如果相同就出栈}return st.empty();
}3、stack的模拟实现
stack.h #pragma once#include vector
#include deque
#include list
#include iostreamnamespace little_monster
{templateclass T,class Container std::dequeTclass 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:Container _c;};
}stack可以通过vector为底层实现也可以通过list为底层实现直接调用这些模版的接口就可以不用在从零开始定义成员变量了
这里的Container以及deque是什么呢
二、容器适配器
1、什么是适配器
适配器是一种设计模式该种设计模式是将一个类的接口转换成用户希望的另外一个接口适配器可以接受不同的容器来达到用户想要的效果而stack和queue的默认适配器是dequepriority_queue的默认适配器是vector
2、容器适配器的使用
常见于stack、queue、priority_queue、优先队列中
三、deque
相关文档
1、原理介绍
deque是一种双开口的连续空间的数据结构可以在头尾两端进行插入和删除操作且时间复杂度为O(1)与vector比较头插效率高不需要搬移元素与list比较空间利用率比较高
deque并不是真正连续的空间而是由一段段连续的小空间拼接而成的实际deque类似于一个动态的二维数组
双端队列底层是一段假想的连续空间实际是分段连续的为了维护其“整体连续”以及随机访问的假象落在了deque的迭代器身上
偷一张详解图 首先我们可以看到start迭代器它由四个指针组成cur表示当前位置first表示第一个位置last表示最后一个位置node是指向map的其中一个变量
当cur等于last时node指向下一个位置然后cur、first、last都重置到下一个map元素在图中就是cur、first指向8last指向15后一个位置
当start迭代器中的node和finish迭代器中的node相同时该数组就是最后一个数组
然后这个map其实是一个指针数组它进行扩容时是从中间向两端地存储如果我们进行头插start指向的数组又满了我们就在start前面的位置再开一个数组并且把数据存储在这个数组的最后一个位置
2、deque的使用
void test_deque()
{std::dequeint dq;dq.push_back(3);dq.push_back(4);dq.push_front(2);dq.push_front(1);for (size_t sz 0; sz dq.size(); sz){std::cout dq[sz] ;}std::cout std::endl;
}3、deque的缺陷
它不适合遍历因为在遍历时deque的迭代器要频繁的去检测其是否移动到某小段小空间的边界导致效率低下因此在实际中需要线性结构时大多数优先使用vector和list但我们知道的一个应用就是STL中做stack和queue的底层数据结构
它结合了vector和list的部分优点也得到了它们的部分缺点与vector相比deque的优势是头插头删和扩容时不需要搬移元素效率高与list比较其底层是连续的空间空间利用率较高 今日分享就到这里~
