数据结构第3单元课后练习答案.ppt

第三单元 栈与队列 链式堆栈的单链表应当设置表头结点（ ）。循环队列也存在空间溢出问题（ ）。栈和队列都是线性表，只是在插入和删除时受到了一些限制（ ）。 √ × × 设A、B、C、D、E五个元素依次进栈(进栈后可立即出栈)，问能否得到下列序列。若能得到，则给出相应的push和pop序列；若不能，则说明理由。1) A,B,C,D,E 2) A,C,E,B,D 3) C,A,B,D,E 4) E,D,C,B,A 答：2）和3）不能。对2）中的E，B，D而言，E最先出栈则表明，此时B和D均在栈中，由于，B先于D进栈，所以应有D先出栈。同理3）也不能。 (1)能。 push,pop,push,pop,push,pop,push,pop,push,pop (4)能。 push,push,push,push,push,pop,pop,pop,pop,pop 链式栈采用下列 结构最有利。 单链表 带表头结点的单链表 单循环链表 双向链表 设计共享栈。 定义一个足够大的栈空间。该空间的两端分别设为两个栈的栈底，用bottom1和bottom2指示，让两个栈的栈顶，用top1和top2指示，都向中间伸展，直到两个栈的栈顶相遇，才会发生溢出。 栈空，两栈均空：top1=-1且 top2=n 栈满：top1=top2-1 0 n-1 ↑ ↑ ↑ ↑ bottom1 top1 top2 bottom2 利用栈可以检查表达式中括号是否配对，试编写算法实现之。 //若不匹配，则返回true,否则返回false //解法一 bool match(char a[],int n) { SeqStackchar s(n); char c; for (int i=0;in;i++) if (a[i]==‘(’) s.Push(a[i]); //判栈满？ else if (a[i]==)) if (!s.Empty()) s.Pop(); //继续检查 else return true; //不匹配 if (!s.Empty()) return true; //不匹配 return false; //匹配 }? //解法二 不用栈，用一个字符数组 bool match(char a[],int n) { char c[n]; int top=-1; for (int i=0;in;i++) if (a[i]==‘(’) { top++; s[top]=a[i]; } else if (a[i]==)) if (top-1) { s[top]=0; top--; } //继续检查 else return true; //不匹配 if (top-1) return true; //不匹配 return false; //匹配 }? //解法三 不用栈，也不用数组，只用一个计数器top bool match(char a[],int n) { int top=-1; for (int i=0;in;i++) if (a[i]==() top++; else if (a[i]==)) if (top-1) top--; //继续检查 else return true; //不匹配 if (top-1) return true; //不匹配 return false; //匹配 } ? 声明并实现链式栈类LinkedStack。 template class T class LinkedStack: public StackT { public: LinkedStack(); ~LinkedStack(); virtual bool IsEmpty() const; virtual bool IsFull() const; virtual bool GetTop(T x); virtual bool Push(const T x); virtua