《栈与队列相关题目》由会员分享，可在线阅读，更多相关《栈与队列相关题目（14页珍藏版）》请在金锄头文库上搜索。
1、18132)16/(16 12C第四章栈与队列第四章栈与队列4-2 改写顺序栈的进栈成员函数 Push (x )，要求当栈满时执行一个 stackFull ( )操作进行栈满处理。其功能是： 动态创建一个比原来的栈数组大二倍的新数组，代替原来的栈数组，原来栈数组中的元素占据新数组的前MaxSize 位置。【解答】templatevoid stack : push ( const Type /栈满，做溢出处理elements +top = item;/进栈template void stack : stackFull ( ) Type * temp = new Type 3 * maxSize
2、;/创建体积大二倍的数组for ( int i = 0; i F) /*注：按 C+的优先级*/(6) !(A Queue ( ) delete elements; void EnQueue ( Type Type DeQueue ( );Type GetFront ( );void MakeEmpty ( ) length = 0; /置空队列int IsEmpty ( ) const return length = 0; /判队列空否int IsFull ( ) const return length = maxSize; /判队列满否private:int rear, length;/队
3、尾指针和队列长度Type *elements;/存放队列元素的数组int maxSize;/队列最大可容纳元素个数构造函数template Queue: Queue ( int sz ) : rear (maxSize-1), length (0), maxSize (sz) /建立一个最大具有 maxSize 个元素的空队列。elements = new TypemaxSize;/创建队列空间assert ( elements != 0 );/断言: 动态存储分配成功与否插入函数template void Queue : EnQueue ( Type /判队列是否不满，满则出错处理lengt
4、h+;/长度加 1rear = ( rear +1) % maxSize;/队尾位置进 1elementsrear = item;/进队列删除函数template Type Queue : DeQueue ( ) assert ( ! IsEmpty ( ) ); /判断队列是否不空，空则出错处理21length-;/队列长度减 1return elements(rear-length+maxSize) % maxSize;/返回原队头元素值读取队头元素值函数template Type Queue : GetFront ( ) assert ( ! IsEmpty ( ) );return e
5、lements(rear-length+1+maxSize) % maxSize;/返回队头元素值4-10 假设以数组 Qm存放循环队列中的元素, 同时设置一个标志 tag，以 tag = 0 和 tag = 1 来区别在队头指 针(front)和队尾指针(rear)相等时，队列状态为“空”还是“满”。试编写与此结构相应的插入(enqueue)和删除(dlqueue)算法。【解答】循环队列类定义#include template class Queue /循环队列的类定义public: Queue ( int=10 );Queue ( ) delete Q; void EnQueue ( Ty
6、pe Type DeQueue ( );Type GetFront ( );void MakeEmpty ( ) front = rear = tag = 0; /置空队列int IsEmpty ( ) const return front = rear /判队列空否int IsFull ( ) const return front = rear /判队列满否private:int rear, front, tag;/队尾指针、队头指针和队满标志Type *Q;/存放队列元素的数组int m;/队列最大可容纳元素个数构造函数template Queue: Queue ( int sz ) :
7、rear (0), front (0), tag(0), m (sz) /建立一个最大具有 m 个元素的空队列。Q = new Typem;/创建队列空间assert ( Q != 0 );/断言: 动态存储分配成功与否插入函数template void Queue : EnQueue ( Type /判队列是否不满，满则出错处理rear = ( rear + 1 ) % m;/队尾位置进 1, 队尾指针指示实际队尾位置Qrear = item;/进队列22tag = 1;/标志改 1，表示队列不空删除函数template Type Queue : DeQueue ( ) assert ( !
8、 IsEmpty ( ) );/判断队列是否不空，空则出错处理front = ( front + 1 ) % m;/队头位置进 1, 队头指针指示实际队头的前一位置tag = 0;/标志改 0, 表示栈不满return Qfront;/返回原队头元素的值读取队头元素函数template Type Queue : GetFront ( ) assert ( ! IsEmpty ( ) );/判断队列是否不空，空则出错处理return Q(front + 1) % m;/返回队头元素的值4-11 若使用循环链表来表示队列，p 是链表中的一个指针。试基于此结构给出队列的插入(enqueue)和删除
9、(dequeue)算法，并给出 p 为何值时队列空。【解答】链式队列的类定义template class Queue;/链式队列类的前视定义template class QueueNode /链式队列结点类定义friend class Queue;private: Type data;/数据域QueueNode *link;/链域public:QueueNode ( Type d = 0, QueueNode *l = NULL ) : data (d), link (l) /构造函数;template class Queue /链式队列类定义public: Queue ( ) : p ( N
10、ULL ) /构造函数Queue ( );/析构函数void EnQueue ( const Type /将 item 加入到队列中Type DeQueue ( );/删除并返回队头元素Type GetFront ( );/查看队头元素的值void MakeEmpty ( );/置空队列，实现与Queue ( ) 相同int IsEmpty ( ) const return p = NULL; /判队列空否private: QueueNode *p;/队尾指针（在循环链表中）;23队列的析构函数template Queue:Queue ( ) /队列的析构函数QueueNode *s;whil
11、e ( p != NULL ) s = p; p = p-link; delete s; /逐个删除队列中的结点队列的插入函数template void Queue:EnQueue ( const Type p-link = p;else /队列不空, 新结点链入 p 之后QueueNode *s = new QueueNode ( item, NULL );s-link = p-link; p = p-link = s;/结点 p 指向新的队尾队列的删除函数template Type Queue:DeQueue ( ) if ( p = NULL ) cout *s = p;/队头结点为 p
12、 后一个结点p-link = s-link;/重新链接, 将结点 s 从链中摘下Type retvalue = s-data; delete s;/保存原队头结点中的值, 释放原队头结点return retvalue;/返回数据存放地址队空条件 p = NULL。4-12 若将一个双端队列顺序表示在一维数组 Vm中，两个端点设为 end1 和 end2，并组织成一个循环队列。试 写出双端队列所用指针 end1 和 end2 的初始化条件及队空与队满条件，并编写基于此结构的相应的插入(enqueue)新元素和删除(dlqueue)算法。【解答】初始化条件 end1 = end2 = 0;队空条件
13、 end1 = end2;队满条件 ( end1 + 1 ) % m = end2; /设 end1 端顺时针进栈，end2 端逆时针进栈循环队列类定义#include template class DoubleQueue /循环队列的类定义public: DoubleQueue ( int=10 );DoubleQueue ( ) delete V; void EnQueue ( Type Type DeQueue (const int end );Type GetFront (const int end );void MakeEmpty ( ) end1 = end2 = 0; /置空队列
14、int IsEmpty ( ) const return end1 = end2; /判两队列空否int IsFull ( ) const return (end1+1) % m = end2; /判两队列满否end1end224private:int end1, end2;/队列两端的指针Type *V;/存放队列元素的数组int m;/队列最大可容纳元素个数构造函数template DoubleQueue: DoubleQueue ( int sz ) : end1 (0), end2 (0), m (sz) /建立一个最大具有 m 个元素的空队列。V = new Typem;/创建队列空
15、间assert ( V != 0 );/断言: 动态存储分配成功与否插入函数template void DoubleQueue : EnQueue ( Type if ( end = 1 ) end1 = ( end1 + 1 ) % m;/end1 端指针先进 1, 再按指针进栈Vend1 = item;/end1 指向实际队头位置else Vend2 = item;/end2 端先进队列, 指针再进 1end2 = ( end2 - 1 + m ) % m;/end2 指向实际队头的下一位置删除函数template Type DoubleQueue : DeQueue ( const int end ) assert ( !IsEmpty ( ) );Typeif ( end = 1 ) temp = Vend1;/先保存原队头元素的值, end1 端指针退 1end1 = ( end1 + m - 1 ) % m;else end2 = ( end2 + 1 ) % m;temp = Vend2;/end2 端指针先退 1。再保存原队头元素的值return temp;读取队头元素的
