导读
栈和队列是有操作限制的线性表。
目录
1、栈的概念、特点、存储结构。
2、栈的java实现及运用。
概念
栈是一种只允许在一端进行插入或删除的线性表。
1、栈的操作端通常被称为栈顶，另一端被称为栈底。
2、栈的插入操作称为进栈（压栈|push）；栈删除操作称为出栈（弹栈|pop）。
特点
栈就像一个杯子，我们只能从杯口放和取，所以栈中的元素是“先进后出”的特点。
存储结构
顺序存储的栈称为顺序栈；链式存储的栈称为链式栈。
java实现
我们可以围绕栈的4个元素来实现栈：
2状态：是否栈空；是否栈满。
2操作：压栈push;进栈pop。
顺序栈的实现
顺序栈示意图：
1 package test; 2 /** 3 * 4 * @author Fzz 5 * @date 2018年1月1日 6 * @Description TODO: 7 * 顺序栈(SqStack)一般用数组来实现，主要有四个元素：2状态2操作。 8 * 2状态：栈空？；栈满？ 9 * 2操作：压栈push；弹栈pop。 10 * @param <T> 11 */ 12 public class SqStack<T> { 13 private T data[];//用数组表示栈元素 14 private int maxSize;//栈空间大小(常量) 15 private int top;//栈顶指针(指向栈顶元素) 16 17 @SuppressWarnings("unchecked") 18 public SqStack(int maxSize){ 19 this.maxSize = maxSize; 20 this.data = (T[]) new Object[maxSize];//泛型数组不能直接new创建，需要使用Object来创建(其实一开始也可以直接使用Object来代替泛型) 21 this.top = -1;//有的书中使用0，但这样会占用一个内存 22 } 23 24 //判断栈是否为空 25 public boolean isNull(){ 26 boolean flag = this.top<=-1?true:false; 27 return flag; 28 } 29 30 //判断是否栈满 31 public boolean isFull(){ 32 boolean flag = this.top==this.maxSize-1?true:false; 33 return flag; 34 } 35 36 //压栈 37 public boolean push(T vaule){ 38 if(isFull()){ 39 //栈满 40 return false; 41 }else{ 42 data[++top] = vaule;//栈顶指针加1并赋值 43 return true; 44 } 45 } 46 47 //弹栈 48 public T pop(){ 49 if(isNull()){ 50 //栈为空 51 return null; 52 }else{ 53 T value = data[top];//取出栈顶元素 54 --top;//栈顶指针-1 55 return value; 56 } 57 } 58 59 }
测试：
package test; import org.junit.Test; public class test { @Test public void fun(){ //初始化栈(char类型) SqStack<Character> stack = new SqStack<Character>(10); //2状态 System.out.println("栈是否为空："+stack.isNull()); System.out.println("栈是否已满："+stack.isFull()); //2操作 //依次压栈 stack.push('a'); stack.push('b'); stack.push('c'); //依次弹栈 System.out.println("弹栈顺序："); System.out.println(stack.pop()); System.out.println(stack.pop()); System.out.println(stack.pop()); } }
链式栈的实现
链式栈示意图：
1 package test; 2 3 /** 4 * @author Fzz 5 * @date 2018年1月1日 6 * @Description TODO: 7 * 链栈(LinkStack)用链表来实现，主要有四个元素：2状态2操作。 8 * 2状态：栈空？；栈满（逻辑上永远都不会栈满，除非你的电脑没内存了^_^）。 9 * 2操作：压栈push；弹栈pop。 10 * @param <T> 11 */ 12 class LinkStack<T>{ 13 //栈顶节点 14 private LinkNode<T> top; 15 16 //初始化1 17 public LinkStack(){ 18 this.top = new LinkNode<T>(); 19 } 20 21 //初始化栈 22 public void initStack(){ 23 this.top.setData(null); 24 this.top.setNext(null); 25 } 26 //是否栈空 27 public boolean isNull(){ 28 boolean flag = top.getNext()==null?true:false; 29 return flag; 30 } 31 32 //压栈 33 public void push(LinkNode<T> node){ 34 if(isNull()){ 35 //栈空，即第一次插入 36 top.setNext(node); 37 node.setNext(null);//该句可以省略(首次插入的元素为栈底元素) 38 }else{ 39 node.setNext(top.getNext()); 40 top.setNext(node); 41 } 42 } 43 44 //弹栈 45 public LinkNode<T> pop(){ 46 if(isNull()){ 47 //栈空无法弹栈 48 return null; 49 }else{ 50 LinkNode<T> delNode = top.getNext();//取出删除节点 51 top.setNext(top.getNext().getNext());//删除节点 52 return delNode; 53 } 54 } 55 } 56 57 58 //链式栈节点（外部类实现，也可以使用内部类） 59 class LinkNode<T>{ 60 private T data;//数据域 61 private LinkNode<T> next;//指针域 62 63 //初始化1 64 public LinkNode(){ 65 this.data = null; 66 this.next = null; 67 } 68 69 //初始化2 70 public LinkNode(T data) { 71 super(); 72 this.data = data; 73 this.next = null; 74 } 75 public T getData() { 76 return data; 77 } 78 public void setData(T data) { 79 this.data = data; 80 } 81 public LinkNode<T> getNext() { 82 return next; 83 } 84 public void setNext(LinkNode<T> next) { 85 this.next = next; 86 } 87 }
测试：
1 package test; 2 3 import org.junit.Test; 4 5 public class test { 6 7 @Test 8 public void fun(){ 9 LinkStack<Character> ls = new LinkStack<Character>(); 10 11 //1状态 12 System.out.println("栈是否为空："+ls.isNull()); 13 14 //2操作 15 //依次压栈 16 ls.push(new LinkNode<Character>('a')); 17 ls.push(new LinkNode<Character>('b')); 18 ls.push(new LinkNode<Character>('c')); 19 20 //依次弹栈 21 System.out.println("弹栈顺序："); 22 System.out.println(ls.pop().getData()); 23 System.out.println(ls.pop().getData()); 24 System.out.println(ls.pop().getData()); 25 } 26 }
栈的应用
栈结构是很基本的一种数据结构，所以栈的应用也很常见，根据栈结构“先进后出”的特点，我们可以在很多场景中使用栈，下面我们就是使用上面我们已经实现的栈进行一些常见的应用：十进制转N进制、行编辑器、校验括号是否匹配、中缀表达式转后缀表达式、表达式求值等。
十进制转换为N进制
如将十进制123456转换为16进制，我们需要用123456除以16后取余压栈，然后用商继续除以16取余压栈，重复以上操作，直到商为0，这样保存在栈中的余数从栈顶到栈底开始排列形成的数字就是16进制了。（注：大于等于10的余数我们要用字母来表示）。
1 package test; 2 3 public class StackUtils{ 4 public static SqStack<?> ss ; 5 6 //弹栈出所有元素 7 public static Object[] popAll(SqStack<?> s){ 8 ss = s; 9 if(ss.isNull()){ 10 return null; 11 }else{ 12 Object[] array = new Object[ss.getTop()+1]; 13 int i = 0; 14 while(!ss.isNull()){ 15 array[i]=ss.pop(); 16 i++; 17 } 18 return array; 19 } 20 } 21 22 //使用栈进行进制装换 23 public static String integerToNhex(Integer num,int hex){ 24 //对传入的进制进行判断 25 if(hex<=0||hex>36){ 26 return "请输入有效的进制"; 27 }else if(num==0){ 28 return "0"; 29 }else if(num>0){//正数 30 SqStack<Integer> stack = new SqStack<Integer>(16); 31 int index = num; 32 while(num!=0){ 33 num = num / hex ; 34 int remainder = index % hex;//取余压栈 35 stack.push(remainder); 36 index = num; 37 } 38 Object[] o = popAll(stack);//弹栈取出余数 39 StringBuilder sb = new StringBuilder(); 40 for(Object i : o){ 41 int in = (int)i; 42 //取出的数字如果>=10需要用字母代替 43 if(in>=10){ 44 char c = (char) ('a'+in-10); 45 sb.append(c); 46 }else{ 47 sb.append(i); 48 } 49 } 50 return sb.toString(); 51 }else{//负数 52 num = -num;//先去负号 53 SqStack<Integer> stack = new SqStack<Integer>(16); 54 int index = num; 55 while(num!=0){ 56 num = num / hex ; 57 int remainder = index % hex;//取余压栈 58 stack.push(remainder); 59 index = num; 60 } 61 Object[] o = popAll(stack);//弹栈取出余数 62 StringBuilder sb = new StringBuilder(); 63 sb.append("-");//添加负号 64 for(Object i : o){ 65 int in = (int)i; 66 //取出的数字如果>=10需要用字母代替 67 if(in>=10){ 68 char c = (char) ('a'+in-10); 69 sb.append(c); 70 }else{ 71 sb.append(i); 72 } 73 } 74 return sb.toString(); 75 } 76 } 77 78 }
测试：
package test; import org.junit.Test; public class test { @Test public void fun(){ String s = StackUtils.integerToNhex(123456, 16); System.out.println("转换得到的16进制数为:"+s); } }
校验括号是否匹配
1 package test; 2 3 public class StackUtils{ 4 5 //表达式括号是否匹配()[]{} 6 public static boolean isMatch(String str) { 7 SqStack<Character> stack = new SqStack<Character>(str.length()+1); 8 char[] arr = str.toCharArray(); 9 for (char c : arr) { 10 //遇到左括号进栈 11 if(c=='('||c=='['||c=='{'){ 12 stack.push(c); 13 } 14 //遇到右括号匹配栈顶符号 15 else if(c==')'){ 16 if(stack.isNull()){ 17 return false;//栈为空,匹配失败 18 }else if(stack.pop()=='('){ 19 continue;//匹配成功继续下一次循环 20 }else{ 21 return false;//匹配不成功代表该表达式不符合规则 22 } 23 } 24 else if(c==']'){ 25 if(stack.isNull()){ 26 return false;//栈为空,匹配失败 27 }else if(stack.pop()=='['){ 28 continue;//匹配成功继续下一次循环 29 }else{ 30 return false;//匹配不成功代表该表达式不符合规则 31 } 32 } 33 else if(c=='}'){ 34 if(stack.isNull()){ 35 return false;//栈为空,匹配失败 36 }else if(stack.pop()=='{'){ 37 continue;//匹配成功继续下一次循环 38 }else{ 39 return false;//匹配不成功代表该表达式不符合规则 40 } 41 } 42 } 43 //如果最后没有右括号但是还存在左括号表示不匹配 44 return stack.isNull(); 45 } 46 47 }
测试：
1 package test; 2 3 import org.junit.Test; 4 5 public class test { 6 @Test 7 public void fun(){ 8 String str1 = "i((l)o[v{e}]y)o{u}!";//表达式1：(()[{}]){} 9 String str2 = "you((do)[not{}])know{}!)";//表达式2：(()[{}]){}) 10 boolean match1 = StackUtils.isMatch(str1); 11 boolean match2 = StackUtils.isMatch(str2); 12 System.out.println("str1中的括号是否匹配："+match1); 13 System.out.println("str2中的括号是否匹配："+match2); 14 } 15 }
作者：风之之
欢迎任何形式的转载，但请务必注明出处。
由于笔者水平有限，如果文章或代码有表述不当之处，还请不吝赐教。喵~
发表评论 取消回复