数据结构——栈的使用

青旅半醒 2022-07-17 04:08 74阅读 0赞

## 栈是常见的数据结构，stack可以说是内存中具有重要的用途，比如说在JVM中就有本地方法栈，在方法的调用中会产生调用栈，在主栈里面调用方法/函数（C语言也是如此），临时变量或者局部变量都会在stack结构中，stack是一种临时的内存模型，调用栈在方法退出时系统会得到回收。在微机系统中常会遇到中断的情况，从中断请求到保护断点以及中断程序响应执行与返回整个过程都与栈结构密切相关。 ##

![这里写图片描述][20160830222922886]

## 栈简单地说就是一种的先进后出的结构。一般情况下有入栈（push）与出栈（pop）基本操作。 ##

## 下面创建一个数据栈，栈存放的数组。通常除了push、pop操作之外，还常有peek（查看）、判断是否栈容量来决定栈是否full或者Empty状态。 ##

class StackDesign
    {
        private int length=0;
        private int top=-1;
    
        int[] a=null;
        public StackDesign(int length)
        {
            this.length=length;
            a=new int[this.length];
        }
        public void push(int data)
        {
            a[++top]=data;
        }
        public int pop() 
        {
            int value=0;
            value=a[top--];
            return value;
        }
        public boolean isEmpty()
        {
            return top==-1;
        }
        public boolean isFull()
        {
    
            return top==this.length-1;
        }
    
    }

## 以上对类StackDesign的设计基于数据先进后出的思想。在push之前需要判断stack是否isFull，在pop数据之前需要判断stack是否isEmpty。这些都是保证stack安全稳定工作必要的判断。 ##

## 以下是测试代码： ##

StackDesign stackApp=new StackDesign(10);
            stackApp.push(6);
            stackApp.push(7);
            stackApp.push(8);
            stackApp.push(9);
    
            while(!stackApp.isEmpty())
            {
                System.out.println(stackApp.pop());
            }

## 测试结果是： ##

9
    8
    7
    6

## 通过以上的结果来看，类StackDesign符合先进后出的基本特征。stack使用比较广泛，比如说字符串反转，分隔符匹配等，总之凡是符合先进后出的条件均可以考虑stack结构来实现。 ##

## 下面给出使用stack结构实现字符串反转功能。 ##

class StringReverse
    {
    
        char[] buffer=null;
        String s=null;
        public String getS() {
            return s;
        }
    
        public void setS(String s) {
            this.s = s;
        }
    
        public String getWord()
        {
            InputStreamReader isr=new InputStreamReader(System.in);
            BufferedReader br=new BufferedReader(isr);
            System.out.println("please input String :");
            try {
                  s=br.readLine();  
    
            } catch (IOException e) {
                // TODO Auto-generated catch block
                e.printStackTrace();
            }finally
            {
    
                try {
                    br.close();
                    isr.close();
                } catch (IOException e) {
                    // TODO Auto-generated catch block
                    e.printStackTrace();
                }
                return s;
            }
    
        }
    
        public void reverse()
        {
            buffer=new char[this.getS().length()];
            System.out.println(buffer.length);
            for(int i=0;i<buffer.length;i++)
            {
                buffer[i]=this.getS().charAt(i);    
            }
        }   
    
        public void reverseShow()
        {
            String sbuffer="";
            for(int i=buffer.length-1;i>=0;i--)
            {
                sbuffer+=buffer[i]+"";
            }
            System.out.println(sbuffer);
        }
    
    }

## 字符创由用户输入所得。下面是测试代码： ##

StringReverse a=new StringReverse();
    String ddd=a.getWord();
    a.reverse();
    a.reverseShow();

## 以下是测试结果： ##

please input String :
    XYZ
    3
    ZYX

## 以上采用先进后出的思想只需要通过charAt（）方法split各个字符后进行push即可。 ##

## 在常见的IDE种，经常会自动提示匹配符的情况。例如\{（\[\] ) \}这种情况下系统不会提示错误，但是系统检测到用户输入的文本中匹配符是这种情况系统就会提示： ##

## \{\[( \]\} 因为少了一个‘）’,编译器具备这种功能可以通过stack实现。具体过程为：当检测到左匹配符时顺序push压栈，当检测到右匹配符时对栈中的左匹配符进行匹配，若匹配成功则pop左匹配符。没找到左匹配符或者无匹配情况则系统输出提示信息。以下是实现代码： ##

class StackX
    {
            private int length=0;
            int top;
            char[] a=null;
            StringGet sg=null;
            public StackX()
            {
                a=new char[100];
    
            }
            public void push(char ch)
            {
                a[++top]=ch;
            }
            public char pop() 
            {
                char value=0;
                value=a[top--];
                return value;
            }
            public boolean isEmpty()
            {
                return top==-1;
            }
            public boolean isFull()
            {
    
                return top==100;
            }
    
    }

## 以上是创建一个基本的stack结构。 ##

class StringGet
    {
        private int length=0;
        String s;
        InputStreamReader isr=null;
        BufferedReader br=null;
        public StringGet()
        {
            isr=new InputStreamReader(System.in);
            br=new BufferedReader(isr);
        }
        public String str() 
        {
            try {
                 System.out.println("请输入字符串：");
                 s=br.readLine();
            } catch (IOException e) 
            {
                e.printStackTrace();
            }finally
            {
    
                try {
                    br.close();
                    isr.close();
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
    
            return s;
    
        }
    
    }

## 以上创建类StringGet并获取用户输入的字符串（包括匹配符）。 ##

class Check
    {
    
        char[] charBuffer=null;
        int length;
        StackX stack=null;
        StringGet stringGet=null;
        public Check()
        {
            //stack=new StackX();
            stringGet=new StringGet();
            length=stringGet.str().length();
            charBuffer=new char[length];
            for(int i=0;i<length;i++)
            {
                char ch=stringGet.s.charAt(i);
                charBuffer[i]=ch;
                //System.out.println(charBuffer[i]);
            }
        }
        public void checkMatching()
        {
          stack=new StackX();
          boolean flag=false;
           for(int i=0;i<charBuffer.length;i++)
           {
               switch(charBuffer[i])
               {    
               case '{':stack.push(charBuffer[i]); break;
    
               case '(':stack.push(charBuffer[i]); break;
    
               case '[':stack.push(charBuffer[i]); break;
    
               case ']': 
                         for(int j=0;j<charBuffer.length;j++)
                         {
                             if(stack.a[j]=='[')
                             {
                                 System.out.println(stack.pop());
                                 flag=true;
    
                             }
                         }
                         if(!flag)
                         {
                             System.out.println("you should check code: short of '['");
                         }
                         break;
    
    
               case ')':
                           for(int j=0;j<charBuffer.length;j++)
                             {
                                 if(stack.a[j]=='(')
                                 {
                                     System.out.println(stack.pop());
                                     flag=true;
    
                                 }
                             }
                             if(!flag)
                             {
                                 System.out.println("you should check code: short of '('");
                             }
                             break;
    
    
               case '}':
    
    
                           for(int j=0;j<charBuffer.length;j++)
                             {
                                 if(stack.a[j]=='{')
                                 {
                                     System.out.println(stack.pop());
                                     flag=true;
    
                                 }
                             }
                             if(!flag)
                             {
                                 System.out.println("you should check code: short of '{'");
                             }
                             break;
                default :break;     
    
               }
    
    
           }
    
        }
    }

## 以上是check类，主要是完成匹配过程。 ##

Check check=new Check();
            check.checkMatching();

## 以上是测试语句。测试结果如下： ##

请输入字符串：
    xyz[]
    [
    
    请输入字符串：
    xyz]
    you should check code: short of '['

## 可以看出以上能够实现基本的匹配符检测功能。对于更复杂的匹配符检测与匹配则需要完善check类，才能检测出多个匹配符嵌套的匹配。 ##

[20160830222922886]: /images/20220717/1bd84bb0b73141f7a2b3d0b1ef588500.png