作者: 程序员will | 来源:发表于2019-11-04 15:33 被阅读0次

    数据结构之栈

    原理

    栈是一种比较常见的数据结构,它的操作可以看做是数组的子集,因为栈只能从栈顶取元素和添加元素,并且栈遵循先进后出原则,即First in last out(FILO).

    栈的运用很广泛,比如在操作系统中,系统常常在运行过程中,会中途去执行另外的程序,随后再返回执行原程序,那么系统是如何找到之前中断程序的位置的呢?答案是系统中维护了一个系统栈。

    fun A(){
    ....
    B()
    ...
    }
    fun B(){
    ....
    C()
    ....
    }
    fun C(){
    ...
    ...
    ...
    }
    

    比如在上方的程序A中,当A运行到第二行时,程序会去执行B方法,此时系统会将A2压入系统栈,随后再去执行B,当B运行到第二行时,程序又进行跳转到C方法,同理,此时程序会将B2压入栈。

    那么此时栈中一共有两个元素,自顶向下分别为B2、A2,于是当程序执行完C方法时,会将B2出栈,那么程序就回到B2行接着往下执行,同理当B方法执行完,A2出栈,程序回到A2行继续执行,直到完成。

    栈的基本实现

    实现一个栈,这里采用的是构造一个栈结构的接口,写一个实现类实现该接口,接口类变量为上一节实现的动态数组,因为栈的操作可以看做是数组的子集。
    具体代码如下:
    接口类

    public interface Stack<E> {
        int getSize();
        boolean isEmpty();
        void push(E e);
        E pop();
        E peek();
    }
    

    这里也运用了泛型,使其能够接受任意的类型的变量。

    实现类:

    public class ArrayStack<E> implements Stack<E> {
        Array<E> array;
    
        //有参的构造函数
        public ArrayStack(int capacity){
            array = new Array<E>(capacity);
        }
    
        //无参的构造函数
        public ArrayStack(){
            array = new Array<>();
        }
    
        @Override
        public int getSize() {
            return array.getSize();
        }
    
        @Override
        public boolean isEmpty() {
            return array.isEmpty();
        }
    
        @Override
        public void push(E e) {
            array.addLast(e);
        }
    
        @Override
        public E pop() {
            return array.removeLast();
        }
    
        @Override
        public E peek() {
            return array.getLast();
        }
    
        public int getCapacity(){
            return array.getCapacity();
        }
    
        @Override
        public String toString(){
            StringBuilder rst = new StringBuilder();
            rst.append("Stack:");
            rst.append("[");
            for(int i = 0; i < array.getSize(); i++){
                rst.append(array.get(i));
    
                if(i != array.getSize()-1){
                    rst.append(",");
                }
            }
            rst.append("] top");
            return rst.toString();
        }
    }
    

    测试类:

    public class Main {
    
        public static void main(String[] args) {
            ArrayStack<Integer> stack = new ArrayStack<>();
    
            for(int i = 0; i < 5; i++){
                stack.push(i);
                System.out.println(stack);
            }
    
            stack.pop();
            System.out.println(stack);
        }
    }
    

    测试结果

    Stack:[0] top
    Stack:[0,1] top
    Stack:[0,1,2] top
    Stack:[0,1,2,3] top
    Stack:[0,1,2,3,4] top
    Stack:[0,1,2,3] top
    

    这里还缺少了我们实现的动态数组类,详情可以看上一节数组章节。

    应用(括号匹配)

    利用栈这种类型的数据结构,可以解决一些算法问题。

    比如leetcode中第20题,括号匹配的问题。

    即这样的字符串"{[()]}"是正确的,但是"[(}]"这样的就是错误的,你需要设计一个方法,判断传入的这种类型的字符串是否是正确的。

    class Solution {
            public boolean isValid(String s){
                Stack<Character> stack = new Stack<>();
                for (int i = 0; i < s.length(); i++){
                    char c = s.charAt(i);
    
                    if(c == '(' || c == '{' || c == '[')
                        stack.push(c);
                    else {
                        if(stack.isEmpty())
                            return false;
                        char topChar = stack.pop();
                        if(c == ')' && topChar != '(')
                            return false;
                        if(c == '}' && topChar != '{'){
                            return false;
                        }
                        if(c == ']' && topChar != '['){
                            return false;
                        }
                    }
                }
                return stack.isEmpty();
            }
        }
    

    示例代码

    相关文章

      网友评论

        本文标题:

        本文链接:https://www.haomeiwen.com/subject/xhjdbctx.html