数据结构之栈及Java实现

た入场券 2022-05-27 06:17 147阅读 0赞

## 一、栈的基本介绍 ##

栈是一种只允许在一端进行插入或删除的线性表，也就是说先进后出。栈的操作端通常被称为栈顶，另一端被称为栈底，栈的插入操作称为压栈（push），栈删除操作称为出栈（pop）。压栈是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；出栈则是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。  
![这里写图片描述][70]

## 二、栈的Java实现 ##

栈的实现方式主要分为两种，一种是基于数组实现的，另一种则是基于链表。顺序存储的栈称为顺序栈；链式存储的栈称为链式栈。不管是基于何种形式，一般都要实现几个方法，分别为检查栈是否为空，是否已满，压栈操作和出栈操作，值得说明的是，在链式栈中无需检测栈是否已满，只要内存足够大，原理上链式栈是不会满的。下面分别介绍两种方式的实现：

1.  基于数组的顺序栈  
    ![70 1][]

public class ArrayStack<T> {
        private T data[];
        private int maxSize;
        private int top;
        //初始化栈
        public ArrayStack(int maxSize){
            this.maxSize = maxSize;
            data = (T[]) new Object[maxSize];
            this.top = -1;
        }
        //判断栈是否已空
        public boolean isNull(){
            if(top == -1){
                return true;
            }
            return false;
        }
        //判断栈是否已满
        public boolean isFull(){
            if(top == maxSize-1){
                return true;
            }
            return false;
        }
        //将value压栈
        public boolean push(T value){
            if(isFull()){
                return false; 
            }
            top++;
            data[top] = value;
            return true;
        }
        //取出栈顶元素
        public T pop(){
            if(isNull()){
                return null;
            }
            T tmp = data[top];
            data[top] = null;
            top--;
            return tmp;
        }
        public static void main(String args[]){
            ArrayStack<String> as = new ArrayStack<String>(4);
            as.push("sasa");
            as.push("qwwq");
            as.push("erer");
            as.push("ddsd");
            //测试栈已满时的情况
            System.out.println(as.push("hhhhh"));
            //测试出栈顺序
            System.out.println(as.pop());
            System.out.println(as.pop());
            System.out.println(as.pop());
            System.out.println(as.pop());
    
        }
    
    }

测试结果：

false
    ddsd
    erer
    qwwq
    sasa

1.  基于链表的链式栈  
    ![70 2][]

public class NodeStack<T> {
        private Node<T> top = null;
        public NodeStack(){
            this.top = null;
        }
        //判断栈是否为空
        public boolean isNull(){
            if(top == null){
                return true;
            }
            return false;
        }
        //压栈
        public boolean push(T data){
            Node<T> node = new Node<T>(data);
            node.setNext(top);
            top = node;
            return true;
        }
        //出栈
        public T pop(){
            if(isNull()){
                return null;
            }
            T tmp = top.data;
            top = top.getNext();
            return tmp;
    
        }
        //取出栈顶的值
        public T peek(){
            if(isNull()){
                return null;
            }
            return top.data;
        }
        class Node<T>{
            private T data;
            private Node<T> next;
            public Node(T value){
                this.data = value;
            }
            public Node<T> getNext(){
                return this.next;
            }
            public void setNext(Node<T> n){
                this.next = n;
            }
            public T getData(){
                return this.data;
            }
            public void setData(T d){
                this.data = d;
            }
        }
    
        public static void main(String args[]){
            NodeStack<String> ns = new NodeStack<String>();
    
            //测试是否为空
            System.out.println(ns.isNull());
            //压栈测试
            ns.push("asdwqewqewqea");
            ns.push("ewewwqsdsadsd");
            ns.push("ffddsfsdfdfdf");
            //测试是否为空
            System.out.println(ns.isNull());
            //出栈测试
            System.out.println(ns.pop());
            System.out.println(ns.pop());
            System.out.println(ns.pop());
            //测试是否为空
            System.out.println(ns.isNull());
        }
    
    
    
    }

测试结果：

true
    false
    ffddsfsdfdfdf
    ewewwqsdsadsd
    asdwqewqewqea
    true

## 三、栈相关算法实现 ##

括号匹配问题是栈的一个经典应用示例，输入表达式即一个字符串，判断这个字符串的括号是不是匹配。

思路如下所示：

1.循环遍历字符串，读取字符每一个字符
        1.1如果是左括号，则入栈；
        1.2如果ch是右括号，则需要进一步判断：
            如果栈空：
                说明多出右括号，直接返回false；
            如果栈不空，ch和栈顶比较：
                如果不同，返回false；
                如果匹配，则出栈一次；
    2.循环结束后栈空，说明左括号匹配完了，则返回true，循环结束后栈不空，则返回false。

实现代码

public class StrMatch {
    
        public boolean match(String str){
            NodeStack<Character> strMatch = new NodeStack<Character>();
            char tmp;
            //循环遍历字符串
            for(int i=0;i<str.length();i++){
                tmp = str.charAt(i);
                //判断是否为左括号
                if(isLeft(tmp)){
                    //左括号入栈
                    strMatch.push(tmp);
                }
                //判断是否为右括号
                else if(isRight(tmp)){
                    //如果栈已空，则右括号不能匹配，返回false
                    if(strMatch.isNull()){
                        return false;
                    }
                    //如果右括号与栈顶的左括号相匹配，移除栈顶的左括号
                    if(corespd(strMatch.peek(),tmp)){
                        strMatch.pop();
                    }
                }
            }
            //循环遍历结束，如果栈已空，则说明匹配完毕，返回true
            if(strMatch.isNull()){
                return true;
            }
            //否则，返回false
            return false;
        }
        //判断左右括号是否对应
        public boolean corespd(char a,char b){
            if(a == '('&&b ==')')
                return true;
            if(a == '['&&b==']')
                return true;
            if(a == '{'&&b == '}')
                return true;
            return false;
        }
        //判断是否为左括号
        public boolean isLeft(char c){
            if(c == '(' || c == '[' ||c == '{'){
                return true;
            }
            return false;
        }
        //判断是否为右括号
        public boolean isRight(char c){
            if(c == ')' || c==']' || c=='}'){
                return true;
            }
            return false;
        }
        public static void main(String[] args) {
            // 测试字符串
            StrMatch sm = new StrMatch();
            String inputStr1 = "{[(2+4)+(3-5)/9]*4+1}*{[(2-4)+(3-5)*9]*(4+1)}";
            String inputStr2 = "{[(2+4)+(3-5)/9]*4+1}*{[(2-4)+(3-5)*9]*(4+1}";
            String inputStr3 = "{[(2+4)+(3-5)/9]*4+1}*[(2-4)+(3-5)*9]*(4+1)}";
            System.out.println(sm.match(inputStr1));
            System.out.println(sm.match(inputStr2));
            System.out.println(sm.match(inputStr3));
        }
    
    }

输出结果

true
    false
    false

[70]: /images/20220527/f5eafeef860c4aabbcc02915af1c4a24.png
[70 1]: /images/20220527/f467d3eeef13479aba57806433b27db5.png
[70 2]: /images/20220527/338f749a10eb43a9aca85a1078a13407.png