使用 Java 集合类中的 LinkedList 模拟栈以此判断字符串是否是回文

一、目的

1. 掌握栈后进先出的核心特性，理解利用栈判断回文字符串的原理；

2. 掌握Java集合中 LinkedList 的使用，理解其模拟栈的两种实现方式；

二、实验步骤与常见问题及解决过程

1.解释使用栈判断回文的原理

1.1回文的定义：回文是指一个字符串正读和反读完全一致（如 abba、abcba）。

1.2栈的特性：后进先出。

1.3用栈判断回文的核心思路：利用栈的反转特性：将所有字符压入栈再依次取出可以达到逆转字符串的功能，最后将得到的字符串与原字符串进行对比。

1.4实验步骤

1）入栈：将字符串的每个字符依次压入栈中

2）出栈对比：将栈中的字符依次弹出，与原字符串的字符从头开始逐一比对；

3）结果判断：若所有字符都匹配，则是回文；若任意位置不匹配，则不是回文。

2.使用LinkedList中的哪些方法来代替入栈与出栈

2.1方法一：栈顶对应 LinkedList 的尾部（用 addLast 和 removeLast 方法）

2.1.1代码展示：

import java.util.LinkedList; import java.util.Scanner; public class Main { public static void main(String[] args) { // 创建扫描器接收用户输入 Scanner scanner = new Scanner(System.in); System.out.print("请输入待判断的字符串："); String input = scanner.nextLine(); // 调用回文判断方法 boolean isPalindrome = checkPalindrome(input); // 输出判断结果 if (isPalindrome) { System.out.println(input + " 是回文字符串"); } else { System.out.println(input + " 不是回文字符串"); } scanner.close(); } public static boolean checkPalindrome(String str) { // 1. 初始化LinkedList模拟栈 LinkedList<Character> stack = new LinkedList<>(); // 2. 入栈：将字符串每个字符添加到链表尾部 for (int i = 0; i < str.length(); i++) { stack.addLast(str.charAt(i)); } // 3. 出栈对比：弹出尾部字符（模拟pop），与原字符串从头比对 for (int i = 0; i < str.length(); i++) { char popChar = stack.removeLast(); // 栈空时removeLast会抛异常，但str长度匹配时不会触发 if (popChar != str.charAt(i)) { return false; // 任意字符不匹配，直接返回false } } return true; } }

2.1.2运行结果展示

1）回文字符串测试

2）非回文字符串测试

2.2方法二：栈顶对应 LinkedList 的头部（用 push 和 pop 方法）

2.2.1 代码展示：

import java.util.LinkedList; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); System.out.print("请输入待判断的字符串："); String input = scanner.nextLine(); // 调用回文判断方法 boolean isPalindrome = checkPalindrome(input); // 输出判断结果 if (isPalindrome) { System.out.println(input + " 是回文字符串"); } else { System.out.println(input + " 不是回文字符串"); } scanner.close(); // 关闭扫描器释放资源 } public static boolean checkPalindrome(String str) { LinkedList<Character> stack = new LinkedList<>(); // 入栈：push()加到链表头部 for (int i = 0; i < str.length(); i++) { stack.push(str.charAt(i)); } // 出栈：pop()取出逆序序列，与原字符串的正序比对 for (int i = 0; i < str.length(); i++) { char popChar = stack.pop(); // 直接和原字符串的第i位进行对比 if (popChar != str.charAt(i)) { return false; } } return true; } }

2.2.2 运行结果展示

1）回文字符串测试

2）非回文字符串测试

三、实验小结

3.1学习思考

一开始把 LinkedList 中的 push 和 pop 方法与 C++ STL 的 <stack> 中的 push 和 pop 函数混为一谈了，<stack> 中的 push 是向底层容器的尾部压入元素；pop 是从底层容器的尾部弹出元素，于是理所当然认为 LinkedList 中的 push 和 pop 方法也是对链表的尾部进行操作。但其实事实是，LinkedList 的 push 和 pop 方法是对链表的头部进行操作，原理是 LinkedList 实现了 Deque（双端队列）接口，而 Deque 对栈的模拟遵循头部为栈顶的约定。

3.2学习记录

LinkedList模拟栈的核心方法对照表：

栈的核心是后进先出，栈顶不论是对应链表的头部还是尾部，只是具体实现细节，只要入栈和出栈的位置一一匹配，就能保证栈的核心特性。