data structure and algorithm
我希望每个人对算法和数据结构是什么有一个深刻的认识，所以我们会在每一篇的文章的开始给你灌输下面的这些知识点：
1、数据结构是一门研究组织数据方式的学科，有了编程语言也就有了数据结构，学好数据结构可以让你写出更漂亮更高效的代码（时间复杂度和空间复杂度）；
2、算法其实就是解决我们生活中遇到的问题的计算方法；
3、程序=数据结构+算法；要学好数据结构和算法就要在日常生活中把遇到的问题尝试用程序去解决
4、数据结构是实现一个算法的基础，所以想要学好算法，需要把数据结构学到位；
5、数据结构分为线性结构和非线性结构；线性结构的特点是数据元素之间存在一对一的线性关系；
6、线性结构又有顺序存储结构和链式存储结构两种的存储结构，顺序存储结构中存储元素是连续的，而链式存储结构中存储元素不一定是连续的；
栈
栈是一个先入后出（FILO）的有序列表，它是线性结构的，栈是限制线性表中元素的插入和删除只能在线性表的同一端进行的一种特殊线性表，允许插入和删除的一端，为变化的一端，称为栈顶（Top），另一端为固定的一端，称为栈底（Bottom）；
栈的底层存储结构可以是顺序存储结构实现，也可以通过链式存储结构实现，下面我们将进行两种方式的代码实现来让大家更好理解FILO这种机制的底层实现：
通过数组实现栈：
public class ArrayStack {
int max;
int[] ins;
int head;
public ArrayStack(int n) {
max=n;
ins=new int[n];
head=-1;
}
public boolean isFull(){
return head==max-1;
}
public boolean isEnpty(){
return head==-1;
}
public void show(){
if(isEnpty())
throw new RuntimeException("栈为空-----");
for(int i=head;i>=0;i--){
System.out.println(ins[i]);
}
}
public void push(int num){
if (isFull()){
System.out.println("栈已满-------");
return;
}
head++;
ins[head]=num;
}
public int pop(){
if (isEnpty())
throw new RuntimeException("栈为空-----");
int value=ins[head];
head--;
return value;
}
public int peek(){
if (isEnpty())
throw new RuntimeException("栈为空-----");
return ins[head];
}
}
通过链表实现栈：
public class LinkedStack {
DoubleLinkedList doubleLinkedList;
public LinkedStack(int count) {
this.doubleLinkedList = new DoubleLinkedList(count);
}
public boolean isEnpty(){
return doubleLinkedList.isEnpty();
}
public boolean isFull(){
return doubleLinkedList.isFull();
}
public void show(){
doubleLinkedList.show();
}
public void push(int val){
doubleLinkedList.push(val);
}
public int pop(){
return doubleLinkedList.pop();
}
public int peek(){
return doubleLinkedList.peek();
}
}
public class DoubleLinkedList {
DoubleNode cur=null;
int count;
int num=0;
int val;
public DoubleLinkedList(int count) {
this.count = count;
}
public boolean isEnpty(){
return num==0;
}
public boolean isFull(){
return num==count;
}
public int peek(){//返回栈顶元素
if(isEnpty()){
throw new RuntimeException("栈为空-----");
}
return cur.val;
}
public int pop(){//出栈
if(isEnpty()){
throw new RuntimeException("栈为空-----");
}
val=cur.val;
cur.pre.next=null;
cur=cur.pre;
num--;
return val;
}
public void push(int val){//入栈
if(isFull()){
System.out.println("栈已满-------");
return;
}
DoubleNode node=new DoubleNode(val);
if(cur==null){
cur=node;
num++;
}else{
cur.next=node;
node.pre=cur;
cur=node;
num++;
}
}
public void show(){
if(isEnpty()){
throw new RuntimeException("栈为空-----");
}
while(cur!=null){
System.out.println(cur.val);
cur=cur.pre;
}
}
}
class DoubleNode{
int val;
DoubleNode pre;
DoubleNode next;
public DoubleNode(int val) {
this.val = val;
}
public int getVal() {
return val;
}
public void setVal(int val) {
this.val = val;
}
public DoubleNode getPre() {
return pre;
}
public void setPre(DoubleNode pre) {
this.pre = pre;
}
public DoubleNode getNext() {
return next;
}
public void setNext(DoubleNode next) {
this.next = next;
}
@Override
public String toString() {
return "DoubleLinkedList{" +
"val=" + val +
", pre=" + pre +
", next=" + next +
'}';
}
}
通过栈实现综合计算器
普通计算器的思想
使用栈来完成计算器的思路：
1、定义三个方法，第一个判断当前字符是否为符号isSymbol()；第二个判断当前符号字符的优先级，优先级按照各种符号在数学计算的运算优先次序进行评级priority()；第三个进行运算，给定两个数字和一个符号进行运算并返回运算的结果；
2、定义两个栈，一个存放数字，一个存放符号；然后依次从头到尾获取运算表达式的各个字符，首先判断是否为符号，
如果是的话判断其是否为”(“，如果是直接压入符号栈，
如果是”)”的话就依次从数字栈中获取两个数字，从符号栈中获取一个符号，进行运算然后将结果压入数字栈，直到从符号栈中取到”(“为止。
如果不是以上两者情况，那么判断当前符号栈是否为空，如果为空的话直接将符号压入栈；
如果不为空的话，判断当前符号与栈顶符号的优先级，如果栈顶符号优先级大的话将其取出，再从数字栈中取出两个数字进行运算，然后将结果压人数字栈，再将当前符号压入符号栈；
如果当前符号的优先级比栈顶符号的优先级大，那么直接将符号压入符号栈；
如果不是符号的话，用一个字符串拼接这个数字字符，然后判断当前字符是否为最后一个字符，以及下一个字符是不是符号，如果两个满足其一的话就将这个拼接的字符串压入数字栈，然后将拼接字符串置空；
3、重复上述步骤直到循环完所有的字符；
4、判断符号栈是否为空，如果不为空那么就循环取出一个符号，然后从数字栈取出两个数字进行运算，并将运算结果压入数字栈；
5、从数字栈中弹出栈顶的元素，这个数字则为最终的运算结果；
代码实现:
public class SimpleComputer {
public static void main(String[] args) {
String exp="(10+50)*(7-1)";
Stack numStack=new Stack(10);
Stack symStack=new Stack(10);
int num1;
int num2;
int sym;
int res=0;
int yxj;
char key=' ';
String str="";
int index=0;
while(index<exp.length()) {
key = exp.substring(index, index + 1).charAt(0);
if(Stack.isSymbol(key)){
if(key=='('){
symStack.add(key);
index++;
continue;
}else if(key==')'){
while(symStack.head()!='('){
num1=numStack.get();
num2=numStack.get();
sym=symStack.get();
res=Stack.calculate(num2,num1,sym);
numStack.add(res);
}
symStack.get();
index++;
continue;
}
if(!symStack.isEnpty()) {
if (Stack.priority(key) <= Stack.priority(symStack.head())) {
num1=numStack.get();
num2=numStack.get();
sym=symStack.get();
res=Stack.calculate(num2,num1,sym);
numStack.add(res);
symStack.add(key);
}else{
symStack.add(key);
}
}else{
symStack.add(key);
}
}else{
str+=key;
if(index==exp.length()-1){
numStack.add(Integer.parseInt(str));
str="";
}else{
if(Stack.isSymbol(exp.substring(index+1,index+2).charAt(0))){
numStack.add(Integer.parseInt(str));
str="";
}
}
}
index++;
}
while(!symStack.isEnpty()){
num1=numStack.get();
num2=numStack.get();
sym=symStack.get();
res=Stack.calculate(num2,num1,sym);
numStack.add(res);
}
res=numStack.get();
System.out.println(res);
}
}
class Stack {
int max;
int[] ins;
int pop;
public Stack(int n) {
max=n;
ins=new int[n];
pop=-1;
}
public boolean isFull(){
return pop==max-1;
}
public boolean isEnpty(){
return pop==-1;
}
public void show(){
if(isEnpty())
throw new RuntimeException("栈为空-----");
for(int i=pop;i>=0;i--){
System.out.println(ins[i]);
}
}
public void add(int num){
if (isFull()){
System.out.println("栈已满-------");
return;
}
pop++;
ins[pop]=num;
}
public int get(){
if (isEnpty())
throw new RuntimeException("栈为空-----");
int value=ins[pop];
pop--;
return value;
}
public int head(){
if (isEnpty())
throw new RuntimeException("栈为空-----");
return ins[pop];
}
public static int priority(int c){
if(c=='*' || c=='/'){
return 1;
}else if(c=='+' || c=='-'){
return 0;
}else {
return -1;
}
}
public static boolean isSymbol(int c){
return c=='+' || c=='-' || c=='*' || c=='/' || c=='(' || c==')';
}
public static int calculate(int num1,int num2,int c){
int res=0;
switch (c){
case '+':
res=num1+num2;
break;
case '-':
res=num1-num2;
break;
case '*':
res=num1*num2;
break;
case '/':
res=num1/num2;
break;
default:
break;
}
return res;
}
}
逆波兰计算器
我们人能很好理解的表达式为中缀表达式，而计算机能很好理解的表达式为后缀表达式（也称为逆波兰表达式），所以我们把通过把中缀表达式转后缀表达式后再进行计算的计算器称为逆波兰表达式；
中缀表达式转后缀表达式的实现：
实现思路：
1、定义一个栈和一个有序集合；
2、判断当前元素是否为数字，如果是的话将该元素添加到集合中；
3、判断当前元素是否为“(“，如果是的话压入栈中；
4、判断当前元素是否为“）”，如果是的话从栈中依次弹出元素添加到集合中，直到遇到“（”；
5、如果都不是的话，循环判断当前栈是否非空，并且当前元素的优先级低于栈顶的元素，如果是的话弹出栈顶元素添加到集合中，循环结束后将当前元素压入栈中；
6、最后循环如果当前栈非空，弹出栈顶元素添加到集合中；
代码实现：
public static ArrayList midToBeh(ArrayList<String> list){
Stack<String> stack=new Stack<>();
ArrayList<String> BList=new ArrayList<String>();
for (String s:list
) {
if(s.matches("\\d+")){
BList.add(s);
}else if(s.equals("(")){
stack.push(s);
}else if(s.equals(")")){
while(!stack.peek().equals("(")){
BList.add(stack.pop());
}
stack.pop();
}else{
while(!stack.isEmpty() && it.mzt.Stack.Stack.priority(s.charAt(0))<it.mzt.Stack.Stack.priority(stack.peek().charAt(0))){
BList.add(stack.pop());
}
stack.push(s);
}
}
while(!stack.isEmpty()){
BList.add(stack.pop());
}
return BList;
}
逆波兰计算器的总体代码实现：
public class RevBoLanComputer {
public static void main(String[] args) {
String exp=" (1 1+50 ) *( 7 - 1 )";
ArrayList list=toList(exp);
System.out.println(list);
ArrayList list1=midToBeh(list);
System.out.println(list1);
int res=RecBoLan(list1);
System.out.println(res);
}
public static ArrayList toList(String str){
str=str.replaceAll("\\s*","");
ArrayList<String> list=new ArrayList<>();
int index=0;
char key=' ';
String ss="";
while (index<=str.length()-1){
key=str.substring(index,index+1).charAt(0);
if(key<48 || key>57){
list.add(String.valueOf(key));
}else{
ss+=key;
if(str.substring(index+1,index+2).charAt(0)<48 || str.substring(index+1,index+2).charAt(0)>57){
list.add(ss);
ss="";
}
}
index++;
}
return list;
}
public static ArrayList midToBeh(ArrayList<String> list){
Stack<String> stack=new Stack<>();
ArrayList<String> BList=new ArrayList<String>();
for (String s:list
) {
if(s.matches("\\d+")){
BList.add(s);
}else if(s.equals("(")){
stack.push(s);
}else if(s.equals(")")){
while(!stack.peek().equals("(")){
BList.add(stack.pop());
}
stack.pop();
}else{
while(!stack.isEmpty() && it.mzt.Stack.Stack.priority(s.charAt(0))<it.mzt.Stack.Stack.priority(stack.peek().charAt(0))){
BList.add(stack.pop());
}
stack.push(s);
}
}
while(!stack.isEmpty()){
BList.add(stack.pop());
}
return BList;
}
public static int RecBoLan(ArrayList<String> list){
Stack<Integer> stack=new Stack<>();
int res;
int num1;
int num2;
for (String s:list
) {
if(s.matches("\\d+")){
stack.push(Integer.valueOf(s));
}else{
num1=stack.pop();
num2=stack.pop();
res= it.mzt.Stack.Stack.calculate(num2,num1,s.charAt(0));
stack.push(res);
}
}
return stack.pop();
}
}