采用顺序栈的回文判断

栈是一种后进先出（LIFO）的线性表，限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。 下面给出顺序栈的操作实现

顺序栈

//SqStack.h #pragma once //LIFO表 template <class ElemType> class SqStack { public: SqStack(int m);//构造函数 ~SqStack();//析构函数 void Clear();//清空栈 bool Empty() const;//判栈空 int Length() const;//求长度 ElemType& Top() const;//取栈顶元素 void Push(const ElemType& e);//入栈 void Pop();//出栈 private: ElemType* m_base;//基地址指针 int m_top;//栈顶指针 int m_size;//向量空间大小 }; //构造函数，分配m个节点的顺序空间，构造一个空的顺序栈 template<class ElemType> SqStack<ElemType>::SqStack(int m) { m_top = 0; m_base = new ElemType[m]; m_size = m; } //析构函数，将栈结构销毁 template<class ElemType> SqStack<ElemType>::~SqStack() { if (m_base != NULL) delete[] m_base; } template<class ElemType> void SqStack<ElemType>::Clear() { m_top = 0; } template<class ElemType> bool SqStack<ElemType>::Empty() const { return m_top == 0; } template<class ElemType> int SqStack<ElemType>::Length() const { return m_top; } template<class ElemType> ElemType& SqStack<ElemType>::Top() const { return m_base[m_top - 1]; } template<class ElemType> void SqStack<ElemType>::Push(const ElemType& e) { if (m_top >= m_size) { ElemType* newbase; newbase = new ElemType[m_size + 10]; for (int i = 0; i < m_top; i++) newbase[i] = m_base[i]; delete[] m_base; m_base = newbase; m_size += 10; } m_base[m_top++] = e; } template<class ElemType> void SqStack<ElemType>::Pop() { m_top--; }

显然，上述顺序栈的操作中，时间复杂度均为o(1)。

顺序栈的应用：回文判断

算法描述不再赘述。

// Palindrome.cpp #include <iostream> #include "SqStack.h" using namespace std; #define MAX_STRING_LEN 100 //判断是否回文 bool ispalindrome(char* in_string) { SqStack<char> s(MAX_STRING_LEN); char deblankstring[MAX_STRING_LEN], c; int i = 0; //过滤字符空格 while (*in_string != '\0') { if (*in_string != ' ') deblankstring[i++] = *in_string; in_string++; } deblankstring[i] = '\0'; //有效字符依次入栈 i = 0; while (deblankstring!='\0') { s.Push(deblankstring[i++]); } //从栈中弹出字符依次比较 i = 0; while (!s.Empty()) { c = s.Top(); s.Pop(); if (c != deblankstring[i]) return false; i++; } return true; } int main() { char instring[MAX_STRING_LEN]; cout << "请输入一个字符串：" << endl; cin.get(instring, MAX_STRING_LEN); if (ispalindrome(instring)) cout << "\"" << instring << "\"" << "是回文。" << endl; else cout << "\"" << instring << "\"" << "不是回文。" << endl; system("pause"); return 0; }