【数据结构】——栈 (链栈和基于Java的运算实现)

目录

链式存储 (链栈)

基本运算实现

栈的应用举例

圆括号匹配检验

字符串回文的判断

数制转换

链式存储 (链栈)

概述：插入和删除限制在表头位置(栈顶)进行，将单链表的头指针head改为栈顶指针top即可。

图示：

基本运算实现

//链表结点类
public class Node {
    //数据域
    private Object data;
    //指针域
    private Node next;

    public Node() {
    }

    public Node(Object data, Node next) {
        this.data = data;
        this.next = next;
    }

    public Object getData() {
        return data;
    }

    public void setData(Object data) {
        this.data = data;
    }

    public Node getNext() {
        return next;
    }

    public void setNext(Node next) {
        this.next = next;
    }
}

public class StackNode {
    //定义头指针
    Node top = null;
    //定义链栈长度
    int size;

    //判栈空
    public boolean StackEmpty(){
        return size == 0;
    }

    //进栈（入栈）
    public void Push(Object x){
        //申请新结点
        Node n = new Node();
        //数据域赋值
        n.setData(x);
        //新结点插入栈顶
        n.setNext(top);
        //top指向新的栈顶
        top = n;
        //链表长度加1
        size++;
    }

    //退栈（出栈）
    public Object Pop(){
        //保存栈顶指针
        Node node = top;
        if (StackEmpty()){
            System.out.println("stack empty!");
            return null;
        }else {
            //保存删除的结点值
            Object x = node.getData();
            //栈顶指针指向下一个结点
            top = node.getNext();
            //链表长度减1
            size--;
            //返回被删除的元素值
            return x;
        }
    }

    //遍历栈
    public void StackNodeShow(){
        //定义一个新结点
        Node node = top;
        for (int i = 0; i < size; i++) {
            System.out.println(node.getData());
            //移动新结点
            node = node.getNext();
        }
    }

    //取栈顶元素
    public Object GetTop() {
        //判断是否栈空
        if (StackEmpty()) {
            System.out.println("stack empty!");
            return null;
        } else return top.getData();
    }
}

public class StackNodeTest {
    public static void main(String[] args) {
        //创建链栈
        StackNode stackNode = new StackNode();

        //判栈空
        boolean b = stackNode.StackEmpty();
        System.out.println("栈是否为空：" + b);
        System.out.println();

        //进栈（入栈）
        stackNode.Push("xx");
        stackNode.Push("hh");
        stackNode.Push("zz");
        stackNode.Push("kk");
        //遍历栈
        System.out.println("遍历栈(先进后出)：");
        stackNode.StackNodeShow();
        //取栈顶元素
        Object o = stackNode.GetTop();
        System.out.println("栈顶元素为："+o);
        System.out.println("链表长度为："+stackNode.size);
        System.out.println();

        //退栈（出栈）
        stackNode.Pop();
        stackNode.Pop();
        //遍历栈
        System.out.println("遍历栈(先进后出)：");
        stackNode.StackNodeShow();
        //取栈顶元素
        Object o1 = stackNode.GetTop();
        System.out.println("栈顶元素为："+o1);
        System.out.println("链表长度为："+stackNode.size);
    }
}

运行结果：

栈的应用举例

圆括号匹配检验

说明：对于输入的一个算术表达式字符串，该算法用于判断其中圆括号是否匹配，匹配返回True，否则返回False。

实现思路：循环读入表达式中的字符，如遇左括号 “(” 就进栈，遇右括号 ”)“ 则判断是否为空，若为空，返回False，否则退栈；循环结束后再判断栈是否为空，若栈空说明括号匹配，否则说明不匹配。

代码实现：基于上边定义的链栈实现的。

public class StackNodeTest {
    public static void main(String[] args) {
        String s = "(15+36)*(4*5)";
        boolean expr = Expr(s);
        System.out.println("括号是否合法：" + expr);

        String s1 = "(15)+36(()*(4*5)";
        boolean expr1 = Expr(s1);
        System.out.println("括号是否合法：" + expr1);
    }

    public static boolean Expr(String s) {
        //创建一个链栈
        StackNode stackNode = new StackNode();
        //循环字符串
        for (int i = 0; i < s.length(); i++) {
            //遇到左括号进栈
            if (s.charAt(i) == '(') {
                stackNode.Push(s.charAt(i));
            } else if (s.charAt(i) == ')') {
                //判栈空
                if (stackNode.StackEmpty()) {
                    //结束运行
                    System.exit(0);
                } else stackNode.Pop(); //遇右括号退栈
            }
        }
        if (stackNode.StackEmpty())
            return true;
        else return false;
    }
}

运行结果：

字符串回文的判断

说明：判断一个字符串是否具有中心对称，正读和反读均相同的字符序列，例如：ababbbaba和 abcba都是中心对称的字符串。

实现思路：首先要知道中心在哪，从中间向两头进行比较，若完全相同，则该字符串是中心对称，否则不是。首先求出字符串的长度，然后将前一半字符入栈，再利用退栈操作将其与后一半字符进行比较。

代码实现：基于上边定义的链栈实现的。

public class StackNodeTest {
    public static void main(String[] args) {
        String s = "abcdaad";
        boolean symmetry = symmetry(s);
        System.out.println("是否是回文字符串：" + symmetry);

        String s1 = "ababbaba";
        boolean symmetry1 = symmetry(s1);
        System.out.println("是否是回文字符串：" + symmetry1);
    }

    public static boolean symmetry(String s) {
        //创建一个链栈
        StackNode stackNode = new StackNode();
        //循环字符串长度的一半
        for (int i = 0; i < s.length() / 2; i++) {
            //前一半字符入栈
            stackNode.Push(s.charAt(i));
        }
        //后一半字符在串中的起始位置
        int k = (s.length() + 1) / 2;
        //后一半字符与栈中字符比较
        for (int i = k; i < s.length(); i++) {
            //退栈依次获取元素,如果有不相同的字符就是不对称
            if ((char) stackNode.Pop() != s.charAt(i))
                return false;
        }
        return true;
    }
}

运行结果：

数制转换

说明：将一个非负的十进制整数N转换成d进制，原理：N = (N/d)*d + N%d，解该题的前提是要会各个进制之间的转换，如果有不懂或者忘了的小伙伴可以参考博主这篇文章：各个进制的概念与转换（二、八、十、十六进制）_South.return-CSDN博客

实现思路：将计算过程中得到的d进制数的各位数字顺序进栈，按出栈序列顺序输出得到的数就是十进制数所对应的d进制数。

代码实现：基于上边定义的链栈实现的。

public class StackNodeTest {
    public static void main(String[] args) {
        conversion(150, 8);
        System.out.println();

        conversion(150, 16);
        System.out.println();
        System.out.println();

        conversion(3553, 8);
        System.out.println();

        conversion(3553, 16);
        System.out.println();
    }

    //将一个非负的十进制数N转换成任意的d进制数
    public static void conversion(int N, int d) {
        //创建一个链栈
        StackNode stackNode = new StackNode();
        //当N大于1时循环
        while (N > 1) {
            //取模，获取余数
            stackNode.Push(N % d);
            N = N / d;
        }
        //退栈
        while (!stackNode.StackEmpty()) {
            Object pop = stackNode.Pop();
            System.out.print(pop);
        }
    }
}

运行结果：

---