C++栈的基本操作和应用
<上一节
下一节>
栈和队列都是特殊的线性表,是限制存取位置的线性结构;可以由顺序表实现,也可以由链表实现。
允许进行插入和删除的一端叫做栈顶(top),而另一端叫栈底(bottom)。栈中没有任何元素时,称为空栈。设给定栈s=(a0,a1,……,an-1),称a0为栈底,an-1为栈顶。
栈又称作后进先出(LIFO:Last In First Out)的线性表。
栈可以用顺序表实现,称顺序栈(查看动画演示);也可以用链表实现,称链栈(查看动画演示)。
{
int top; //栈顶指针(下标)
T *elements; //动态建立的元素
int maxSize; //栈最大容纳的元素个数
public:
Stack(int=20);//栈缺省大小为20元素
~Stack()
{
delete[] elements;
}
void Push(const T &data); //压栈
T Pop(); //弹出,top--,出栈
T GetElem(int i); //取第i个数据,top不变
void PrintStack(); /*输出栈内所有数据*/
void MakeEmpty()//清空栈
{
top= -1;
}
bool IsEmpty() const//判断栈空
{
return top== -1;
}
bool IsFull() const
{
return top==maxSize-1;
}
};
顺序栈类模板中的成员函数的代码参见【例7.8】。
顺序栈必须先开一定大小内存空间,执行起来简单,速度快,可能溢出。链栈内存空间随用随开,不会溢出,但执行复杂(不断地动态分配),速度慢。
现考虑最简单的+、-、*、/四个运算符和结束符=组成的算术表达式,只有两个优先级,先*/,后+-。设有:a+b*c-d/e=。 为实现运算符的优先级,采用两个栈:一个数栈,一个运算符栈。数栈暂存操作数,运算符栈暂存运算符。从左向右扫描算术表达式,遇到操作数,压入数栈;遇到运算符,则与运算符栈栈顶的运算符比较优先级,若新的运算符优先级高,或运算符栈空,则压栈。否则将栈顶运算符出栈,与数字栈出栈的两个数据进行运算,结果压入数栈,再将新运算符压栈。继续扫描,直到遇到=号,扫描结束。栈中数据继续按前面规则出栈。(查看动画演示)
详细代码请参见【例7.9】。
什么是栈
栈定义为:只允许在表的一端进行插入和删除的线性表。允许进行插入和删除的一端叫做栈顶(top),而另一端叫栈底(bottom)。栈中没有任何元素时,称为空栈。设给定栈s=(a0,a1,……,an-1),称a0为栈底,an-1为栈顶。
栈又称作后进先出(LIFO:Last In First Out)的线性表。
栈可以用顺序表实现,称顺序栈(查看动画演示);也可以用链表实现,称链栈(查看动画演示)。
顺序栈的类模板定义
template<typename T>class Stack{
int top; //栈顶指针(下标)
T *elements; //动态建立的元素
int maxSize; //栈最大容纳的元素个数
public:
Stack(int=20);//栈缺省大小为20元素
~Stack()
{
delete[] elements;
}
void Push(const T &data); //压栈
T Pop(); //弹出,top--,出栈
T GetElem(int i); //取第i个数据,top不变
void PrintStack(); /*输出栈内所有数据*/
void MakeEmpty()//清空栈
{
top= -1;
}
bool IsEmpty() const//判断栈空
{
return top== -1;
}
bool IsFull() const
{
return top==maxSize-1;
}
};
顺序栈类模板中的成员函数的代码参见【例7.8】。
链栈的类模板定义
综合单链表和栈可知:首先定义链栈的节点类模板,然后在节点类基础上定义链栈类模板。详细代码参见【例7.9_h】。顺序栈与链栈的比较
顺序栈和链栈逻辑功能是一样,尽管这里两个栈模板的成员函数功能选择稍有出入,因为顺序栈可以随机访问其中的元素,而链栈只能顺序访问,但逻辑上完全可以做到一样(物理结构不同)。顺序栈必须先开一定大小内存空间,执行起来简单,速度快,可能溢出。链栈内存空间随用随开,不会溢出,但执行复杂(不断地动态分配),速度慢。
栈的应用
栈可用于表达式的计算。现考虑最简单的+、-、*、/四个运算符和结束符=组成的算术表达式,只有两个优先级,先*/,后+-。设有:a+b*c-d/e=。 为实现运算符的优先级,采用两个栈:一个数栈,一个运算符栈。数栈暂存操作数,运算符栈暂存运算符。从左向右扫描算术表达式,遇到操作数,压入数栈;遇到运算符,则与运算符栈栈顶的运算符比较优先级,若新的运算符优先级高,或运算符栈空,则压栈。否则将栈顶运算符出栈,与数字栈出栈的两个数据进行运算,结果压入数栈,再将新运算符压栈。继续扫描,直到遇到=号,扫描结束。栈中数据继续按前面规则出栈。(查看动画演示)
详细代码请参见【例7.9】。
<上一节
下一节>