本文主要是介绍顺序栈及应用，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
参考的李春葆老师的数据结构教程#ifndef __STACK_H_
#define __STACK_H_#include <iostream>using namespace std;const int MaxSize = 100;template<class T>
class SeqStack
{
public:SeqStack();~SeqStack();bool StackEmpty();bool Pop(T &e);bool Push(T e);bool GetTop(T &e);
private:T *data;int top;
};
//
template<class T>
SeqStack<T>::SeqStack()
{data = new T[MaxSize];top = -1;
}
//
template<class T>
SeqStack<T>::~SeqStack(){}
//
template<class T>
bool SeqStack<T>::StackEmpty()
{if(top == -1)return true;elsereturn false;
}
//
template<class T>
bool SeqStack<T>::Push(T e)
{if(top == MaxSize-1)return false;else{++top;data[top] = e;return true;}
}
//
template<class T>
bool SeqStack<T>::Pop(T &e)
{if(StackEmpty())return false;else{e = data[top];top--;return true;}
}
//
template<class T>
bool SeqStack<T>::GetTop(T &e)
{if(StackEmpty())return false;else{e = data[top];return true;}
}
//
bool isSerial(int str[], int n) //判断序列str是否为一个合适的出栈序列
{int i, j ,e;int a[MaxSize];SeqStack<int> st; //建立一个顺序栈for(i = 0; i<n; ++i)a[i] = i+1;i = 0;j = 0;while(i<n&&j<n){if(st.StackEmpty()||(st.GetTop(e)&&e!=str[j])){st.Push(a[i]);cout<<"元素"<<a[i]<<"进栈"<<endl;++i;}else{st.Pop(e);cout<<"元素"<<e<<"出栈"<<endl;++j;}}while(!st.StackEmpty()&&st.GetTop(e)&&e==str[j]){st.Pop(e);cout<<"元素 "<<e<<"出栈"<<endl;++j;}if(j == n)return true;elsereturn false;
}
void Disp(int str[],int n) //输出str
{int i;for(i = 0;i<n; ++i)cout<<str[i];
}
//
bool isPalindrome(char str[],int n) //判断一个字符串是否是回文串
{int i;char e;SeqStack<char> st;while(i<n) //将字符串入栈{st.Push(str[i]);++i;}i = 0;while(i<n){st.Pop(e); //得到栈顶元素，并出栈if(e =! str[i]) //判断首尾是否一样return false;++i;}return true;
}
//检查输入的表达式中的括号是否匹配
bool isMatch(char str[],int n)
{int i = 0;char e;SeqStack<char> st;while(i<n){if(str[i] == '('||str[i] == '{'||str[i] == '[')//如果是左括号则入栈st.Push(str[i]);else{if(str[i] == ')'){if(!st.Pop(e)) //得到栈顶元素并出栈return false;if(e != '(')return false; //如果左右不一样，则返回错误}if(str[i] == ']'){if(!st.Pop(e))return false;if(e != '[')return false;}if(str[i] == '}'){if(!st.Pop(e))return false;if(e != '{')return false;}}++i;}if(!st.StackEmpty()) //最后栈不为空则也不是正确的匹配return false;elsereturn true;
}
#endif // __STACK_H_#include "Stack.h"int main()
{//测试是否是合理的出栈顺序int n = 4;int str[] = {3,4,2,1};cout<<"由1~"<<n<<"产生";Disp(str,n);cout<<"的操作序列"<<endl;if(isSerial(str,n)){Disp(str,n);cout<<"是合适的出栈序列"<<endl;}else{Disp(str,n);cout<<"不是合适的出栈序列"<<endl;}//判断是否是回文串char str1[]= "abcba";if(isPalindrome(str1,5))cout<<"是回文串"<<endl;elsecout<<"不是回文串"<<endl;//判断括号是否匹配char str3[]="{【)}";if(isMatch(str3,4))cout<<str3<<"中的括号匹配"<<endl;elsecout<<str3<<"中的括号不匹配"<<endl;return 0;
}
//
这篇关于顺序栈及应用的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
