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

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

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

3、则队列的判空条件是（A ）。A. front=rearB. front!=rearC. fron t=rear+1D. fron t=（rear+1）% maxSize&在循环顺序队列中，假设以少用一个存储单元的方法来区分队列判满和判空的条件， 和rear分别为队首和队尾指针，它们分别指向队首元素和队尾元素的下一个存储单元， 队列的最大存储容量为maxSize，则队列的判满条件是（D ）。A. front=rearB. front!=rearC. fron t=rear+1D. fron t=（rear+1）% maxSize9. 在循环顺序队列中，假设以少用一个存储单元的方法来区分队

4、列判满和判空的条件，和rear分别为队首和队尾指针，它们分别指向队首元素和队尾元素的下一个存储单元， 队列的最大存储容量为maxSize，则队列的长度是（ C ）。A. rear-frontB. rear-front+1C. （rear-fro nt+maxSize）%maxSize D. （rear-fro nt+1）%maxSize10. 设长度为n的链队列采用单循环链表加以表示，若只设一个头指针指向队首元素，则入 队操作的时间复杂度为（B ） °2A . 0（1）B. 0（n） C. O（log2n）D . 0（n ）、填空题1. 栈是一种操作受限的特殊线性表，其特殊性体现在其

5、插入和删除操作都限制在行。允许插入和删除操作的一端称为栈顶，而另一端称为 栈底。栈具有 后进先出 的特点。2. 栈也有两种存储结构，一种是顺序存储，另一种是 链式存储；以这两种存储结构存储的栈分别称为顺序栈和链栈。3. 在顺序栈中，假设栈顶指针top是指向栈顶元素的下一个存储单元，则顺序栈判空的条件是top=0 ;栈顶元素的访问形式是stackElemtop-1 ;4. 在不带表头结点的链栈中，若栈顶指针top直接指向栈顶元素，则将一个新结点p入栈时修改链的两个对应语句为p.setNext(top) ； top=p; 。5. 在不带表头结点的链栈中，若栈顶指针top直接指向栈顶元素，则栈顶元素

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

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

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

9、是否为回文序列，若是则返回true值，否则返回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 < str.length(); i+) char c = (Character) S.pop().charValue(); if (c != str.charAt(i)return false;return true; 3. 假设以一

10、个数组实现 两个栈：一个栈以数组的第一个存储单元作为栈底，另一个栈以数 组的最后一个存储单元作为栈底 , 这种栈称为顺序双向栈。试编写一个顺序双向栈类DuSqStack,类中要求编写 3个方法。一个是构造方法DuDuSqStack(int maxSize),此方法实现构造一个容量为 maxSize 的顺序双向空栈；一个是实现入栈操作的方法 push(Object X,int i),此方法完成将数据元素X压入到第i(i=0或1)号栈中的操作；一个是实现出栈操作的方法pop( int i), 此方法完成将第 i 号栈的栈顶元素出栈的操作。参考答案 :class DuSqStackprivate O

11、bject stackElem; /栈存储空间private int top0; /栈顶指针 , 指示第 0 号的栈顶元素的下一个位置private int top1; / private int base0;/ private int base1;/栈顶指针 , 指示第 1 号的栈顶元素的下一个位置栈尾指针 , 指示第 0 号的栈底元素栈尾指针 , 指示第 1 号的栈底元素/ 构造方法public DuSqStack(int maxSize) / 初始化栈 , 即构造一个双向空栈stackElem = new ObjectmaxSize;/ top0=base0=0; top1=base1=

12、maxSize-1;为栈分配 maxSize 个存储单元/ 入栈操作方法public void push(Object X, int i) throws Exception II将数据元素X压入到第i(i的值为0或1)号栈中 if (top0 > top1) /栈满throw new Exception(" 栈已满 ");II 抛出异常else if (i=0)stackElemtop0+=X;else if (i=1)stackElemtop1-=X;/ 出栈操作方法public Object pop(int i) throws Exception /将S中第i号栈

13、的栈顶元素出栈，并返回栈顶元素值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 号栈为空 ");elsex=stackElem+top1;return x; / DuSqStack类结束4. 循环顺序队列类采用设置一个计数器的方法来区分循环队列的判空和判满。试分别编写顺序循环队列中入队和出队操作的函数。参考答案 :/

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

15、ct 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 (num=0)/ 队列为空return null

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

17、法分别如下：/ 队列置空操作方法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 void poll() throws Exception / 移除带头结点的

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

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

20、 求栈中的数据元素个数并由函数返回其值 public int length() return top;/ 查看栈顶对象而不移除它，返回栈顶对象 public Object peek() if (!isEmpty()/ 栈非空return stackElemtop - 1; /栈顶元素else/ 栈为空 return null;/ 移除栈顶对象并作为此函数的值返回该对象 public Object pop() if (top = 0)/ 栈为空return null;else / 栈非空return stackElem-top;/修改栈顶指针，并返回栈顶元素/ 把 o 压入栈顶public vo

21、id 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-)打印System.out.print(stackElemi.toString() + " ");

22、/ / 测试类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+)/ 初始化栈中的元素，其中元素个数为 10S.push(i);System.out.println("栈中各元素为 (栈顶到栈底 ) ： ");S.display();/ 打印栈中元素(栈低到栈顶)System.out.println();if (!S.isE

23、mpty()/栈非空，输出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

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

25、ise;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;/ 求队列中的数据元素个数并由函数返回其值 public int leng

26、th() Node p = front;int length = 0;/ 队列的长度while (p != null) / 一直查找到队尾 p = p.getNext();+length;/ 长度增 1return length;/把指定的元素 0插入队列public void offer(Object o) Node p = new Node(o);/ 初始化新的结点 if (front != null) /队列非空rear.setNext(p);rear = p;/改变队列尾的位置 else/ 队列为空front = rear = p;/ 查看队列的头而不移除它，返回队列顶对象，如果此队列

27、为空，则返回 public 0bject peek() if (front != null) /队列非空return front.getData();/返回队列元素elsereturn null;/ 移除队列的头并作为此函数的值返回该对象，如果此队列为空，则返回nullnullpublic 0bject poll() if (front != null) /Node p = front;/ p front = front.getNext(); return p.getData();/队列非空指向队列头结点返回队列头结点数据 elsereturn null;/ 打印函数，打印所有队列中的元素 (

28、 队列头到队列尾 )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 args) LinkQueue Q =

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

30、出队列的长度System.out.println (" 队列头元素为： " + Q.peek().toString(); / 输出队列头元素System.out.println (" 去除队列头元素后，队列中各元素为 ( 从队首到队尾 ) ： "); Q.poll();/ 删除元素Q.display();/ 打印队列中元素System.out.println();System.out.println(" 去除队列中剩余的所有元素！进行中。"); / 输出Q.clear(); / 清除队列中的元素if (Q.isEmpty()/队列空，

31、输出System.out.println(" 队列已清空 !"); 运行结果：小 C：TIMDO<Ssyst»32cBd_ eze队列中各元素为寂首到队尾厂123456789 10 队列非空I队列欝长度为；10 队首兀素为：丄 去除队首元素后，队列中各元素为<队首到队尾”驚豁誉的所有元看逬行中。3. 设计一个循环顺序队列类。要求：(1) 循环顺序队列类采用设置标志位的方法来区分循环队列的判空和判满条件。(2) 循环顺序队列类除构造函数外，成员函数还应包括入队、出队和判队列是否为空的 函数。(3) 设计一个测试程序进行测试，并给出测试结果。参考答案：pa

32、ckage chO3Exercise;import java.util.Sca nner;/循环顺序队列类(采用设置标志位的方法来区分循环队列的判空和判满条件)class CircleSqQueue_flag private Object queueElem; /队列存储空间private intfron t;队头的引用，若队列不空，指向队首元素private int rear;/队尾的引用，若队列不空，指向队尾元素的下一个位置private intflag; /队列判空与判满的标志，当入列操作后其值置为1,出队操作后其值置为0/构造函数public CircleSqQueue_flag(i

33、nt maxSize) queueElem = new ObjectmaxSize; 为队列分配 maxSize 个存储单元 front =rear= 0;/ 队头、队尾初始化为0flag = 0;/判断队列是否为空public boolea n isEmpty() retur n fron t=rear&&flag=0; /判断队列是否已满public boolea n isFull() return front=rear&&flag=1;/ 入队操作方法 : 把指定的元素 x 插入队列 public void offer(Object x) throws E

34、xception if (isFull()/ 队列满throw new Exception(" 队列已满 ");/ 输出异常 else / 队列未满queueElemrear = x;/ x 赋给队尾元素 rear = (rear + 1) % queueElem.length;/ 修改队尾指针 flag=1; / 修改标志位值 null/ 出队操作方法 : 移除队列的头并作为此函数的值返回该对象，如果此队列为空，则返回 public Object poll() if (isEmpty()/ 队列为空 return null;else Object t = queueEle

35、mfront;/取出队首元素front = (front + 1) % queueElem.length;/更改队首的位置flag=0; / 修改标志位值 return t;/ 返回队首元素/ 打印函数 : 打印所有队列中的元素 ( 队首到队尾 ) 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+)/初始化队列中的元素，其中元素个数为