# 栈

2023-09-18

#### 顺序栈结构定义

#define MaxSize 100
typedef struct {
int data[MaxSize];
int top;
} SqStack;


#### 初始化

void initStack(SqStack &S) {
S.top = -1;
}


#### 判断栈是否为空

bool stackEmpty(SqStack S) {
return S.top == -1 ? true : false;
}


#### 进栈

bool Push(SqStack &S, int x) {
if (S.top == MaxSize - 1)
return false;
S.data[++ S.top] = x;
return true;
}


#### 出栈

bool Pop(SqStack &S,  int &x) {
if (S.top == - 1)
return false;
x = S.data[S.top --];
return true;
}


### 相关题目

#### 判断括号序列是否合法

bool bracketCheck(char str[], int len) {
SqStack S;
initStack(S);
for (int i = 0; i < len; i ++) {
if (str[i] == '(' || str[i] == '[' || str[i] == '{') {
Push(S, str[i]);
} else {
if (stackEmpty(S)) {
return false;
}
char ch;
Pop(S, ch);
if (str[i] == ')' && ch != '(') {
return false;
}
if (str[i] == ']' && ch != '[') {
return false;
}
if (str[i] == '}' && ch != '{') {
return false;
}
}
}
return stackEmpty(S);
}


#### 栈的压入、弹出序列

class Solution {
public:
bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
stack<int> st;
int idx = 0;
for (int i = 0; i < pushed.size(); i ++) {
st.push(pushed[i]);
while(!st.empty() && st.top() == popped[idx]){
st.pop();
idx ++;
}
}
return st.empty();
}
};


#### 栈实现递归函数

struct Stack {
int n;
double ans;
}st[1005];

double fun(int n, int x) {
int top = -1;
double fv1 = 1, fv2 = 2 * x;
for (int i = n; i >= 2; i --) {
top ++;
st[top].n = i;
}
while(top >= 0) {
st[top].ans = 2 * x * fv2 - 2 * (st[top].n - 1) * fv1;
fv1 = fv2;
fv2 = st[top].ans;
top --;
}
if (n == 0)	return fv1;
return fv2;
}


#### 逆波兰表达式（后缀表达式）求值

class Solution {
public:
int evalRPN(vector<string>& tokens) {
stack<int> st;
for (int i = 0; i < tokens.size(); i ++) {
string s = tokens[i];
if (!(s == "+" || s == "-" || s == "*" || s == "/")) {
st.push(atoi(s.c_str()));
} else {
int b = st.top();
st.pop();
int a = st.top();
st.pop();
switch(s[0]) {
case '+':
st.push(a + b);
break;
case '-':
st.push(a - b);
break;
case '*':
st.push(a * b);
break;
case '/':
st.push(a / b);
break;
}
}
}
return st.top();
}
};


#### 最小栈

class MinStack {
public:
stack<int> st;
stack<int> min_st;

MinStack() {
min_st.push(INT_MAX);
}

void push(int val) {
st.push(val);
min_st.push(min(min_st.top(), st.top()));
}

void pop() {
st.pop();
min_st.pop();
}

int top() {
return st.top();
}

int getMin() {
return min_st.top();
}
};


Q.E.D.