数据结构：栈（stack）详解 c++信息学奥赛基础知识讲解

目录

一、栈的定义

二、栈的操作

三、代码实操

四、栈的实现

1、string实现stack

2、vector实现stack

3、deque实现栈

---

一、栈的定义

stack是一个比较简单易用的数据结构，stack是一种容器适配器，专门用在具有后进先出操作的上下文环境中，其删除只能从容器的一端进行元素的插入与提取操作。遵循的是后进先出的原则、Last In Fist Out，LIFO（跟队列是反的，栈是后进先出）

stack是作为容器适配器被实现的，容器适配器即是对特定类封装作为其底层的容器，并提供一组特定的成员函数来访问其元素，将特定类作为其底层的，元素特定容器的尾部(即栈顶)被压入和弹出。

如何声明一个栈

stack<储存的类型> 容器名

常规类型栈

• 储存int型数据的栈 stack<int> s;
• 储存double型数据的栈 stack<double> s;
• 储存string型数据的栈 stack<string> s;
• 储存结构体或者类的栈 stack<结构体名> s;

数组栈stack：

• 储存int型数据的栈 stack<int> s[n];
• 储存double型数据的栈 stack<double> s[n];
• 等等，n为数组的大小

二、栈的操作

//其实栈就这几个成员函数
push() //在栈顶增加元素 
pop() //移除栈顶元素 
top() //返回栈顶元素 
empty() //堆栈为空则返回真 
size() //返回栈中元素数目 

三、代码实操

#include<iostream>//c++标准头文件，可以使用cout,cin等标准库函数 
#include<stack>//使用stack时需要的头文件 
using namespace std;//命名空间，防止重名给程序带来各种隐患，使用cin,cout,stack,map,set,vector,queue时都要使用
int main(){stack<int> s;//定义一个int类型的stacks.push(1);//往栈里放入一个元素1s.push(2);//往栈里放入一个元素2s.push(3); //往栈里放入一个元素3cout<<"按顺序放入元素1、2、3后，目前栈里的元素：1 2 3" <<endl;cout<<"s.size()="<<s.size()<<endl;//s.size()返回栈内元素的个数  cout<<"s.empty()="<<s.empty()<<endl; //判断栈是否为空，值为1代表空，0代表非空，用s.size()同样可以判断 ，s.size()的值为0就代表空的 cout<<"s.top()="<<s.top()<<endl;//查看栈顶的元素 cout<<endl;s.pop();//弹出栈顶元素 cout<<"s.pop()后，目前栈里的元素：1 2"<<endl;cout<<"s.size()="<<s.size()<<endl;cout<<"s.empty()="<<s.empty()<<endl; cout<<"s.top()="<<s.top()<<endl;cout<<endl;s.pop();cout<<"s.pop()后，目前栈里的元素：1"<<endl;cout<<"s.size()="<<s.size()<<endl;cout<<"s.empty()="<<s.empty()<<endl; cout<<"s.top()="<<s.top()<<endl;cout<<endl;s.pop();cout<<"s.pop()后，目前的栈是空的"<<endl;cout<<"s.size()="<<s.size()<<endl;cout<<"栈是空的就不能用s.top()访问栈顶元素了" <<endl; cout<<"s.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() //返回栈顶元素 

示例代码：

#include<iostream>//c++标准头文件，可以使用cout,cin等标准库函数 
#include<string>//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 i=0;i<s.size();i++){cout<<s[i]<<' ';}cout<<endl; cout<<"s.pop_back()="<<s.size()<<endl;//s.size()返回string内字符的个数  cout<<"s.empty()="<<s.empty()<<endl; //判断栈是否为空，值为1代表空，0代表非空，用s.size()同样可以判断 ，s.size()的值为0就代表空的 cout<<"s.back()="<<s.back()<<endl;//查看栈顶的元素 cout<<endl;s.pop_back();//弹出栈顶元素 cout<<"s.pop_back()后，目前string里的元素：";for(int i=0;i<s.size();i++){//可以通过下标随机访问元素 cout<<s[i]<<' ';}cout<<endl; cout<<"s.size()="<<s.size()<<endl;cout<<"s.empty()="<<s.empty()<<endl; cout<<"s.back()="<<s.back()<<endl;cout<<endl;s.pop_back();cout<<"s.pop_back()后，目前string里的元素：";for(int i=0;i<s.size();i++){cout<<s[i]<<' ';}cout<<endl; cout<<"s.size()="<<s.size()<<endl;cout<<"s.empty()="<<s.empty()<<endl; cout<<"s.back()="<<s.back()<<endl;cout<<endl;s.pop_back();cout<<"s.pop_back()后，目前的string是空的"<<endl;cout<<"s.size()="<<s.size()<<endl;cout<<"string是空的就不能用s.back()访问栈顶元素了" <<endl; cout<<"s.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() //返回栈顶元素 

示例代码：

#include<iostream>//c++标准头文件，可以使用cout,cin等标准库函数 
#include<vector>//使用vector时需要的头文件 
using namespace std;//命名空间，防止重名给程序带来各种隐患，使用cin,cout,stack,map,set,vector,queue时都要使用
int main(){vector<int> v;//定义一个int类型的stackv.push_back(1);//往vector里放入一个元素1v.push_back(2);//往vector里放入一个元素2v.push_back(3); //往vector里放入一个元素3cout<<"按顺序放入字符1、2、3后，目前vector里的元素：" ;for(int i=0;i<v.size();i++){//可以通过下标随机访问元素 cout<<v[i]<<' ';}cout<<endl; cout<<"v.pop_back()="<<v.size()<<endl;//v.size()返回vector内元素的个数  cout<<"v.empty()="<<v.empty()<<endl; //判断栈是否为空，值为1代表空，0代表非空，用v.size()同样可以判断 ，v.size()的值为0就代表空的 cout<<"v.back()="<<v.back()<<endl;//查看栈顶的元素 cout<<endl;v.pop_back();//弹出栈顶元素 cout<<"v.pop_back()后，目前vector里的元素：";for(int i=0;i<v.size();i++){cout<<v[i]<<' ';}cout<<endl; cout<<"v.size()="<<v.size()<<endl;cout<<"v.empty()="<<v.empty()<<endl; cout<<"v.back()="<<v.back()<<endl;cout<<endl;v.pop_back();cout<<"v.pop_back()后，目前vector里的元素：";for(int i=0;i<v.size();i++){cout<<v[i]<<' ';}cout<<endl; cout<<"v.size()="<<v.size()<<endl;cout<<"v.empty()="<<v.empty()<<endl; cout<<"v.back()="<<v.back()<<endl;cout<<endl;v.pop_back();cout<<"v.pop_back()后，目前的vector是空的"<<endl;cout<<"v.size()="<<v.size()<<endl;cout<<"vtring是空的就不能用v.back()访问栈顶元素了" <<endl; cout<<"v.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()=1

3、deque实现栈

deque(双端队列)：是一种双开口的"连续"空间的数据结构，双开口的含义是：可以在头尾两端进行插入和删除操作，且时间复杂度为O(1)，与vector比较，头插效率高，不需要搬移元素；与list比较，空间利用率比较高。

deque并不是真正连续的空间，而是由一段段连续的小空间拼接而成的，实际deque类似于一个动态的二维数组，其底层结构如下图所示：

deque 折中了 vector 与 string的结构，使用多个小数组来存储空间，为了管理这些小数组，又开辟了一个叫做中控的指针数组，数组中的指针分别指向这些小数组。

 需要注意的是，最开始使用指针是中控指针数组中间位置的指针，当进行头插、尾插的时候，就可以直接使用前一个、后一个指针指向新开辟的空间了：

当中控数组满时，只需对中控数组进行扩容就可以了， 而且由于中控数组中存放的都是指针，所以拷贝代价极低。

由以上结构我们可知deque的优点有：

1. 相比vector，deque 的扩容代价低
2. 头插头删、尾插尾删效率高
3. 支持下标随机访问

比如，假设每个小数组的容量为 10 ，我们想要找到下标为 25 的元素，只需要用下标减去第一个数组内元素的个数，再除以每个数组的容量就能找到其所在哪一个小数组。对应到上面我们所画的图中，就是 (25 - 1) / 10 。找到对应元素存在于第 2 个数组后，再用 (25 - 1) % 10 就可以知道对应元素是在该小数组中的第几个。

综上：

1. 与vector比较，deque的优势是：头部插入和删除时，不需要搬移元素，效率特别高，而且在扩容时，也不需要搬移大量的元素，因此其效率是必vector高的。
2. 与list比较，其底层是连续空间，空间利用率比较高，不需要存储额外字段。但是，deque有一个致命缺陷：不适合遍历，因为在遍历时，deque的迭代器要频繁的去检测其是否移动到某段小空间的边界，导致效率低下，而序列式场景中，可能需要经常遍历，因此在实际中，需要线性结构时，大多数情况下优先考虑vector和list，deque的应用并不多，而目前能看到的一个应用就是，STL用其作为stack和queue的底层数据结构。

STL中对stack和queue默认选择deque作为其底层容器，主要是因为：

1. stack和queue不需要遍历(因此stack和queue没有迭代器)，只需要在固定的一端或者两端进行操作。
2. 在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:stack<int> 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();}
};