栈的一些应用

大家都知道栈是先进后出的一种数据结构。。。

栈是运算受限的线性表（队列也一样）， 其实现有顺序存储（数组）和链式存储（链表）两种实现方式。

由于栈的先进后出的特性， 使得它可以在很多场合下都可以大显身手：

1. 数制转换， 比如十进制转八进制

Stack s = new xxxStack();
while(num > 0) {
    s.push(num % 8);
    num = num / 8;
}

while(!s.isEmpty()) System.out.println(s.pop());

2. 括号匹配 {}， [], ()
思路也是一样的， 比如对于字符串 {(){[]}}
每读入一个字符, 与栈顶top进行比较， 看是不是匹配的另一半， 如果是则出栈， 如果不是则进栈。

3. 判断回文字符串
虽然Java API提供了相关的方法可以直接使用， 但其也有可能是基于栈来实现的（未核实， 需读源代码）。。。（已核实： 基于数组的直接交换。。。）

public static boolean isPlalindrome(String str){ 　　
    return new StringBuffer(str).reverse().toString().equals(str); 　　
} 

【Update】StringBuffer的reverse方法实现， 部分代码：

private static void reverse(char[] value) {
	int n = value.length - 1;
	for (int j = (n - 1) >> 1; j >= 0; --j) {
		char temp = value[j];
		char temp2 = value[n - j];
		value[j] = temp2;
		value[n - j] = temp;
	}
}

那如果直接用栈又是如何来实现呢？
那就得分两种情况。
1) 字符串长度为偶数
2) 字符串长度为基数

当为偶数的时候， 只需要把前一半压栈， 然后再遍历后一半， 如果每一个值都和栈顶相同则出栈。 如果任何一个值不匹配， 则可以断定该字符串不是回文字符串。

而对于基数则只需要skip中间的那个字符就可以了， 其他的和偶数情况一致。

评论

1 楼 huhu_long 2011-10-20  

补充1：

在二叉树遍历的时候，如果采取非递归的方式，则可以借助Stack来实现

比如先根遍历：

if (node == null)
	return;
Stack stack = new Stack();

while (node.left != null) {
	stack.push(node);
	System.out.print(node.value);
	node = node.left;
}

System.out.print(node.value);
node = (Node) stack.pop();

while (node != null) {
	node = node.right;
	while (node.left != null) {
		stack.push(node);
		System.out.print(node.value);
		node = node.left;
	}

	System.out.print(node.value);
	if (stack.empty())
		break;
	node = (Node) stack.pop();
}