一、栈
1、什么是栈
栈(Stack)是一种线性存储结构，它具有如下特点：
（1）栈中的数据元素遵守”先进后出”(First In Last Out)的原则，简称FILO结构。
（2）限定只能在栈顶进行插入和删除操作。
2、栈的基本操作
栈主要有以下几种基本操作：
（1）push(): 向栈内压入一个成员；
（2）pop(): 从栈顶弹出一个成员；
（3）empty(): 如果栈为空返回true，否则返回false；
（4）top(): 返回栈顶，但不删除成员；
（4）size(): 返回栈内元素的大小；
3、简单的动态栈的实现
具体代码实现：
//1、动态顺序栈的实现
#include<iostream>
using namespace std;
#if 1
template<class T>
class Stack
{
public:
Stack()//构造函数
:_capacity(0)
, _size(0)
,_array(NULL)
{}
void Push(const T& data)
{
CheckCapacity();//检查是否需要增容
_array[_size] = data;
_size++;
}
void Pop()
{
if (Empty())
return;
else
{
_size--;
//Top()--;
}
}
T& Top()
{
return _array[Size() - 1];
}
T& Top()const
{
return _array[Size() - 1];
}
size_t Size()const
{
return _size;
}
bool Empty()const
{
return Size() == 0;
}
void Display()
{
if (_array == NULL)
return;
for (size_t i = 0; i < Size(); ++i)
{
cout << _array[i]<<" ";
}
cout << endl;
}
private:
void CheckCapacity()
{
int sz = Size();
int NewSize = _capacity * 2 + 3;
if (_capacity <= sz)
{
T *pStr = new T[NewSize];
if (pStr == NULL)
{
cout << "增容失败" << endl;
return;
}
else
{
for (int i = 0; i < Size(); ++i)
{
pStr[i] = _array[i];
}
if (_array != NULL)
delete[]_array;
_array = pStr;
_capacity = NewSize;
cout << "增容成功！" << endl;
}
}
}
T* _array;
size_t _capacity;//容量
size_t _size;//存放元素的个数
};
//测试函数
int main()
{
Stack<int>s;
s.Push(1);
s.Push(2);
s.Push(3);
s.Push(4);
s.Push(5);
s.Display();
s.Pop();
s.Pop();
s.Display();
cout << s.Top() << ""<<endl;
cout << s.Size() << "" << endl;
/*s.Size();
s.Display();*/
system("pause");
return 0;
}
运行结果检验：
二、栈的应用
栈是一个重要的数据结构，其特性简而言之就是“后进先出”，这种特性在计算机中有着广泛的运用。其实程序员无时无刻不在使用者栈，函数的调用是我们间接使用栈的最好的例子，但是栈在实际中的运用远不止这些，比较经典的应用还包括括号匹配、逆波兰表达式的求值等，下面就介绍这两个对栈的简单应用：
1、括号匹配问题
1）括号匹配问题的四种结果：
（1）左右括号匹配正确
（2）左右括号匹配错误
（3）左括号多于右括号
（4）右括号多于左括号
2）算法基本思想
（1）顺序扫描算数表达式（表现为一个字符串），当遇到三种类型的左括号时候让该括号进栈；
（2）当扫描到某一种类型的右括号时，比较当前栈顶元素是否与之匹配，若匹配，退栈继续判断；若当前栈顶元素与当前扫描的括号不匹配，则左右括号配对次序不正确；
（3）若字符串当前为某种类型的右括号而堆栈已经空，则右括号多于左括号；
（4）字符串循环扫描结束时，若堆栈非空（即堆栈尚有某种类型的左括号），则说明左括号多于右括号；
（5）否则，括号配对正确。
3）代码实现：
#include<string>
#include<stack>
#include<iostream>
using namespace std;
bool MatchBrackets(char* pStr)
{
stack <char> s;//用来存放括号的栈
int Len = strlen(pStr);
for (int i = 0; i < Len; ++i)
{
if (pStr[i] == '{' || pStr[i] == '(' || pStr[i] == '[')
{
s.push(pStr[i]);
}
else if (pStr[i] == '}' || pStr[i] == ')' || pStr[i] == ']')
{
if (s.empty())
{
cout << "右括号多于左括号" << endl;
return false;
}
else
{
if ((pStr[i] == ')'&&s.top() == '(') || (pStr[i] == '}'&&s.top() == '{')
|| (pStr[i] == ']'&&s.top() == '['))
{
s.pop();
}
else
{
cout << "左右括号匹配错误" << endl;
return false;
}
}
}
}
if (s.empty())
{
cout << "匹配成功！" << endl;
}
else
{
cout << "左括号多于右括号" << endl;
return false;
}
}
int main()
{
char ptr1[] = "{[]}}";
char ptr2[] = "{[(]}";
MatchBrackets(ptr1);
MatchBrackets(ptr2);
system("pause");
return 0;
}
运行结果检验：
2、实现逆波兰表达式
算法基本思路：
a、操作符栈初始化，将结束符#进栈，然后读取中缀表达式中的首字符ch
b、重复执行以下步骤，直到ch = ‘#’，同时栈顶的操作符也是‘#’时，循环终止
若ch是操作数则直接输出，读取下一个字符
若ch是操作符，判断ch的优先级icp和当前位于栈顶的操作符op的优先级isp
若icp(ch) > isp(op)，令ch进栈，读入下一个字符ch
若icp(ch) < isp(op)，退栈并输出
若icp(ch) == isp(op)，退栈但不输出，若退出的是‘（’继续读入下一个字符ch
c、算法结束，输出的序列即为后缀表达式
将中缀表达式转换为后缀表达式函数实现：
void ChangeRPN(const char*pStr)
{
stackopra;//操作符栈
vectornum;//用于存放转换之后的后缀表达式
opra.push(‘#’);
char ch;
int sz = strlen(pStr);
for (int i = 0; i < sz; i++)
{
if (IsOperator(pStr[i]))//是否是操作符
{
ch = pStr[i];
if (icp(ch)>isp(opra.top()))//栈外优先级大于栈内，ch入操作符栈
{
opra.push(ch);
}
else if (icp(ch) < isp(opra.top()))//栈外优先级小于栈内优先级，先将操作符栈栈顶
{ //输入到后缀表达式num中并出操作符栈,
num.push_back(opra.top());
opra.pop();
i--; //此时栈外操作符还需进行下一次比较，所以要给它-1；否则就跳过该操作符了
}
else
{
if (opra.top() == '(')
{
opra.pop();
}
}
}
else
num.push_back(pStr[i]);//数字入栈
}
while (!opra.empty() && opra.top() != '#')//当字符串数组遍历结束后，依次将操作符栈的元素出
{ //栈并输入到后缀表达式数组中
num.push_back(opra.top());
opra.pop();
}
for (size_t i = 0; i < num.size(); ++i)//后缀表达式打印
{
cout << num[i];
}
cout << endl;
//CalRPN(num);
}
完整的函数实现：中缀表达式–>后缀表达式–>后缀表达式求值
#include<iostream>
using namespace std;
#include<string.h>
#include<stack>
#include<vector>
//12 * (3 + 4) - 6 + 8 / 2 == > 12 3 4 + *6 - 8 2 / += == >
bool IsOperator(const char str)//判断字符是否是操作符
{
if (str == '+' || str == '-' || str == '*' || str == '/' || str == '%'||str=='('||str==')')
return true;
return false;
}
int isp(char str)//栈内优先数
{
switch (str)
{
case '#':return 0;
case'(':
return 1;
break;
case'*':
case'/':
case'%':
return 5;
break;
case'+':
case'-':
return 3;
break;
case ')':
return 6;
break;
default:
cout << "操作数错误" << endl;
exit(0);
break;
}
return 0;
}
int icp(char str)//栈外优先数
{
switch (str)
{
case'#':
return 0;
break;
case'(':
return 6;
break;
case'*':
case'/':
case'%':
return 4;
break;
case'+':
case'-':
return 2;
break;
case')':
return 1;
break;
default:
cout << "操作数错误" << endl;
exit(0);
break;
}
return 0;
}
int CalcRPN(const char* pstr)
{
stack<int>num;//存放数字的栈
int sz = strlen(pstr);
for (int i = 0; i < sz; ++i)
{
//不是操作符，则入栈num
if (!IsOperator(pstr[i]))
num.push(pstr[i]);
else
{//否则分别取出左操作数和右操作数进行相关计算，并把计算的结果入栈
char right = num.top();
num.pop();
char left = num.top();
num.pop();
if (pstr[i] == '+')
num.push(left + right);
if (pstr[i] == '-')
num.push(left - right);
if (pstr[i] == '*')
num.push(left * right);
if (pstr[i] == '/')
{
if (right == '0')
{
cout << "除数为0" << endl;
exit(EXIT_FAILURE);
}
num.push(left / right);
}
if (pstr[i] == '%')
{
num.push(left % right);
}
else
{
cout << "表达式非法！" << endl;
}
}
}
return num.top();//当前栈顶元素即为表达式的计算结果
}
int CalRPN(vector<char>pstr)
{
int count = pstr.size();
int index = 0;
stack<int> Sum;
while (index<count)
{
if (isdigit(pstr[index])) //如果碰到一个数字字符 1 2 0 ' '
{
int num = pstr[index] - 48; //1 2 ' '
index++; //num = 1
while (isdigit(pstr[index]))
{
num = num * 10 + (pstr[index] - 48); //num=12
index++;
}
Sum.push(num);
}
else if (IsOperator(pstr[index])) //如果是操作符
{
int right = Sum.top();
Sum.pop();
int left = Sum.top();
Sum.pop();
if (pstr[index] == '+')
Sum.push(left + right);
if (pstr[index] == '-')
Sum.push(left - right);
if (pstr[index] == '*')
Sum.push(left * right);
if (pstr[index] == '/')
{
if (right == '0')
{
cout << "除数为0" << endl;
exit(EXIT_FAILURE);
}
Sum.push(left / right);
}
if (pstr[index] == '%')
{
Sum.push(left % right);
}
else
{
cout << "表达式非法！" << endl;
}
index++;
}
else
index++;
}
cout << Sum.top() << endl;
return Sum.top();
}
void ChangeRPN(const char*pStr)
{
stack<char>opra;//操作符栈
vector<char>num;//用于存放转换之后的后缀表达式
opra.push('#');
char ch;
int sz = strlen(pStr);
for (int i = 0; i < sz; i++)
{
if (IsOperator(pStr[i]))//是否是操作符
{
ch = pStr[i];
if (icp(ch)>isp(opra.top()))//栈外优先级大于栈内，ch入操作符栈
{
opra.push(ch);
}
else if (icp(ch) < isp(opra.top()))//栈外优先级小于栈内优先级，先将操作符栈栈顶
{ //输入到后缀表达式num中并出操作符栈,
num.push_back(opra.top());
opra.pop();
i--; //此时栈外操作符还需进行下一次比较，所以要给它-1；否则就跳过该操作符了
}
else
{
if (opra.top() == '(')
{
opra.pop();
}
}
}
else
num.push_back(pStr[i]);//数字入栈
}
while (!opra.empty() && opra.top() != '#')//当字符串数组遍历结束后，依次将操作符栈的元素出
{ //栈并输入到后缀表达式数组中
num.push_back(opra.top());
opra.pop();
}
for (size_t i = 0; i < num.size(); ++i)//后缀表达式打印
{
cout << num[i];
}
cout << endl;
CalRPN(num);
}
void PutSpace(char*str)//打空格
{
char pstr[100];
int index = 0;
int len = strlen(str);
while (*str)
{
if (isdigit(*str)) //数字符
{
pstr[index] = *str;
index++;
str++;
while (isdigit(*str))
{
pstr[index] = *str;
index++;
str++;
}
pstr[index]=' ';
index++;
}
else if (IsOperator(*str))//运算符
{
pstr[index] = *str;
index++;
str++;
}
else //非法字符
{
str++;
}
}
pstr[index] = 0;
ChangeRPN(pstr);
}
int main()
{
char str[] = "12*(3+4)-6+8/2";
PutSpace(str);
//char *pstr = "12*( 3 +4 ) - 6 + 8/ 2 ";//1234+*6-82/+
system("pause");
return 0;
}
运行结果测试：
版权声明：本文为qq_37964547原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。