题目:将堆栈S1中的元素移至堆栈S2,元素顺序不能改变.只能使用一些非数组变量作为辅助空间.
1.用Java实现,首先使用链表LinkedList构造栈数据结构.
import java.util.LinkedList;
public class CharStack {
private LinkedList<Character> storage = new LinkedList<Character>();
/** 入栈 */
public void push(char v) {
storage.addFirst(v);
}
/** 出栈，但不删除 */
public char peek() {
return storage.getFirst();
}
/** 出栈 */
public char pop() {
return storage.removeFirst();
}
/** 栈是否为空 */
public boolean empty() {
return storage.isEmpty();
}
/** 打印栈元素 */
public String toString() {
return storage.toString();
}
}
2.移动算法
方法move()是移动的算法实现,具体算法为:
1.从栈from中pop一个元素,存于变量achar;
2.将栈to中的所有元素压入栈from;
3.将achar压入栈to;
4.将先前压入栈from的所有元素压入栈to;
5.重复[1-4],直到栈from空; 6.使用整型变量turn区分在栈from中本身自己的元素和来自于栈to的元素;
7.测试,执行代码结果:
Source:[E, D, C, B, A]
MoveTo:[E, D, C, B, A]
public class StackMove {
private CharStack from;
private CharStack to;
public StackMove(CharStack from, CharStack to) {
this.from = from;
this.to = to;
}
public void move() {
int turn = 0;
while (!from.empty()) {
char achar = from.pop();
for (int i = 0; i < turn; i++)
from.push(to.pop());
to.push(achar);
for (int i = 0; i < turn; i++)
to.push(from.pop());
turn++;
}
}
public static CharStack initStack(String s) {
CharStack stack = new CharStack();
char[] chars = s.toCharArray();
for (char c : chars)
stack.push(c);
return stack;
}
public static void main(String[] args) {
CharStack from = initStack("ABCDE");
System.out.println("Source:" + from.toString());
CharStack to = new CharStack();
new StackMove(from, to).move();
System.out.println("MoveTo:" + to.toString());
}
}
责任编辑：小草
