![](https://csdnimg.cn/release/download_crawler_static/86331483/bg3.jpg)
3
8
↑
操作符
isp ( ' / ' ) < icp ( '↑' ), 进栈, 读下一符号 # -/↑
a x * b x
9 2
操作数 直接输出, 读下一符号
# -/↑
a x * b x 2
10 #
操作符
isp ( '↑' ) > icp ( ' # ' ), 退栈输出
# -/
a x * b x 2↑
isp ( '
/ ' ) > icp ( ' # ' ), 退栈输出 # -
a x * b x 2
↑/
isp ( ' - ' ) > icp ( ' # ' ), 退栈输出
#
a x * b x 2↑/ -
结束
4-9 假设以数组 Q[m]存放循环队列中的元素, 同时以 rear 和 length 分别指示环形队列中的队尾位置和队列
中所含元素的个数。试给出该循环队列的队空条件和队满条件, 并写出相应的插入(enqueue)和删除(dlqueue)
元素的操作。
【解答】
循环队列类定义
#include <assert.h>
template <class Type> class Queue { //循环队列的类定义
public:
Queue ( int=10 );
~Queue ( ) { delete [ ] elements; }
void EnQueue ( Type & item );
Type DeQueue ( );
Type GetFront ( );
void MakeEmpty ( ) { length = 0; } //置空队列
int IsEmpty ( ) const { return length == 0; } //判队列空否
int IsFull ( ) const { return length == maxSize; } //判队列满否
private:
int rear, length; //队尾指针和队列长度
Type *elements; //存放队列元素的数组
int maxSize; //队列最大可容纳元素个数
}
构造函数
template <class Type>
Queue<Type>:: Queue ( int sz ) : rear (maxSize-1), length (0), maxSize (sz) {
//建立一个最大具有 maxSize 个元素的空队列。
elements = new Type[maxSize]; //创建队列空间
assert ( elements != 0 ); //断言: 动态存储分配成功与否
}
插入函数
template<class Type>
void Queue<Type> :: EnQueue ( Type &item ) {
assert ( ! IsFull ( ) ); //判队列是否不满,满则出错处理
length++; //长度加 1
rear = ( rear +1) % maxSize; //队尾位置进 1
elements[rear] = item; //进队列
}
删除函数