ID #5710

就地移动栈数据

题目:将堆栈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());
  }
}


2011-07-01 18:29
阅读:
I'm VC , Just U know Y
本站部分文章来源于互联网,版权归原作者所有。

延伸阅读: