二、Stack

2.1 介绍

栈作为数据结构中的一种,是STL实现的一个先进先出,后进后出的容器。

//头文件添加
#include<stack>

//声明
stack<int> s;
stack<string> s;
stack<node> s;//node是结构体类型

2.2 方法函数

代码含义
s.push(ele)元素ele入列,增加元素O(1)
s.pop()移出栈顶元素O(1)
s.top()取得栈顶元素(但是不删除)O(1)
s.empty()检测栈内是否为空,空为真O(1)
s.size()返回栈内元素个数O(1)

2.3 栈遍历

2.3.1 栈遍历

栈只能对栈顶元素进行操作,如果想要进行遍历,只能将栈中元素一个个取出来存在数组中

stack<int> st;
for (int i = 0; i < 10; ++i) st.push(i);
while (!st.empty()) {
    int tp = st.top(); // 栈顶元素
    st.pop();
}
2.3.2 数组模拟栈进行遍历

通过一个数组对栈进行模拟,一个存放下标的变量top模拟指向栈顶的指针。

一般来说单调栈和单调队列写法均可以使用额外变量tt或者hh来进行模拟

特点:比STL的stack速度更快,遍历元素方便

int s[100]; // 栈 从左至右为栈底到栈顶
int tt = -1; // tt 代表栈顶指针,初始栈内无元素,tt为-1

for(int i = 0; i <= 5; ++i) {
	//入栈 
	s[++tt] = i;
}
// 出栈
int top_element = s[tt--]; 

//入栈操作示意
//  0  1  2  3  4  5  
//                tt
//出栈后示意
//  0  1  2  3  4 
//              tt