数据结构之栈、队列、字符串——软件测试工程师面试秘籍（06）

lsekfe

考点：
　　·栈、队列的概念及特点
　　·函数如何压栈
　　·字符串复制、反转等操作

　　1．栈
　　栈又称后进先出（Last In First Out，LIFO）线性表。限制在栈的一端进行插入或者删除的操作，每次出栈的元素都是栈顶的元素，即最后入栈的元素，如图2.5所示。
　　按照存储方式，栈分为顺序栈和链式栈。顺序栈一般由一维数组和栈顶变量组成。链式栈不会出现栈溢出的情况。
　　函数通过栈来辅助完成调用过程。例如，Z()函数调用A()函数时，首先，将传给A的参数压栈，将现在这条指令（A(…)）的下一条指令的地址压入栈中，以便A()函数执行完后返回Z()函数中继续执行。然后，进入A()函数的内存空间，调用PUSH EBP，即将Z()函数的EPB的内容（地址0x000F）压入栈中。接着，调用MOV EBP ESP，让EBP有一个新的栈顶。最后，将A()函数的局部变量压入栈中，开始执行A()函数的代码。这时，栈和EBP的情况如图2.6所示。

图2.5  栈

图2.6  栈和EBP的情况
　函数参数入栈时，按照从右到左的顺序，并要注意高地址和低地址。入栈时以机器字长为单位且所有参数按字对齐。

　　2．队列
　　队列又称先进先出（First In First Out，FIFO）线性表，它的所有插入操作（又称入队）在队列的一端，而删除操作（又称出队）在队列的另一端，如图2.7所示。

图2.7  队列
队列同样也有顺序队列和链式队列，需要两个变量或指针来指示队头和队尾。在顺序队列中，由于队列的队头和队尾位置是时刻变化的，因此可能会到达队头了，而队尾空出来很多新的空闲区域。而循环队列利用假溢出解决了该问题。到达队头之后，重新回到队尾，当队头指针连接到队尾指针时，视为满队。
　　循环队列次数=(队尾-队头+数组长度)mod(数组长度)
　　3．字符串
　　字符串是面试中常考的内容，也是实际工作中最实用的技术之一。下面列出关于字符串的面试题。
　　试题1．不调用库函数实现字符串复制函数strCpy()。
　　分析：函数声明为strCpy (char * src , const char * des)，其中有如下几点需要注意。
　　（1）src长度为0。
　　（2）src和des地址相同（src==des）。
　　答案：代码如下。

1. char *strcpy(char *strDest,const char *strSrc)
   
2. {   
   
3.     if(strDest==NULL||strSrc==NULL)
   
4.        return NULL
   
5.     if(strDest==strSrc)
   
6.        return strDest
   
7.     char*tempptr
   
8. =
   
9. strDest
   
10.     while((*strDest++=*strSrc++)!
    
11. =
    
12. '∕0'
    
13. )
    
14.     retum tempptr
    
15. }
    
16. int strlen(const char*str)
    
17. {
    
18.   assert(strt!=NULL);//断言字符串地址非0
    
19.   int len;
    
20.   while((*str++)!='\0')
    
21.   {    len++;  }
    
22.   return len;
    
23. }

复制代码

试题2．编写函数实现整数与字符串之间的相互转化。
　　分析：整数转化成字符串，可以采用加0、然后逆序的方法，整数加0后会隐性转化为字符串；字符串转化成整数，可以采用减0、然后乘以10累加的方法，字符串减0后会隐性转化为整数。

　　试题3．不调用库函数实现字符串反转。
　　答案：代码如下。

1. package com.others;
   
2. publicclassrevertStr {
   
3. 
   
4. publicstaticvoid main(String[] args) {
   
5.          System.out.println(inverse("liuling"));
   
6.     }
   
7. 
   
8. publicstatic String inverse(String str){
   
9. char[] chars=str.toCharArray(); //得到字符数组
   
10. for (int i=0;i<chars.length/2;i++) {
    
11. char temp=chars[i];
    
12.            chars[i]=chars[chars.length-i-1];
    
13.            chars[chars.length-i-1]=temp;
    
14.         }
    
15. 
    
16. return String.copyValueOf(chars);
    
17.     }
    
18. 
    
19. }

复制代码