导读

  栈和队列是有操作限制的线性表。

目录

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 }
SqStack

   测试:

复制代码
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 }
LinkStack

  测试:

复制代码
 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 }
StackUtils

  测试:

复制代码
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 }
isMatch

  测试:

复制代码
 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 }
复制代码

作者:风之之
欢迎任何形式的转载,但请务必注明出处。
由于笔者水平有限,如果文章或代码有表述不当之处,还请不吝赐教。喵~

点赞(0)

评论列表 共有 0 条评论

暂无评论
立即
投稿
发表
评论
返回
顶部