【三】一起算法---栈：STL stack、手写栈、单调栈

纸上得来终觉浅，绝知此事要躬行。大家好！我是霜淮子，欢迎订阅我的专栏《算法系列》。

学习经典算法和经典代码，建立算法思维；大量编码让代码成为我们大脑的一部分。

⭐️已更系列

 1、基础数据结构

       1.1、链表➡传送门

       1.2、队列➡传送门

       1.3、 栈   ➡本章

专栏直达《算法系列》

目录

前言

文本翻转

问题描述：

输入：

输出：

1.3、栈

1.3.1、STL stack

1.3.2、手写栈

1.3.3、单调栈

---

前言

文本翻转

问题描述：

伊格内修斯喜欢用相反的方式写字。给定一行由伊格内修斯写的文字，你应该把所有的单词倒过来，然后输出。

输入：

测试样本：olleh !dlrow

输出：

hello world!

1.3、栈

“栈”的特点是”先进后出“。栈在生活中有许多表现：坐电梯，先进电梯的被挤在最里面，只能最后才出来；栈只有唯一的一个出入口，从这个口进入，也从这个口弹出，这是它与队列最大的区别。队列有一个出口和一个入口，所以手写栈比手写队列会简单一点，

在编程中常用的递归就是用栈来实现的。栈要用存储空间来存储，如果栈的深度太大，或者进栈的数组太大，那么总数会超过系统为栈分配的空间，就会爆栈导致栈溢出。为避免爆栈，需要严格控制栈的大小。

1.3.1、STL stack

STL  stack 的有关操作

• stack<Type> s 定义栈，Type为数据类型，如int,float,char等。
• a.push(item) 把item放到栈顶。
• s.top() 返回栈顶元素，但不会删除。
• s.pop()  删除栈顶元素，但不会返回。在出栈时需要执行两步操作：先使用pop()获得栈顶元素，在使用pop()删除栈顶元素。
• s.size() 返回栈中的元素个数。
• s.empty() 检查栈是否为空，如果为空，返回True,否则返回false.

文本翻转的代码如下：

#include<bits/stdc++.h>
using namespace std;
int main(){int n;   scanf("%d",&n);  getchar();while(n--){stack<char> s;while(true){char ch = getchar();              //一次读入一个字符if(ch==' '||ch=='\n'||ch==EOF){while(!s.empty()){ printf("%c",s.top()); s.pop();} //输出并清除栈顶if(ch=='\n'||ch==EOF)  break;printf(" ");}else    s.push(ch);               //入栈}printf("\n");
}
return 0;
}

1.3.2、手写栈

手写栈代码简单且节省空间。

#include<bits/stdc++.h>
const int N = 100100;
struct mystack{char a[N];                            //存放栈元素，字符型int t = 0;                            //栈顶位置void push(char x){ a[++t] = x; }      //送入栈char top()       { return a[t]; }     //返回栈顶元素void pop()       { t--;         }     //弹出栈顶int empty()      { return t==0?1:0;}  //返回1表示空
}st;
int main(){
int n;	scanf("%d",&n);  getchar();
while(n--){
while(true){
char ch = getchar();            //一次读入一个字符
if(ch==' '||ch=='\n'||ch==EOF){while(!st.empty()){ printf("%c",st.top()); st.pop();}  //输出并清除栈顶	if(ch=='\n'||ch==EOF)  break;printf(" ");}else    st.push(ch);              //入栈}printf("\n");}return 0;
}

1.3.3、单调栈

单调栈不是一种新的栈结构，它在结构上仍然是一个普通的栈，它是栈的一种使用方式。

单调栈内的元素是单调递增或单调递减的，有单调递增栈、单调递减栈。单调栈可以用来处理比较问题。

单调栈使用时始终保持栈内的元素是单调的。例如，单调递减栈从栈顶到栈底是从小到大的顺序。当一个数入栈时，与栈顶比较，若比栈顶小，则入栈，若比栈顶大，则弹出栈顶，直到这个数能入栈为止。注意：每个数都一定入栈。

-END-