就地移动栈数据

　　题目:将堆栈S1中的元素移至堆栈S2,元素顺序不能改变.只能使用一些非数组变量作为辅助空间.

　　1.用Java实现,首先使用链表LinkedList构造栈数据结构.

import java.util.LinkedList;

public class CharStack {

　　private LinkedList storage = new LinkedList();

　　/** 入栈 */

　　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());

　　}

}

　　本文出自 “子 孑” 博客，请务必保留此出处http://zhangjunhd.blog.51cto.com/113473/55162