顺序栈结构定义

#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();
    }
};

栈实现递归函数

题意：
函数Pn(x),n=0时为1，n=1时为2x，其他为2xPn-1(x)-2(n-1)Pn-2(x)

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.