栈的定义和数据类型
栈定义
又称堆栈，一种运算受限的线性表，仅允许在表的一端进行插入和删除运算。对栈进行运算的一端称为栈顶，栈顶的第一个元素称为栈顶元素，相对地另一端称为栈底。
栈的基本操作
- 入栈
public E push(E item) {
addElement(item);
return item;
}
- 出栈 pop() （要先判断非空）
public synchronized E pop() {
E obj;
int len = size();
obj = peek(); //调用peek
removeElementAt(len - 1); //下标是从底往上算的
return obj;
}
- 获取栈顶元素 peek() （要先判断非空）
public synchronized E peek() {
int len = size();
if (len == 0) //空会抛异常
throw new EmptyStackException();
return elementAt(len - 1);
}
- 判断栈是否为空 empty()
public boolean empty() {
return size() == 0;
}
- 搜索（返回距离栈顶元素个数（栈顶元素算第一个））
public synchronized int search(Object o) {
int i = lastIndexOf(o);
if (i >= 0) {
return size() - i;
}
return -1;
}
栈的存储结构
- 顺序存储结构：可以使用一个数组stack[maxSize]和一个整型变量top来实现，数组存储栈的元素，变量表示栈顶指针。
- 链式存储结构：可以由结点构成的单链表实现，此时表头指针称为栈顶指针。
- 两种存储结构顶插入删除时间复杂度都是O(1)
- Java中的栈Stack.class是继承至Vector<E>
extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable，所以内部是由数组实现的。
栈和递归
在计算机系统内，执行递归函数是通过自动使用栈来实现的，栈中每个元素包含递归函数的每个参数域、每个局部变量域和调用后的返回地址域。每次进行函数调用时，都要把相应的值压入栈，每次调用结束时，按照本次返回地址返回到指定的位置执行。
和栈相关的经典算法
- 倒叙打印
- 字符配对匹配（检查语法）
输入一串字符，判断这个字符串的括号是否匹配，若匹配则返回1，否则返回0.
做括号进栈，右括号匹配出栈
public static int pickStr(String str) {
if(str==null || str.length()<=0)return 0;
int len = str.length();
for(int i=0; i<len; i++) {
String c = ""+str.charAt(i);
switch(c){
case "{":;
case "[":;
case "(":
stack.push(c);
break;
case "}":
if(stack.empty())return 0;//注意先判断非空
if("{".equals(stack.peek())) {
stack.pop();
}else {
return 0;
}
break;
case "]":
if(stack.empty())return 0;
if("[".equals(stack.peek())) {
stack.pop();
}else {
return 0;
}
break;
case ")":
if(stack.empty())return 0;
if("(".equals(stack.peek())) {
stack.pop();
}else {
return 0;
}
break;
}
}
return stack.empty()?1:0;
}
- 进制转换
将十进制数num转换为r进制的过程为num除以基数r，得到余数y0,依次类推，然后再从高位到低位组合。
String transform(long num, int r){
Stack<Integer> stack = new Stack<Integer>();
while(num !=0){
int k = num % r;
stack.push(k);
num = num/r;
}
StringBuilder sb = new StringBuilder();
while(!stack.empty()){
sb.append(stack.pop());
}
return sb.toString();
}
- 中缀表达式和后缀表达式
- 中缀表达式：把双目运算符出现在两个操作数中间的表达式称为中缀表达式。如12/6+2
- 后缀表达式：又称逆波兰式，把运算符放在两个运算对象的后面。如上面中缀表达式对应的后缀表达式为126/2+
- 中缀表达式既要考虑括号还要考虑运算符的优先级，对计算机来说太复杂，后缀表达式能很好解决这种问题，计算过程完全按照运算符出现对先后顺序，整个计算过程只需扫描一遍即可。
- 中缀表达式转换为后缀表达式对规则：把每个运算符都移到他的两个元算对象的后面，然后删除所有的括号即可。
中缀表达式转换为后缀表达式的算法如下
static Stack<String> stack = new Stack<String>(); //运算符栈
public static String change(String midStr) {
StringBuilder sb = new StringBuilder();
if(midStr == null || midStr.length()<1) {
return null;
}
int len = midStr.length();
stack.push("@"); //给栈底放入特殊字符，最低优先级
for(int i=0; i<len; i++) {
String c = midStr.charAt(i)+"";
//空格不用处理
if(c.equals(" ")) {
continue;
}else if(c.equals("(")) { //左括号直接加入运算符栈
stack.push(c);
continue;
}else if(c.equals(")")) { //右括号，使括号内的人留在栈中的运算符依次出栈并写入结果sb
while(!stack.peek().equals("(")){
sb.append(stack.pop());
}
stack.pop(); //出左括号
}else if(c.equals("+")||c.equals("-")||c.equals("*")||c.equals("/")) {//对于运算符，使暂存与栈顶且不低于c优先级的运算符依次出栈并写入结果
String w = stack.peek();
while(precedence(w) >= precedence(c)) {
sb.append(w);
stack.pop();
w=stack.peek();
}
stack.push(c); //符号入栈
continue;
}else { //此处必须为数字或小数点，否则中缀表达式错误
char ch = midStr.charAt(i);
if((ch<'0' || ch>'9') && ch!='.') {
return null;
}
while((ch>='0' && ch<='9') || ch=='.') { //把数值每一位依次假如结果字符串
sb.append(ch+"");
i++;
if(i>=len)break; //记得判断
ch = midStr.charAt(i);
}
i--;
sb.append(" "); //数字之间以及和符号用空格隔开
continue;
}
}
//把暂存在栈中的运算符依次退栈并写到结果
String s = stack.pop();
while(!s.equals("@")) {
if(s.equals("(")){
return null; //还有左括号，说明表达式出错
}else {
sb.append(s);
s = stack.pop();
}
}
return sb.toString();
}
private static int precedence(String w) {
switch(w) {
case "+":
case "-":
return 1;
case "*":
case "/":
return 2;
case "(":
case "@":
default:
return 0;
}
}
change("12+(3(20/4)-8)6") 返回“12 3 20 4 /*8 -6 *+”
- 后缀运算求值
static Stack<Double> stack = new Stack<Double>(); //存储操作数和中间结果
public static double compute(String str) {
if(str==null || str.length()<=0) {
return 0.0;
}
double x,y; //保存符点数
int len = str.length();
for(int i=0; i<len; i++) {
if(str.charAt(i) == ' ') { //空格不做处理
i++;
continue;
}
switch(str.charAt(i)) {
case '+':
x = stack.pop() + stack.pop(); //栈顶两个加法，赋值给x
break;
case '-':
x = stack.pop();
x = stack.pop() - x; //先进栈到减后进栈的
break;
case '*':
x = stack.pop() * stack.pop();
break;
case '/':
x = stack.pop();
if(x!=0.0) { //被除数不能为0
x = stack.pop()/x;
}else {
return 0.0;
}
break;
default:
x = 0; //保存浮点数的整数部分
while(str.charAt(i)>=48 && str.charAt(i)<=57) {
x = x*10 + str.charAt(i) - 48;
i++;
}
if(str.charAt(i) == '.') {
i++;
y = 0; //利用y保存扫描到到小数部分到值
double j = 10.0; //用j作为相应小数位到权值
while(str.charAt(i) >= 48 && str.charAt(i) <= 47) {
y = y + (str.charAt(i) - 48)/j;
i++;
j = j*10;
}
x = x + y; //合并为一个小数
}
}
stack.push(x); //操作数或中间结果入栈
}
x = stack.pop(); //栈中只有一个最终结果则正确，否则是错误的
if(stack.empty())return x;
return 0.0;
}
- n个布尔值的所有可能组合 2^n
输出n个布尔值的所有可能组合，当n=1时有0和1两种，当n=2时有00、01、10、11四种，当n=n时，有2的n次方种，f(n) = 2*f(n-1) = 2^n. 设n个布尔量用布尔数组表示b[n]，要得到b[0]-b[n-1]这n个布尔值的组合，则可看成b[0]在分别为true和false时b[1]-b[n-1]的组合。
private void comp(bool[] b, int k, int n){
if(k==n){ //递归停止条件,输出排列好的组合
for(int 1=0; i<n; i++){
System.out.print(" " + b[i]);
}
System.out.println("");
}else{
b[k] = false;
return comp(b, k+1, n);
b[k] = true;
return comp(b, k+1, n);
}
}
调用时k从0开始
- 1-n个元素的全排列
输出1-n这n个自然数的全排列 n!
n! = n*(n-1)!
用一个数组a[n]来保存1-n之间的n个自然数，对于i=0n-1,每次使a[0]同a[i]交换（i=0,1,2...n-1）后，进行递归，然后再交换a[0]与a[i]使它恢复为此排列前的状态；同理，对于i=1n-1,每次使a[1]同a[i]交换（i=1,2...n-1）后，进行递归，然后再交换a[1]与a[i]使它恢复为此排列前的状态；依次类推。
private void permute(int[] a, int s, int n){
int temp;
if(s==n-1){ //递归到最后一个元素结束，输出结果
for(int i=0;i< n; i++){
System.out.print(""+a[i]);
}
System.out.println("");
}else{
for(int i=s; i< n; i++){ //循环n-s次，每次使a[s]取一个新值
temp = a[s]; a[s] = a[i]; a[i] = temp; //交换a[s]和a[i]
permute(a, s+1; n);
temp = a[s]; a[s] = a[i]; a[i] = temp;//交换回 a[s]和a[i]
}
}
}
调用时s从0开始
- 迷宫
一个迷宫包含m行n列小方格，每个方格用0表示可通行，1表示墙壁，当然入口和出口都是0才是可通行的。从入口开始，每次可上下左右任意方向移动一格，求从入口到出口到一条路径。
int[][] maze;
int[][] mark;
int m, n;
int[][] move= {{1,0}, {0,1}, {-1,0}, {0,-1}}; //右下左上的偏移下标
private void seekPath(int[][] path) {
m = path.length;
n = path[0].length;
maze = new int[m+2][n+2]; //加上围墙的迷宫数组
mark = new int[m+2][n+2]; //保存访问标记
for(int i=0; i<m+2; i++) {
for(int j=0; j<n+2; j++) {
//给迷宫数组外围加上一层“围墙”,这样迷宫数组每个位置都有四个方向，不用去判断各种边界条件
if(i==0 || i==m+1 || j==0 || j==n+1) {
maze[i][j] = 1;
}else {
maze[i][j] = path[i-1][j-1];
}
mark[i][j] = 0;
}
}
mark[1][1] = 1; //入口设为1，表示访问过
if(seek(1, 1)) { //从新迷宫数组入口（1，1）处递归
System.out.print("(" + 0 + "," + 0 + ")"); //按所经过位置的反序输出，最后输出起点坐标
}else {
System.out.print("无通路");
}
}
private boolean seek(int x, int y) {
//从迷宫中坐标点（x,y）的位置寻找通向终点的路径，找到返回true，否值返回false
int g,h; //作为下一个位置的行列坐标
if(x==m && y==n)return true; //到达出口
for(int i=0; i<4; i++) { //循环尝试4个方向
g = x + move[i][0];
h = y + move[i][1];
if(maze[g][h]==0 && mark[g][h]==0) { //下一个为0，且没访问过
mark[g][h] = 1; //标记为访问
if(seek(g,h)){ //继续递归找下一个
int ap = g-1;
int bp = h-1;
System.out.print("(" + ap + "," + bp + ")"); //找到打出坐标
return true;
}
}
}
return false;
}
- 汉诺塔问题
相传它源于印度神话中的大梵天创造的三个金刚柱a,b,c，一根柱子上叠着上下从小到大n个黄金圆盘。大梵天命令婆罗门将这些圆盘按从小到大的顺序从a柱移动到c柱子上，其中大圆盘不能放在小圆盘上面，依次打出移动过程。
/**
* @param n n个圆盘
* @param a 柱子a
* @param b 柱子b
* @param c 柱子c
*/
private void hanTower(int n, char a, char b, char c) {
if(n==1) {
System.out.println( a + " -> " + c); //一个，直接从a柱子搬到c柱子
}else {
hanTower(n-1, a, c, b); //首先以c柱子为过渡，把a上面到n-1个搬到b上
System.out.println( a + " -> " + c); //再把a的搬到c
hanTower(n-1, b, a, c); //后续目标，把上面搬到过渡柱b上的n-1个搬到c上
}
}
public static void main(String[] args) {
hanTower(3, 'a', 'b', 'c');
}
