牛客网界面：
剑指offer题目专栏界面：
一、斐波那契数列
1、题目要求
2、个人题解
2.1、解题思路
首先根据题目我们得知当n等于1或者2的时候，该函数计算结果为1，那么就先处理这种情况
接下来在n大于2的情况下讨论问题，此时由题可得函数返回结果依赖于n为1或者2的返回值，那么我们就想到利用递归来解这道题。
不断递推，当有结果出现时开始逐步回溯。
2.2、代码实现
class Solution { public: int Fibonacci(int n) { if(n==1||n==2){ return 1; } if(n>2) return Fibonacci(n-1) + Fibonacci(n-2); return -1; } };
2.3、代码解析
首先当n等于1或者2的时候，返回结果为 1
当n大于2时，调用自身的递归：
Fibonacci(n-1) + Fibonacci(n-2)会逐步缩小形参的值
当形参为1或者2时得到结果并开始回溯，最终得到正确结果
最后的return -1 是为了防止非法输入。
二、用两个栈实现队列
1、题目要求
2、个人题解
2.1、解题思路
既然是两个栈实现队列功能，那么一定要理解栈和队列的差异：
栈：一端封闭，只能对栈顶操作，先进后出
队列：不封闭，对两端操作，先进先出
对两个栈进行压栈和删除栈顶元素的操作，拼接成队列的特点
2.2、代码实现
class Solution { public: //push操作都会把元素压入栈1 void push(int node) { stack1.push(node); } int pop() { while(!stack1.empty()){ //栈1不空时将 stack2.push(stack1.top());//栈顶元素压进栈2 stack1.pop(); //将此次栈顶删去 } int res = stack2.top();//res是每次pop的返回值 stack2.pop(); //将栈2的栈顶元素删除 while(!stack2.empty()){ //当栈2不空时 stack1.push(stack2.top());//将栈顶元素压进栈1 stack2.pop(); //随后删除栈2此次栈顶元素 } return res; } private: stack<int> stack1;//栈1 stack<int> stack2;//栈2 };
2.3 代码解析
push函数没什么好分析的，就是直接将元素值压入栈1，重点在pop函数：
1.当栈1不空时，依次将栈中元素压入到栈2中
2.经过两次压栈操作，此时栈2的栈顶元素顺序就是队列栈顶的顺序
那么此时栈2的栈顶元素stack2.top()就是我们要返回的值
记录之后从栈中删除
3.然后判断栈2不为空的情况：
依次将剩下元素压进栈1中
下次再调用pop函数时也是两次压栈，顺序与队列顺序一致
测试后代码通过所有案例，每一步我都加了注释，方便大家吸收理解
本次牛客网剑指《offer》专题的两道经典题目分享结束，期待你的关注和鼓励~
