哪个做h5的网站好用,中信建设有限责任公司湖南省人防建筑设计院,网站所有页面只显示域名,广东网站设计公司电话目录
一、栈的定义
二、栈的操作
三、代码实操
四、栈的实现
1、string实现stack
2、vector实现stack
3、deque实现栈 一、栈的定义
stack是一个比较简单易用的数据结构#xff0c;stack是一种容器适配器#xff0c;专门用在具有后进先出操作的上下文环境中#xff…
目录
一、栈的定义
二、栈的操作
三、代码实操
四、栈的实现
1、string实现stack
2、vector实现stack
3、deque实现栈 一、栈的定义
stack是一个比较简单易用的数据结构stack是一种容器适配器专门用在具有后进先出操作的上下文环境中其删除只能从容器的一端进行元素的插入与提取操作。遵循的是后进先出的原则、Last In Fist OutLIFO跟队列是反的栈是后进先出
stack是作为容器适配器被实现的容器适配器即是对特定类封装作为其底层的容器并提供一组特定的成员函数来访问其元素将特定类作为其底层的元素特定容器的尾部(即栈顶)被压入和弹出。 如何声明一个栈
stack储存的类型 容器名
常规类型栈
储存int型数据的栈 stackint s;储存double型数据的栈 stackdouble s;储存string型数据的栈 stackstring s;储存结构体或者类的栈 stack结构体名 s;
数组栈stack
储存int型数据的栈 stackint s[n];储存double型数据的栈 stackdouble s[n];等等n为数组的大小
二、栈的操作
//其实栈就这几个成员函数
push() //在栈顶增加元素
pop() //移除栈顶元素
top() //返回栈顶元素
empty() //堆栈为空则返回真
size() //返回栈中元素数目 三、代码实操
#includeiostream//c标准头文件可以使用cout,cin等标准库函数
#includestack//使用stack时需要的头文件
using namespace std;//命名空间防止重名给程序带来各种隐患使用cin,cout,stack,map,set,vector,queue时都要使用
int main(){stackint s;//定义一个int类型的stacks.push(1);//往栈里放入一个元素1s.push(2);//往栈里放入一个元素2s.push(3); //往栈里放入一个元素3cout按顺序放入元素1、2、3后目前栈里的元素1 2 3 endl;couts.size()s.size()endl;//s.size()返回栈内元素的个数 couts.empty()s.empty()endl; //判断栈是否为空值为1代表空0代表非空用s.size()同样可以判断 s.size()的值为0就代表空的 couts.top()s.top()endl;//查看栈顶的元素 coutendl;s.pop();//弹出栈顶元素 couts.pop()后目前栈里的元素1 2endl;couts.size()s.size()endl;couts.empty()s.empty()endl; couts.top()s.top()endl;coutendl;s.pop();couts.pop()后目前栈里的元素1endl;couts.size()s.size()endl;couts.empty()s.empty()endl; couts.top()s.top()endl;coutendl;s.pop();couts.pop()后目前的栈是空的endl;couts.size()s.size()endl;cout栈是空的就不能用s.top()访问栈顶元素了 endl; couts.empty()s.empty()endl; }运行结果
按顺序放入元素1、2、3后目前栈里的元素1 2 3
s.size()3
s.empty()0
s.top()3s.pop()后目前栈里的元素1 2
s.size()2
s.empty()0
s.top()2s.pop()后目前栈里的元素1
s.size()1
s.empty()0
s.top()1s.pop()后目前的栈是空的
s.size()0
栈是空的就不能用s.top()访问栈顶元素了
s.empty()1四、栈的实现
stack是一种后进先出的特殊线性数据结构因此只要具有push_back()和pop_back()操作的线性结构都可以作为stack的底层容器比如string、vector和list都可以
1、string实现stack
栈中的数据是不允许随机访问的就是不能像数组那样用下标访问也不能遍历栈内的元素这是很局限的。实际上我们经常使用的string类型就是一种栈结构但是我们可以通过下标访问元素我们可以看看
//string的栈相关的成员函数
empty() //堆栈为空则返回真
pop_back() //移除栈顶元素
push_back() //在栈顶增加元素
size() //返回栈中元素数目
back() //返回栈顶元素
示例代码
#includeiostream//c标准头文件可以使用cout,cin等标准库函数
#includestring//string包括了一些字符串操作的库函数但用string时是不用引入这个头文件的
using namespace std;//命名空间防止重名给程序带来各种隐患使用cin,cout,stack,map,set,vector,queue时都要使用
int main(){string s;//定义一个字符串s.push_back(1);//往栈里放入一个元素1s.push_back(2);//往栈里放入一个元素2s.push_back(3); //往栈里放入一个元素3cout按顺序放入字符1、2、3后目前string里的元素 ;for(int i0;is.size();i){couts[i] ;}coutendl; couts.pop_back()s.size()endl;//s.size()返回string内字符的个数 couts.empty()s.empty()endl; //判断栈是否为空值为1代表空0代表非空用s.size()同样可以判断 s.size()的值为0就代表空的 couts.back()s.back()endl;//查看栈顶的元素 coutendl;s.pop_back();//弹出栈顶元素 couts.pop_back()后目前string里的元素;for(int i0;is.size();i){//可以通过下标随机访问元素 couts[i] ;}coutendl; couts.size()s.size()endl;couts.empty()s.empty()endl; couts.back()s.back()endl;coutendl;s.pop_back();couts.pop_back()后目前string里的元素;for(int i0;is.size();i){couts[i] ;}coutendl; couts.size()s.size()endl;couts.empty()s.empty()endl; couts.back()s.back()endl;coutendl;s.pop_back();couts.pop_back()后目前的string是空的endl;couts.size()s.size()endl;coutstring是空的就不能用s.back()访问栈顶元素了 endl; couts.empty()s.empty()endl; }输出结果
按顺序放入字符1、2、3后目前string里的元素1 2 3
s.pop_back()3
s.empty()0
s.back()3s.pop_back()后目前string里的元素1 2
s.size()2
s.empty()0
s.back()2s.pop_back()后目前string里的元素1
s.size()1
s.empty()0
s.back()1s.pop_back()后目前的string是空的
s.size()0
string是空的就不能用s.back()访问栈顶元素了
s.empty()1
2、vector实现stack
vector是stack的升级版多了很多成员函数像随机插入函数insert()等等大家完全可以用vector替代stack的。vector和string不同的是string只能存储char类型的而vector能存储所有类型的数据想int、double、结构体、类等等
//vector的栈相关的成员函数
empty() //堆栈为空则返回真
pop_back() //移除栈顶元素
push_back() //在栈顶增加元素
size() //返回栈中元素数目
back() //返回栈顶元素 示例代码
#includeiostream//c标准头文件可以使用cout,cin等标准库函数
#includevector//使用vector时需要的头文件
using namespace std;//命名空间防止重名给程序带来各种隐患使用cin,cout,stack,map,set,vector,queue时都要使用
int main(){vectorint v;//定义一个int类型的stackv.push_back(1);//往vector里放入一个元素1v.push_back(2);//往vector里放入一个元素2v.push_back(3); //往vector里放入一个元素3cout按顺序放入字符1、2、3后目前vector里的元素 ;for(int i0;iv.size();i){//可以通过下标随机访问元素 coutv[i] ;}coutendl; coutv.pop_back()v.size()endl;//v.size()返回vector内元素的个数 coutv.empty()v.empty()endl; //判断栈是否为空值为1代表空0代表非空用v.size()同样可以判断 v.size()的值为0就代表空的 coutv.back()v.back()endl;//查看栈顶的元素 coutendl;v.pop_back();//弹出栈顶元素 coutv.pop_back()后目前vector里的元素;for(int i0;iv.size();i){coutv[i] ;}coutendl; coutv.size()v.size()endl;coutv.empty()v.empty()endl; coutv.back()v.back()endl;coutendl;v.pop_back();coutv.pop_back()后目前vector里的元素;for(int i0;iv.size();i){coutv[i] ;}coutendl; coutv.size()v.size()endl;coutv.empty()v.empty()endl; coutv.back()v.back()endl;coutendl;v.pop_back();coutv.pop_back()后目前的vector是空的endl;coutv.size()v.size()endl;coutvtring是空的就不能用v.back()访问栈顶元素了 endl; coutv.empty()v.empty()endl;
}输出结果
按顺序放入字符1、2、3后目前vector里的元素1 2 3
v.pop_back()3
v.empty()0
v.back()3v.pop_back()后目前vector里的元素1 2
v.size()2
v.empty()0
v.back()2v.pop_back()后目前vector里的元素1
v.size()1
v.empty()0
v.back()1v.pop_back()后目前的vector是空的
v.size()0
vtring是空的就不能用v.back()访问栈顶元素了
v.empty()13、deque实现栈
deque(双端队列)是一种双开口的连续空间的数据结构双开口的含义是可以在头尾两端进行插入和删除操作且时间复杂度为O(1)与vector比较头插效率高不需要搬移元素与list比较空间利用率比较高。
deque并不是真正连续的空间而是由一段段连续的小空间拼接而成的实际deque类似于一个动态的二维数组其底层结构如下图所示 deque 折中了 vector 与 string的结构使用多个小数组来存储空间为了管理这些小数组又开辟了一个叫做中控的指针数组数组中的指针分别指向这些小数组。 需要注意的是最开始使用指针是中控指针数组中间位置的指针当进行头插、尾插的时候就可以直接使用前一个、后一个指针指向新开辟的空间了 当中控数组满时只需对中控数组进行扩容就可以了 而且由于中控数组中存放的都是指针所以拷贝代价极低。
由以上结构我们可知deque的优点有
相比vectordeque 的扩容代价低头插头删、尾插尾删效率高支持下标随机访问
比如假设每个小数组的容量为 10 我们想要找到下标为 25 的元素只需要用下标减去第一个数组内元素的个数再除以每个数组的容量就能找到其所在哪一个小数组。对应到上面我们所画的图中就是 (25 - 1) / 10 。找到对应元素存在于第 2 个数组后再用 (25 - 1) % 10 就可以知道对应元素是在该小数组中的第几个。
综上
与vector比较deque的优势是头部插入和删除时不需要搬移元素效率特别高而且在扩容时也不需要搬移大量的元素因此其效率是必vector高的。与list比较其底层是连续空间空间利用率比较高不需要存储额外字段。但是deque有一个致命缺陷不适合遍历因为在遍历时deque的迭代器要频繁的去检测其是否移动到某段小空间的边界导致效率低下而序列式场景中可能需要经常遍历因此在实际中需要线性结构时大多数情况下优先考虑vector和listdeque的应用并不多而目前能看到的一个应用就是STL用其作为stack和queue的底层数据结构。
STL中对stack和queue默认选择deque作为其底层容器主要是因为
stack和queue不需要遍历(因此stack和queue没有迭代器)只需要在固定的一端或者两端进行操作。在stack中元素增长时deque比vector的效率高(扩容时不需要搬移大量数据)queue中的元素增长时deque不仅效率高而且内存使用率高。结合了deque的优点而完美的避开了其缺陷。 deque的迭代器 五、案例实操
题目描述实现一个MyQueue类该类用两个栈来实现一个队列。
示例
MyQueue queue new MyQueue();queue.push(1);
queue.push(2);
queue.peek(); // 返回 1
queue.pop(); // 返回 1
queue.empty(); // 返回 false
说明
你只能使用标准的栈操作 -- 也就是只有 push to top, peek/pop from top, size 和 is empty 操作是合法的。你所使用的语言也许不支持栈。你可以使用 list 或者 deque双端队列来模拟一个栈只要是标准的栈操作即可。假设所有操作都是有效的 例如一个空的队列不会调用 pop 或者 peek 操作。
代码实现
class MyQueue {
private:stackint inStack, outStack;//私有成员函数入栈并出栈void in2out() {while (!inStack.empty()) {outStack.push(inStack.top());inStack.pop();}}public:MyQueue() {}//入队void push(int x) {inStack.push(x);}//出队并返回首元素int pop() {if (outStack.empty()) {in2out();}int x outStack.top();outStack.pop();return x;}//返回队首元素int peek() {if (outStack.empty()) {in2out();}return outStack.top();}//判断队是否为空bool empty() {return inStack.empty() outStack.empty();}
};
