栈
栈（stack）一种操作受限的线性结构，限定仅能在尾部进行插入和删除，能进行插入和删除操作的一端叫做栈顶，而另一端叫做栈底；我们将插入栈的操作叫做入栈，从栈中删除元素的操作叫做出栈，栈是一个先入后出（FILO）的数据结构，即先入栈的元素会后出栈。
栈最常被我们接触的场景就是函数调用了，在进程地址空间中，有一块空间叫做栈空间，是在发生函数调用的时候我们通常将主调函数的上下文入栈，然后在栈上再开辟一块空间用于存放这个被调函数的上下文信息；因为调用链是自上而下的，而运行环境的恢复则是得按照一个自下而上的顺序逆序进行恢复，非常贴合栈自然的一个操作顺序。
栈的面试点
上述主要介绍了栈的定义、操作上的一些特点，以及常用到的一些场景。另外因为栈的操作相对比较简单，所以也比较常见于技术开发面试的一些面试题目的，列举一些例子。
括号匹配（简单难度）
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/valid-parentheses
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。解法：
#include <stack>
class Solution {
public:
bool isValid(string s) {
stack<char> local_stack;
for(int index = 0;index<s.length();++index){
if((s[index] == '(') || (s[index]=='{') || (s[index]=='[')){
local_stack.push(s[index]);
}
else if (s[index] == ')') {
if((!local_stack.empty()) && local_stack.top() == '('){
local_stack.pop();
}
else {
return false;
}
}
else if ((!local_stack.empty()) &&s[index] == ']') {
if(local_stack.top() == '['){
local_stack.pop();
}
else {
return false;
}
}
else if ((!local_stack.empty()) &&s[index] == '}') {
if(local_stack.top() == '{'){
local_stack.pop();
}
else {
return false;
}
}
else {
return false;
}
}
if(local_stack.empty()) {
return true;
}
return false;
}
};这道题的基本思路就是运用了栈的后进先出的规则，对于输入的括号串发现是左括号就入栈，发现是右括号就和栈顶进行匹配，能匹配上就出栈，这里需要关注两个边界点：
1）最开始输入的时候就是右括号，此时栈为空，和栈顶进行比较的话会报异常；所以上面判断的步骤需要先判空
2）需要防止输入非括号字符串的场景；
此外由于上述判断分支比较多，我们可通过一些办法对代码进行一定程度的精简，如下：
#include <stack>
class Solution {
public:
bool isValid(string s) {
stack<char> local_stack;
local_stack.push(' ');
for(int index = 0;index<s.length();++index){
if((s[index] == '(') || (s[index]=='{') || (s[index]=='[')){
local_stack.push(s[index]);
}
else if ((s[index] == ')') || (s[index]=='}') || (s[index]==']')) {
if((s[index] - local_stack.top()< 3) && (s[index] - local_stack.top() > 0)){
local_stack.pop();
}
else {
return false;
}
}
else {
return false;
}
}
if(local_stack.top() == ' ') {
return true;
}
return false;
}
};两个点：
1）一个是新增一个哨兵，以后就不需要每一步都判断栈为空的情形
2）根据ASC码来判断
其他类似消消乐等编程题也是类似的解法，无非是出栈的条件从括号匹配变为其他指定的条件而已。
栈与线性结构（中等难度）
题目描述
（源于leetcode上面的一道题），链表重排：假设我们的输入链表为L1->L2->L3->...->Ln-1->Ln，我们希望输出链表为L1->Ln->L2->Ln-1...
题目分解
从题目我们可以看出，这个链表可以拆解为L1->L2->...->Ln/2和Ln->Ln-1->...->Ln/2+1的链表合并，即一个正序链表和逆序链表的归并。
实现代码：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
#include <stack>
#include <queue>
class Solution {
public:
void reorderList(ListNode* head) {
stack<ListNode*> reverse_stack;
queue<ListNode*> traverse_queue;
ListNode* reverse = head;
int count = 0;
while(reverse != nullptr) {
reverse_stack.push(reverse);
traverse_queue.push(reverse);
ListNode* next = reverse->next;
reverse->next = nullptr;
reverse = next;
count++;
}
ListNode* result = traverse_queue.front();
traverse_queue.pop();
count--;
while((count>0)&&(!reverse_stack.empty())){
ListNode* temp = reverse_stack.top();
reverse_stack.pop();
result->next = temp;
result = temp;
count--;
if((count > 0) && (!traverse_queue.empty())) {
ListNode* temp = traverse_queue.front();
traverse_queue.pop();
result->next = temp;
result = temp;
count--;
}
}
}
};上述代码是栈的一个应用场景，但是从代码设计角度上说，空间复杂度偏高，用了O(2*N)，我们可以用线性表的角度对这个代码进行优化，于是有：
#include <vector>
class Solution {
public:
void reorderList(ListNode* head) {
vector<ListNode*> list_vec;
ListNode* iter = head;
while(iter!=nullptr){
list_vec.push_back(iter);
ListNode* temp = iter->next;
iter->next = nullptr;
iter = temp;
}
vector<ListNode*>::iterator vec_iter = list_vec.begin()+1;
vector<ListNode*>::iterator vec_riter = list_vec.end()-1;
iter = head;
while(vec_iter <= vec_riter){
iter->next = *vec_riter;
iter = iter->next;
vec_riter--;
if(vec_iter <= vec_riter) {
iter->next = *vec_iter;
iter = iter->next;
vec_iter++;
}
}
}
};主体思路是，用vector管理链表，然后头尾指针交替插入；但是这个还是会有新增O（n）的额外空间开销，我们希望达到O(1)的空间复杂度，于是有：
class Solution {
public:
void reorderList(ListNode* head) {
ListNode* iter_first = head;
ListNode* tail = nullptr;
if(iter_first == nullptr){
return;
}
//找到中间位置
ListNode* iter_second = head->next;
while(iter_second != nullptr) {
iter_second = iter_second->next;
if(iter_second != nullptr){
iter_second = iter_second->next;
iter_first = iter_first->next;
}
}
//后半部分reverse
ListNode* iter_pre = iter_first->next;
if(iter_pre == nullptr){
return;
}
ListNode* iter_curr = iter_pre->next;
iter_pre->next = nullptr;
if(iter_curr != nullptr){
iter_next = iter_curr->next;
while(iter_next != nullptr){
iter_curr->next = iter_pre;
iter_pre = iter_curr;
iter_curr = iter_next;
iter_next = iter_next->next;
}
iter_curr->next = iter_pre;
tail = iter_curr;
}
else{
tail = iter_pre;
}
//链表归并
ListNode* first = head;
while(first != nullptr && tail != nullptr){
ListNode* temp1 = first->next;
ListNode* temp2 = tail->next;
first->next = tail;
tail->next = temp1;
first = temp1;
tail=temp2;
}
}
};总体思路是，先通过二倍步长找到链表的中间位置，然后对后半部分的链表进行reverse，剩下的就是对两个链表的归并排序了。
栈与一些算法（高难度）
栈也可以和一些算法如动态规划等结合，这类问题在面试过程中属于比较难的题目了，这里举一个比较简单的例子，最长有效括号问题，给一个只包含'('和‘)’的字符串，找出最长有效括号字串的长度：
class Solution {
public:
int longestValidParentheses(string s) {
int maxans = 0;
stack<int> stk;
stk.push(-1);
for (int i = 0; i < s.length(); i++) {
if (s[i] == '(') {
stk.push(i);
} else {
stk.pop();
//空了表示是非法串了
if (stk.empty()) {
stk.push(i);
} else {
//非空，top记录的是上一个合法串的起始位置，i-top就是合法串的长度，每次合法都更新一下
maxans = max(maxans, i - stk.top());
}
}
}
return maxans;
}
};
