第3章栈与队列习题参考答案

1、习题三参考答案 备注：红色字体标明的是与书本内容有改动的内容 一、选择题 1. 在栈中存取数据的原则是（ B ）。 A.先进先出B.先进后出 C.后进后出D.没有限制 2. 若将整数1、2、3、4依次进栈，则不可能得到的出栈序列是（D ）。 A. 1234 B.1324 C.4321 D.1423 3. 在链栈中，进行出栈操作时（ B ）。 A .需要判断栈是否满B.需要判断栈是否为空 C.需要判断栈元素的类型D.无需对栈作任何差别 4. 在顺序栈中，若栈顶指针top指向栈顶元素的下一个存储单元，且顺序栈的最大容量是 maxSize，则顺序栈的判空条件是（ A ）。 A . top=0 B.t

2、op=-1 C. top=maxSize D.top=maxSize-1 5. 在顺序栈中，若栈顶指针top指向栈顶元素的下一个存储单元，且顺序栈的最大容量是 maxSize。则顺序栈的判满的条件是（C ）。 6.在队列中存取数据兀素的原则是（ A ）。 A.先进先出 B. 先进后出 C.后进后出 D. 没有限制 7.在循环顺序队列中， 假设以少用一个存储单元的方法来区分队列判满和判空的条件, A . top=0 B.top=-1 C. top=maxSize D.top=maxSize-1 front front front 表尾讲 和rear分别为队首和队尾指针，它们分别指向队首元素和队尾

3、元素的下一个存储单元， 队列的最大存储容量为maxSize，则队列的判空条件是（A ）。 A. front=rearB. front!=rear C. fron t=rear+1D. fron t=（rear+1）% maxSize 栈顶元素的访问形式是stackElemtop-1 ; 4. 在不带表头结点的链栈中，若栈顶指针top直接指向栈顶元素，则将一个新结点p入栈 时修改链的两个对应语句为p.setNext(top) ； top=p; 。 5. 在不带表头结点的链栈中，若栈顶指针top直接指向栈顶元素，则栈顶元素出栈时的修 改链的对应语句为 top=top.getNext();。 6.

4、队列也是一种操作受限的线性表，它与栈不同的是，队列中所有的插入操作均限制在表 的一端进行，而所有的删除操作都限制在表的另一端进行，允许插入的一端称为队尾， 允许删除的一端称为队首。队列具有先进先出的特点。 7. 由于队列的删除和插入操作分别在队首和队尾进行，因此，在链式存储结构描述中分别 需要设置两个指针分别指向队首结点和队尾结点，这两个指针又分别称为 队首指针和队尾指针。 8. 循环顺序队列是将顺序队列的存储区域看成是一个首尾相连的环，首尾相连的状态是通 过数学上的 求模(或取余)运算来实现的。 9. 在循环顺序队列中，若规定当front=rear时，循环队列为空；当 fron t=(rea

5、r+1)%maxSize 时，循环队列为满，则入队操作时的队尾指针变化的相应语 句 是 rear=(rear+1)% maxSize ；出队操作时的 队首指针变化 的相应 语句是 fron t=(fro nt+1)%maxSize。 10. 无论是顺序栈还是顺序队列，插入元素时必须先进行栈或队列是否为满的 判断，删除 元素时必须先进行 栈或队列是否为空的 判断；而链栈或链队列中，插入元素无需进行 栈或队列是否为满的判断，只要在删除元素时先进行栈或队列是否为空的判断。 三、算法设计题 1. 编写一个函数，要求借助一个栈把一个数组中的数据元素逆置。 参考答案： /借助一个顺序栈将已知一个数组中的数

6、据元素逆置 public reverse(Object a) throws Excepti on SqStack S=new SqStack(a.le ngth); /构造一个容量为a.le ngth的顺序栈 for(i nt i=0;ia .len gth;i+) S.push (a i); for( in t i=0;ia.le ngth;i+) ai=S.pop(); 2. 编写一个函数判断一个字符序列是否为回文序列，所谓回文序列就是正读与反读都相同 的字符序列，例如：abba和abdba均是回文序列。要求只使用栈来实现。 参考答案： /判断字符序列是否为回文序列，若是则返回true值，

7、否则返回false。 public boolea n isPali ndSeq(Stri ng str) Lin kStack S = new Lin kStack(); int i = 0; for (; i str.length(); i+) S.push(str.charAt(i); for (i = 0; i top1) /栈满 throw new Exception( 栈已满 );II 抛出异常 else if (i=0) stackElemtop0+=X; else if (i=1) stackElemtop1-=X; / 出栈操作方法 public Object pop(int

8、i) throws Exception /将S中第i号栈的栈顶元素出栈，并返回栈顶元素值 Object x=null; if(i=0) if (top0=base0) throw new Exception(第 0 号栈为空 ); else x=stackElem-top0; else if (i=1) if (top1=base1) throw new Exception(第 0 号栈为空 ); else x=stackElem+top1; return x; / DuSqStack类结束 4. 循环顺序队列类采用设置一个计数器的方法来区分循环队列的判空和判满。试分别编写 顺序循环队列中入队

9、和出队操作的函数。 参考答案 : / 循环顺序队列存储结构类描述如下 : class CircleSqQueue_num private Object queueElem; /队列存储空间 private int front; / 队首的引用，若队列不空，指向队首元素，初值为 0 private int rear; / 队尾的引用，若队列不空，指向队尾元素的下一个位置 ， 初值为 0 private int num; / 计数器用来记录队列中的数据元素个数 / CircleSqQueue_num 类结束 为类 CircleSqQueue_num 所编写的入队和出队操作方法如下： / 入队操作方

10、法 public void offer(Object x) throws Exception / 把指定的元素 x 插入队列 if (num=queueElem.length)/ 队列满 throw new Exception( 队列已满 );/ 输出异常 else / 队列未满 queueElemrear = x;/ x 加入队尾 rear=(rear + 1) % queueElem.length; / 更改队尾的位置 +num; / 计数器加 1 / 出队操作方法 public Object poll() / 移除队首元素并作为此函数的值返回该对象，如果此队列为空，则返回 null if

11、 (num=0)/ 队列为空 return null; else Object t = queueElemfront;/取出队首元素 front = (front + 1) % queueElem.length;/ 更改队首的位置 -num; / 计数器减 1 return t;/ 返回队首元素 5. 假设采用带头结点的循环链表来表示队列，并且只设一个指向队尾元素的指针(不设队 首指针)，试编写相应的队列置空、队列判空、入队和出队操作的函数。 参考答案 : 用队尾指针标识的循环链队列的类描述如下 : class CircleLinkQueue private Node rear;/循环链队列的

12、尾指针 为此类编写的队列置空、队列判空、入队和出队操作的方法分别如下： / 队列置空操作方法 public void clear() / 将一个已经存在的带头结点的循环链队列置成空队列 rear.setNext(rear); / 入队操作方法 public void offer ( Object x) throws Exception / 将指定的元素 x 插入到带头结点的循环链队列中 Node p= new Node(x); /生成新结点 p.setNext(rear.getNext();/ 插入链列列的尾部 rear.setNext(p); rear=p; / 出队操作方法 public

13、void poll() throws Exception / 移除带头结点的循环链队列中的队首元素并作为此函数的值返回该对象，如果此队列为空，则返回 null Node p = rear.getNext().getNext();/ p指向待删除的队首结点 if (p=rear) else rear.setNext(rear); / 删除队首结点后，链队列变成了空链队列 rear.getNext().setNext(p.getNext();/ 删除队首结点 四、上机实践题 1. 在顺序栈类中增加一个 main 成员函数， 使其实际运行来测试顺序栈类中各成员函数的正 确性。 参考答案 : pack

14、age ch03Exercise; / 顺序栈类 public class SqStack 栈存储空间 private Object stackElem; / private int top; / 非空栈中始终表示栈顶元素的下一个位置，当栈为空时其值为 0 / 栈的构造函数，构造一个存储空间容量为 maxSize 的栈 public SqStack(int maxSize) stackElem = new ObjectmaxSize;/ 为栈分配 maxSize 个存储单元 top = 0; /初始化 top 为 0 / 将一个已经存在的栈置成空 public void clear() top

15、 = 0; / 测试栈是否为空 public boolean isEmpty() return top = 0; / 求栈中的数据元素个数并由函数返回其值 public int length() return top; / 查看栈顶对象而不移除它，返回栈顶对象 public Object peek() if (!isEmpty()/ 栈非空 return stackElemtop - 1; /栈顶元素 else / 栈为空 return null; / 移除栈顶对象并作为此函数的值返回该对象 public Object pop() if (top = 0)/ 栈为空 return null;

16、else / 栈非空 return stackElem-top;/修改栈顶指针，并返回栈顶元素 / 把 o 压入栈顶 public void push(Object o) throws Exception if (top = stackElem.length)/栈满 throw new Exception( 栈已满 );/ 输出异常 else / 栈未满 stackElemtop+ = o;/ o赋给栈顶元素后， top 增 1 ( 栈顶到栈底 ) / 打印函数，打印所有栈中的元素 public void display() 打印 for (int i = top - 1; i = 0; i-

17、) System.out.print(stackElemi.toString() + );/ / 测试类 public class Exercise3_4_1 public static void main(String args) throws Exception SqStack S = new SqStack(100); / 初始化一个新的栈 for (int i = 1; i = 10; i+)/ 初始化栈中的元素，其中元素个数为 10 S.push(i); System.out.println( 栈中各元素为 (栈顶到栈底 ) ： ); S.display();/ 打印栈中元素(栈低到

18、栈顶) System.out.println(); if (!S.isEmpty()/ 栈非空，输出 System.out.println( 栈非空！ ); System.out.println( 栈的长度为： + S.length();/ 输出栈的长度 System.out.println( 栈顶元素为： + S.peek().toString();/ 输出栈顶元素 System.out.println( 去除栈顶元素后，栈中各元素为 ( 栈顶到栈底 ) ： S.pop();/ 删除元素 S.display();/ 打印栈中元素 System.out.println(); System.ou

19、t.println(”去除栈中剩余的所有元素！进行中。);/ 输出 S.clear(); /将栈清空 if (S.isEmpty()栈空，输出 System.out.println(”栈已清空!); 运行结果： CA g中各元素为 栈顶到栈底: .098765 戋程总度为， 黒顶元素为: 10 10 C: IMDOfSsyst eaJZXod- exe 去除栈顶元素后.栈中各元素为t桟顶到栈底儿 987654321 盍除我史剩余的所有元素！进行中 栈己清工* 2. 在链队列类中增加一个main成员函数，使其实际运行来测试链队列类中各成员函数的正 确性。 参考答案： package chO3Ex

20、ercise; import ch02.Node; /链队列类 class Lin kQueue private Node fro nt;队头的引用 private Node rear;/ 队尾的引用，指向队尾元素 /链队列类的构造函数 public Lin kQueue() front = rear = n ull; /将一个已经存在的队列置成空 public void clear() front = rear = n ull; /测试队列是否为空 public boolea n isEmpty() retur n front = n ull; / 求队列中的数据元素个数并由函数返回其值 p

21、ublic int length() Node p = front; int length = 0;/ 队列的长度 while (p != null) / 一直查找到队尾 p = p.getNext(); +length;/ 长度增 1 return length; /把指定的元素 0插入队列 public void offer(Object o) Node p = new Node(o);/ 初始化新的结点 if (front != null) /队列非空 rear.setNext(p); rear = p;/改变队列尾的位置 else / 队列为空 front = rear = p; /

22、查看队列的头而不移除它，返回队列顶对象，如果此队列为空，则返回 public 0bject peek() if (front != null) /队列非空 return front.getData();/返回队列元素 else return null; / 移除队列的头并作为此函数的值返回该对象，如果此队列为空，则返回 null null public 0bject poll() if (front != null) / Node p = front;/ p front = front.getNext(); return p.getData();/ 队列非空 指向队列头结点 返回队列头结点数据

23、 else return null; / 打印函数，打印所有队列中的元素 ( 队列头到队列尾 ) public void display() if (!isEmpty() Node p = front; while (p != rear.getNext() / 从对头到队尾 System.out.print(p.getData().toString() + ); p = p.getNext(); else System.out.println( 此队列为空 ); / 测试类 public class Exercise3_4_2 public static void main(String ar

24、gs) LinkQueue Q = new LinkQueue(); for (int i = 1; i = 10; i+) / 初始化队列中的元素，其中元素个数为 10 Q.offer(i); System.out.println( 队列中各元素为 ( 从队首到队尾 ) ： ); Q.display();/ 打印队列中元素( 从队首到队尾 ) System.out.println(); if (!Q.isEmpty() System.out.println( 队列非空！ ); System.out.println( 队列的长度为： + Q.length();/输出队列的长度 System.o

25、ut.println ( 队列头元素为： + Q.peek().toString(); / 输出队列头元素 System.out.println ( 去除队列头元素后，队列中各元素为 ( 从队首到队尾 ) ： ); Q.poll();/ 删除元素 Q.display();/ 打印队列中元素 System.out.println(); System.out.println( 去除队列中剩余的所有元素！进行中。); / 输出 Q.clear(); / 清除队列中的元素 if (Q.isEmpty()/队列空，输出 System.out.println( 队列已清空 !); 运行结果：小 C：TIM

26、DOSsyst32cBd_ eze 队列中各元素为寂首到队尾厂 123456789 10 队列非空I 队列欝长度为；10 队首兀素为：丄 去除队首元素后，队列中各元素为队首到队尾” 驚豁誉的所有元看逬行中。 3. 设计一个循环顺序队列类。要求： (1) 循环顺序队列类采用设置标志位的方法来区分循环队列的判空和判满条件。 (2) 循环顺序队列类除构造函数外，成员函数还应包括入队、出队和判队列是否为空的 函数。 (3) 设计一个测试程序进行测试，并给出测试结果。 参考答案： package chO3Exercise; import java.util.Sca nner; /循环顺序队列类(采用设置

27、标志位的方法来区分循环队列的判空和判满条件) class CircleSqQueue_flag private Object queueElem; /队列存储空间 private intfron t;队头的引用，若队列不空，指向队首元素 private int rear;/队尾的引用，若队列不空，指向队尾元素的下一个位置 private intflag; /队列判空与判满的标志，当入列操作后其值置为1,出队操 作后其值置为0 /构造函数 public CircleSqQueue_flag(i nt maxSize) queueElem = new ObjectmaxSize; 为队列分配 ma

28、xSize 个存储单元 front =rear= 0;/ 队头、队尾初始化为0 flag = 0; /判断队列是否为空 public boolea n isEmpty() retur n fron t=rear /判断队列是否已满 public boolea n isFull() return front=rear / 入队操作方法 : 把指定的元素 x 插入队列 public void offer(Object x) throws Exception if (isFull()/ 队列满 throw new Exception( 队列已满 );/ 输出异常 else / 队列未满 queueE

29、lemrear = x;/ x 赋给队尾元素 rear = (rear + 1) % queueElem.length;/ 修改队尾指针 flag=1; / 修改标志位值 null / 出队操作方法 : 移除队列的头并作为此函数的值返回该对象，如果此队列为空，则返回 public Object poll() if (isEmpty()/ 队列为空 return null; else Object t = queueElemfront;/取出队首元素 front = (front + 1) % queueElem.length;/更改队首的位置 flag=0; / 修改标志位值 return t

30、;/ 返回队首元素 / 打印函数 : 打印所有队列中的元素 ( 队首到队尾 ) public void display() if (!isEmpty() /队列非空 / 从队首到队尾 int i = front; do System.out.print(queueElemi.toString() + ); i = (i + 1)% queueElem.length; while(i!=rear); else System.out.println( 此队列为空 ); / 测试类 public class Exercise3_4_3 public static void main(String args) throws Exception CircleSqQueue_flag Q = new CircleSqQueue_flag(100); for (int i = 1; i = 10; i+) /初始化队列中的元素，其中元素个数为10 Q.offer(i); System.out.println(”队列中各元素为(队首到队尾)：); Q.display();打印队列中元素(队首到队尾) System.out.pri ntl n(); if (!Q.isEmpty()队列非空，输出 System.o