【C++数据结构】用栈实现回文字符串的判断（类模板)_用栈实现回文判断的算法

目录

前言：

一、回文字符串判断方法

二、代码实现

1.创建结点

2.创建栈

（1）入栈函数        

（2）出栈函数

（3）清空函数

3.回文判断

（1）创建一个string对象用于存放输出的字符串，创建一个char类型的栈。

（2）将字符串逐个入栈。 

（3）遍历字符串并逐个出栈进行判断。

（4）将上面过程封装成函数，调用函数便可以进行判断。

4.main函数

三、完整代码

---

前言：

        栈实现的是一种后进先出（last-in，first-out，LIFO）策略，将一个正序的数组入栈并出栈后可以得到逆序数组，利用这个特点我们可以很简便地实现回文字符串的判断。

---

提示：以下是本篇文章正文内容，代码注释较为详细，可供参考

一、回文字符串判断方法

        对于一个字符串，如果正读和反读是一样的，那么这个字符串就是回文字符串（例如：“123aa321”）。从编程的角度来说，本质上可以看作其正反序相等。而逆序又可以通过栈实现，有了这个思路我们便可以通过以下步骤来实现回文字符串的判断：

1.定义结点Node和栈Stack

2.创建一个栈并将字符串逐个入栈

3.将栈中元素逐个出栈并与字符串逐个比较，若出现不相等的情况返回并输出非回文字符串，若全部相等则为回文字符串。

        下面开始代码详解和演示：

二、代码实现

1.创建结点

        关于结点的建立就不赘述了，这里要注意的是后面要用到的类模板Stack要先提前声明，否则在Node类里声明友元时会报错。

template<class T>class Stack;	//向前声明
template<class T>
class Node {
private:
	T m_data;	//数据域
	Node* m_next;	//指针域
public:
	Node(const T& val) {
		this->m_data = val;
	}	//有参构造
	Node& operator=(const Node& rhs) = delete;	//禁止赋值
	friend class Stack<T>;	//声明友元
};

2.创建栈

        入栈出栈清空都是基本的写法，不多赘述。

template<class T>
class Stack {
private:
	Node<T>* m_top = nullptr;	//栈顶指针
public:
	Stack() = default;	//默认构造
	Stack(const Stack&) = delete;	//禁止复制
	Stack& operator=(const Stack&) = delete;	//禁止赋值
	~Stack() {
		clear();
	};	//析构
	void clear();	//清空栈
	void push(const T& val);	//入栈
	void pop();//出栈
	bool empty()const {
		return this->m_top == nullptr;
	}	//判断是否为空
	const T& top() {
		return this->m_top->m_data;
	}	//取出栈顶元素
};

（1）入栈函数        

template<class T>
void Stack<T>::push(const T& val) {
	Node<T>* node = new Node<T>(val);
	node->m_next = this->m_top;
	this->m_top = node;
}

（2）出栈函数

template<class T>
void Stack<T>::pop() {
	if (empty()) {
		return;
	}
	Node<T>* p = this->m_top;
	this->m_top = this->m_top->m_next;
	delete p;
}

（3）清空函数

template<class T>
void Stack<T>::clear() {
	Node<T>* p = nullptr;
	while (this->m_top != nullptr) {
		p = this->m_top;
		this->m_top = this->m_top->m_next;
		delete p;
	}
}

3.回文判断

（1）创建一个string对象用于存放输出的字符串，创建一个char类型的栈。

        这里选用char类型是因为其既能存放数字也能存放字母，并可以使用==运算符判断。

string str;		//创建一个string对象，用于存储输入的字符串
	cout << "请输入字符串:";
	cin >> str;

（2）将字符串逐个入栈。 

        注意这里并未考虑中间空格的情况，如有需要可以自行加入跳过空格的判断。

for (int i = 0; i < str.size(); i++) {
		reverse_str.push(str[i]);
	}	//将字符串依次入栈

（3）遍历字符串并逐个出栈进行判断。

        注意要定义一个char对象用来存放字符串的单个字符，这样才能和Stack<char>内的元素进行==运算符判断，判断时调用top（）获取栈顶元素，判断完后调用pop（）将之前的栈顶元素出栈，便可进行下一次判断。

for (int j = 0; j < str.size(); j++) {
		char contract = str[j];		//创建一个char类型对象用来存放str[i]的单个字符，用于判断和依次出栈的char字符是否相等
		if (reverse_str.top() != contract) {
			cout << "此字符串不是回文字符串!" << endl;
			return;
		}	//若遇到一个不相等的直接输出结果并返回
		else reverse_str.pop();
	}	//for遍历str的每个字符进行比较
 
	cout << "此字符串是回文字符串!" << endl;	//若遍历完都无不相等的则说明为回文，输出结果

（4）将上面过程封装成函数，调用函数便可以进行判断。

void check() {
	string str;		//创建一个string对象，用于存储输入的字符串
	cout << "请输入字符串:";
	cin >> str;
	Stack<char> reverse_str;	//创建一个栈
	for (int i = 0; i < str.size(); i++) {
		reverse_str.push(str[i]);
	}	//将字符串依次入栈
	for (int j = 0; j < str.size(); j++) {
		char contract = str[j];		//创建一个char类型对象用来存放str[i]的单个字符，用于判断和依次出栈的char字符是否相等
		if (reverse_str.top() != contract) {
			cout << "此字符串不是回文字符串!" << endl;
			return;
		}	//若遇到一个不相等的直接输出结果并返回
		else reverse_str.pop();
	}	//for遍历str的每个字符进行比较
 
	cout << "此字符串是回文字符串!" << endl;	//若遍历完都无不相等的则说明为回文，输出结果
}

4.main函数

        简洁明了，这就是抽象和封装的好处。

int main()
{
	check();	//调用check()函数
}

三、完整代码

        以下是完整代码展示，由于个人水平有限，如有错误/不严谨的地方敬请指正。

#include <iostream>
#include <string>
using namespace std;
template<class T>class Stack;	//向前声明
template<class T>
class Node {
private:
	T m_data;	//数据域
	Node* m_next;	//指针域
public:
	Node(const T& val) {
		this->m_data = val;
	}	//有参构造
	Node& operator=(const Node& rhs) = delete;	//禁止赋值
	friend class Stack<T>;	//声明友元
};
 
template<class T>
class Stack {
private:
	Node<T>* m_top = nullptr;	//栈顶指针
public:
	Stack() = default;	//默认构造
	Stack(const Stack&) = delete;	//禁止复制
	Stack& operator=(const Stack&) = delete;	//禁止赋值
	~Stack() {
		clear();
	};	//析构
	void clear();	//清空栈
	void push(const T& val);	//入栈
	void pop();//出栈
	bool empty()const {
		return this->m_top == nullptr;
	}	//判断是否为空
	const T& top() {
		return this->m_top->m_data;
	}	//取出栈顶元素
};
 
template<class T>
void Stack<T>::push(const T& val) {
	Node<T>* node = new Node<T>(val);
	node->m_next = this->m_top;
	this->m_top = node;
}
 
template<class T>
void Stack<T>::pop() {
	if (empty()) {
		return;
	}
	Node<T>* p = this->m_top;
	this->m_top = this->m_top->m_next;
	delete p;
}
 
template<class T>
void Stack<T>::clear() {
	Node<T>* p = nullptr;
	while (this->m_top != nullptr) {
		p = this->m_top;
		this->m_top = this->m_top->m_next;
		delete p;
	}
}
 
void check() {
	string str;		//创建一个string对象，用于存储输入的字符串
	cout << "请输入字符串:";
	cin >> str;
	Stack<char> reverse_str;	//创建一个栈
	for (int i = 0; i < str.size(); i++) {
		reverse_str.push(str[i]);
	}	//将字符串依次入栈
	for (int j = 0; j < str.size(); j++) {
		char contract = str[j];		//创建一个char类型对象用来存放str[i]的单个字符，用于判断和依次出栈的char字符是否相等
		if (reverse_str.top() != contract) {
			cout << "此字符串不是回文字符串!" << endl;
			return;
		}	//若遇到一个不相等的直接输出结果并返回
		else reverse_str.pop();
	}	//for遍历str的每个字符进行比较
 
	cout << "此字符串是回文字符串!" << endl;	//若遍历完都无不相等的则说明为回文，输出结果
}
 
int main()
{
	check();	//调用check()函数
}

  

---

之后也会每周更新C++数据结构和算法的相关内容，将逐渐由浅入深，感兴趣的朋友可以点个赞和关注。