2.1.2 栈、队列、串
1．栈、队列的概念及特点
2．函数如何压栈
3．栈、队列运用到算法中
4．字符串拷贝、反转等操作
栈，又称为后进先出（LIFO: last in first out）线性表，是限制在表的一端进行插入或者删除的操作，每次出栈的元素都是栈顶所在的元素，也就是最后进栈的元素，如图2.5所示。
按照存储方式，栈分为顺序栈和链式栈。顺序栈一般是由一维数组和栈顶变量组成。链式栈不会出现满栈溢出的情况。
函数通过栈来辅助完成调用过程。例如，Z函数调用A函数，首先会先将传给A的参数压栈，将现在这个指令〔就是A(…)〕的下一个指令的地址压入栈中，以便A函数完后返回到Z中继续执行。然后进入A函数的内存空间，先调用PUSH EBP，也就是将Z的EPB的内容（地址0x000f）压入栈中，接着再MOV EBP ESP，让EBP有一个新的栈顶。最后再将A函数的局部变量压入栈中，开始执行A函数的代码。这时，栈和EBP的情况如图2.6所示。
图2.6 函数在栈的存储结构
函数的参数入栈时，按照从右到左的压栈顺序，并注意高地址和低地址，压栈时以机器字为单位且所有参数字对齐。
队列，又称为先进先出（FIFO:first in first out）线性表，它的所有插入操作（又叫入队）在队列的一端，而删除操作（又叫出队）在队列的另一端，如图2.7所示。
队列同样也有顺序存储和链式存储，需要两个变量或指针来指示队头和队尾。在顺序队列中，由于队列的队头和队尾位置是时刻变化着的，可能会存在队头到顶了，而队尾后面空出来很多新的空闲区域，因此，循环队列利用假溢出解决了该问题。队头到顶之后，重新回到最底部，当头指针绕上一圈赶上尾指针，视为满队。
循环队列个数＝（队尾－队头＋数组大小）mod数组大小。
图2.7 队列
字符串也是面试中常考的内容，也是实际工作中最实用的技术。下面列出所有字串面试题。
试题1．不调用库函数地实现strCpy。
strCpy (char * src , const char * des)。有几点需要注意。
" src长度为空〔len(src)==0〕。
" src和des地址相同(src==des)。
代码如下。
char *strcpy(char *strDest,const char *strSrc) { if(strDest＝＝NULL||strSrc＝＝NULL) return NULL if(strDest==strSrc) return strDest char*tempptr=strDest while((*strDest++=*strSrc++)!='∕0') retum tempptr } int strlen( const char*str) { assert( strt!=NULL);//断言字符串地址非0 int len; while((*str++)!='\0') { len++; } return len; } |
试题2．自写函数实现数字与字符串之间的相互转化。
思路：整数转化成字符串，可以采用加'0'，然后再逆序，整数加'0'就会隐性转化为char类型的数。字符串转化成整数，可以采用减'0'，再乘以10累加的方法，字符串减'0'就会隐性转化为int类型的数。
试题3．不调用库函数实现字符串反转。
代码如下。
package com.others; publicclassrevertStr { publicstaticvoid main(String[] args) { System.out.println(inverse("liuling")); } publicstatic String inverse(String str){ char[] chars = str.toCharArray(); //得到字符数组 for (int i = 0; i < chars.length/2; i++) { char temp = chars[i]; chars[i] = chars[chars.length-i-1]; chars[chars.length-i-1] = temp; } return String.copyValueOf(chars); } } |
版权声明：51Testing软件测试网获作者授权连载本书部分章节。
任何个人或单位未获得明确的书面许可，不得对本文内容复制、转载或进行镜像，否则将追究法律责任。
相关文章：
