Java玩转《啊哈算法》解密回文之栈

菩萨清凉月，常游毕竟空，众生心垢净，菩提影现中。

这目录

这开头
这代码地址
栈
- 案例
- 代码
- 优化建议
- 类似
- 扩展

这开头

各位女士们，先生们好！本人最近在看《啊哈算法》，这本书写的确实还可以，很有趣味性。

但略微遗憾的是，书籍示例代码是c语言，而不是本人常用的Java。

那就弥补遗憾吧。于是乎说干就干，把这本书的示例语言用java写一遍，顺带夹杂一些私货，附上自己的一些理解！

于是就有了本篇博客，本篇博客主要是讲常见数据结构的一种：栈。

在这里插入图片描述

来不及买纸质书但又想尽快感受算法魅力的童鞋也甭担心，电子版的下载链接已经放到下方了，可尽情下载。

链接：https://pan.baidu.com/s/1imxiElcCorw2F-HJEnB-PA?pwd=jmgs
提取码：jmgs

在这里插入图片描述

这代码地址

本文代码已开源：

git clone https://gitee.com/guqueyue/my-blog-demo.git

请切换到gitee分支，

然后查看aHaAlgorithm模块下的src/main/java/com/guqueyue/aHaAlgorithm/chapter_2_StackAndChainTable即可！

栈

在上期博客：Java玩转《啊哈算法》解密QQ号之队列中，我们说到
在这里插入图片描述

而与队列相对的栈，也有一个非常核心的概念：FILO(First In Last Out) - 先进后出
在这里插入图片描述

如上图，栈就像往桶里面放球，先放进去的球，要后面才能拿出来。

在这里插入图片描述

这也暗合一句歇后语：砌墙的石头 —— 后来居上。

当然，在我往期的博客：递归和循环之间不得不说的故事中，里面也有生动形象的动图用来理解栈，这里就不多加赘述。

同样的，栈也只有两种操作：

新来的元素入栈。
栈顶的元素出栈。

案例

同样的，作者这里也用了一个案例，来引出栈：

栈究竟有哪些作用呢？
我们来看一个例子。“xyzyx”是一个回文字符串，所谓回文字符串就是指正读反读均相同的字符序列，如“席主席”、“记书记”、“aha”和“ahaha”均是回文，但“ahah”不是回文。通过栈这个数据结构我们将很容易判断一个字符串是否为回文。

我们来分析一下这道题目，关于回文串，无非就是左右对称嘛。

那么，我们只需要如下几步即可：

求出中心对称点。将回文串分为 左串 和 右串 。
将 左串 以 从右到左 的顺序和 右串 以 从左到右的顺序进行逐个字符匹配。若全匹配上，则为回文串；反之，则不然。
我们只需要将左串 以 从左到右 的顺序入栈，由于栈为先进后出，所以我们只需要出栈，即为从右到左。

那么，我们只需要边匹配边出栈，匹配上则出栈；匹配不上，则结束匹配。

如果匹配结束，栈为空，则说明是回文串；反之，则不是。

代码

理论讲完了，下面直接上代码：

package com.guqueyue.aHaAlgorithm.chapter_2_StackAndChainTable;

import java.util.Scanner;

/**
 * @Author: guqueyue
 * @Description: 通过栈判断是否为回文串
 * @Date: 2024/1/12
 **/
public class PalindromeStr {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        System.out.print("请输入一段字符串：");
        String str = scanner.nextLine();

        // 获取字符串长度 以及 字符串中心点
        int len = str.length();
        int mid = len / 2 - 1;

        // 初始化栈并入栈 - 左串
        char[] stack = new char[101];
        int top = -1;
        for (int i = 0; i <= mid; i++) {
            stack[++top] = str.charAt(i);
        }

        // 获取起始匹配点 - 长度为偶数为 mid+1, 奇数为 mid+2
        int next = (len % 2 == 0) ? mid + 1 : mid + 2;
        // 开始匹配 - 右串
        for (int i = next; i <= len - 1; i++) {
            if (str.charAt(i) != stack[top]) {
                break;
            }

            top--;
        }
		
		// 若栈顶为-1, 即栈为空，则是回文串
        System.out.println(top == -1 ? "YES" : "NO");
    }
}

运行，若输入aha：
在这里插入图片描述
若输入ahah：

完美！！！

优化建议

当然，我们也可以把数组和栈顶指针抽出来封装成栈类再使用，如：

package com.guqueyue.aHaAlgorithm.entity;

/**
 * @Author: guqueyue
 * @Description: 栈 - 字符栈
 * @Date: 2024/2/5
 **/
public class CharStack {

    public char[] data = new char[10]; // 数组，用来存储栈的内容
    public int top = -1; // 栈顶
}

然后，小幅改动即可：

package com.guqueyue.aHaAlgorithm.chapter_2_StackAndChainTable;

import com.guqueyue.aHaAlgorithm.entity.CharStack;

import java.util.Scanner;

/**
 * @Author: guqueyue
 * @Description: 通过栈判断是否为回文串
 * @Date: 2024/2/5
 **/
public class PalindromeStr2 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        System.out.print("请输入一段字符串：");
        String str = scanner.nextLine();

        // 获取字符串长度 以及 字符串中心点
        int len = str.length();
        int mid = len / 2 - 1;

        // 初始化栈并入栈 - 左串
        CharStack stack = new CharStack();
        for (int i = 0; i <= mid; i++) {
            stack.data[++stack.top] = str.charAt(i);
        }

        // 获取起始匹配点 - 长度为偶数为 mid+1, 奇数为 mid+2
        int next = (len % 2 == 0) ? mid + 1 : mid + 2;
        // 开始匹配 - 右串
        for (int i = next; i <= len - 1; i++) {
            if (str.charAt(i) != stack.data[stack.top]) {
                break;
            }

            stack.top--;
        }

        // 若栈顶为-1, 即栈为空，则是回文串
        System.out.println(stack.top == -1 ? "YES" : "NO");
    }
}