使用链栈和链队列的基本操作，判断一个字符串是否为回文（C++）

（1）实现节点类模板，放在node.h文件中；
（2）实现链栈类模板，放在lk_stack.h文件中；
（3）实现链队列类模板，放在lk_queue.h文件中；
（4）实现字符串是否为回文的判断，放在alg.h文件中。

node.h

#pragma once
template
struct Node
{
	//数据成员
	ElemType data;//数据成分
	Node* next;//指针成分

	//构造函数模板
	Node();//无参数构造函数模板
	Node(const ElemType& e, Node* link=NULL);//已知数据元素值和指针建立节点
};

//节点类模板的实现部分
template
Node::Node()
//构造指针成分为空的节点
{
	next = NULL;
}

template
Node::Node(const ElemType& e, Node* link)
//构造一个数据成分为e和指针成分为link的节点
{
	data = e;
	next = link;
}

lk_stack.h

#pragma once
#include"node.h"
template
class linkStack   //链栈
{
protected:
	//数据成员
	Node* top;
	int count;

public:
	linkStack();
	virtual ~linkStack();
	int Length()const;
	bool Push(const ElemType& e);
	bool Pop(ElemType& e);
	bool Pop();
	void Clear();
	bool Empty()const;

};

template
linkStack::linkStack()
{
	top = NULL;
	count = 0;
}

template
void linkStack::Clear()
{
	while (!Empty())
	{
		Pop();
	}
}
template
linkStack::~linkStack()
{
	Clear();
}

template
int linkStack::Length()const
{
	return count;
}

template
bool linkStack::Push(const ElemType& e)
{
	Node* newTop = new Node(e, top);
	if (newTop == NULL)
	{
		return false;
	}
	else
	{
		top = newTop;
		count++;
		return true;
	}
}

template
bool linkStack::Pop(ElemType& e)
{
	if (Empty())
	{
		return false;
	}
	else
	{
		Node* oldTop = top;
		e = oldTop->data;
		top = oldTop->next;
		delete oldTop;
		count--;
		return true;
	}
}

template
bool linkStack::Pop()
{
	if (Empty())
	{
		return false;
	}
	else
	{
		Node* oldTop = top;
		top = oldTop->next;
		delete oldTop;
		count--;
		return true;
	}
}

template
bool linkStack::Empty()const
{
	return count == 0;
}

lk_queue.h

#pragma once
#include"node.h"

template
class linkQueue   //链队列
{
protected:
	//数据成员
	Node* front,*rear;//队头队尾指针
	int count;

public:
	linkQueue();
	virtual ~linkQueue();
	int Length()const;
	bool InQueue(const ElemType& e);
	bool OutQueue(ElemType& e);
	bool OutQueue();
	void Clear();
	bool Empty()const;
};


template
linkQueue::linkQueue()
{
	rear = front = new Node;
	count = 0;
}

template
void linkQueue::Clear()
{
	while (!Empty())
	{
		OutQueue();
	}
}

template
bool linkQueue::Empty()const
{
	return count == 0;
}

template
linkQueue::~linkQueue()
{
	Clear();
	delete front;
}

template
int linkQueue::Length()const
{
	return count;
}

template
bool linkQueue::InQueue(const ElemType& e)
{
	Node*temPtr = new Node(e);
	if (temPtr == NULL)
	{
		return false;
	}
	else
	{
		rear->next = temPtr;
		rear = temPtr;
		count++;
		return true;
	}

}

template
bool linkQueue::OutQueue(ElemType& e)
{
	if (!Empty())
	{
		Node* temPtr = front->next;
		e = temPtr->data;
		front->next = temPtr->next;
		if (rear == temPtr)
		{
			rear = front;
		}
		delete temPtr;
		count--;
		return true;
	}
	else
	{
		return false;
	}
}

template
bool linkQueue::OutQueue()
{
	if (!Empty())
	{
		Node* temPtr = front->next;
		front->next = temPtr->next;
		if (rear == temPtr)
		{
			rear = front;
		}
		delete temPtr;
		count--;
		return true;
	}
	else
	{
		return false;
	}
}

alg.h

#pragma once
#include"lk_queue.h"
#include"lk_stack.h"

bool Palindrome(char* s)
{
	linkQueue LQ;
	linkStack LS;
	int ls = 0;
    bool T=false;
	char c1, c2;


	for (int i=0;s[i]!=''; i++)
	{
		LQ.InQueue(s[i]);
		LS.Push(s[i]);
			ls++;
	}

	for (int i = 1; i <= ls; i++)
	{
		LQ.OutQueue(c1);
		LS.Pop(c2);
		if (c1 != c2)
		{
			return false;
		}
	}
	return true;
}

main.cpp

#include 					// 标准流操作
#include 					// 包含C函数strlen()、strcpy()、strncpy()、strcat()和strcmp()的声明（string.h与cstring是C的头文件）
using namespace std;				// 标准库包含在命名空间std中
#include "lk_stack.h"				// 链栈
#include "lk_queue.h"				// 链队列
#include "alg.h"					// 算法
int main()							// 主函数main()
{
	char s1[] = "abcba";				// 定义串s1
	if (Palindrome(s1))
	{	// 回文
		cout << """ << s1 << """ << "是回文." << endl;
	}
	else
	{	// 非回文
		cout << """ << s1 << """ << "不是回文." << endl;
	}
	char s2[] = "abcbac";			// 定义串s2
	if (Palindrome(s2))
	{	// 回文
		cout << """ << s2 << """ << "是回文." << endl;
	}
	else
	{	// 非回文
		cout << """ << s2 << """ << "不是回文." << endl;
	}
	return 0;						// 返回值0, 返回操作系统
}