数据结构和算法是面试的一座大山，尤其去面试大厂更是必不可少！简单说明一下为啥喜欢考数据结构和算法，首先，算法有用也没用，如果是中小型企业的简单业务逻辑，可能用不到啥算法，但大厂一定会用到，都知道数据库底层会用到红黑树、B++树等，去oracle公司，那数据结构一定要玩转，再加入想去阿里，百万数据量，不会算法去优化，可能阿里早倒闭，但小长数据量会比较少，用算法就没什么必要了。
一、桶排序应用-求最大差值
1、题目
给定一个数组，求如果排序之后，相邻两数的最大差值，要求时间复杂度O（N），且要求不能用基于比较的排序。
2、思路分析
桶排序应该都知道吧，跟计数排序和基数排序都是非比较排序，像快排、归并都是比较排序。其实，桶排序是一种思想，具体实现是计数排序和基数排序。
接下来直接来分析题目，如下：
如果有N个数，准备N+1个桶，
遍历找到最小值和最大值
假如，有9个数，准备10个桶，中间必定存在最少一个空桶，说明最大差值一定不在一个桶内，但不一定在空桶两边。
举例子如下：
三个数，四个桶，最大差值19
19 空桶 30 49
3、代码实现
如下：
View Code二、用数据实现固定大小的队列和栈
1、题目
用数据实现固定大小的队列和栈
2、思路分析
队列和和栈的特性分别是：先进先出和先进后出，思路分析见下图：
图上，标注的很明白了，有不明白的欢迎留言
3、代码实现
首先是数组实现栈，代码如下：
#include<iostream> #include<vector>using namespace std; class ArrayStack{ private: int index; //插入位置的下标 int *arr; int maxSize; public: ArrayStack(int initSize){ if(initSize < 0) throw "The initSize is less than 0"; arr = new int[initSize]; index = 0; maxSize = initSize; } void push(int num){ //压入栈 if(index == maxSize) throw "The stack is full"; arr[index++] = num; } int pop(){ if(index == 0) throw "The stack is empty"; return arr[--index]; } }; int main() { ArrayStack stack1 = ArrayStack(3); stack1.push(2); stack1.push(3); stack1.push(1); cout << "num:" << stack1.pop() << endl;
