1.txt

关于数据结构

public class Practice_2_3 {

    // 仍未入站，在外面等待的车厢
    private Stack waiting = new Stack();

    // 已经在站内未出的车厢
    private Stack hasIn = new Stack();

    // 已经出来的车厢
    private Stack hasOut = new Stack();

    // 车厢总数
    private int n;

    // 初始化时输入总车厢数 n
    public Practice_2_3(int n) {
        this.n = n;
        // 初始化在外等待的车厢
        for (int i = n; i >= 1; i--) {
            waiting.push(i);
        }
    }

    // 每个时刻不是入站就是出站，遍历这两种情况
    // 其实就是一棵完全二叉树，在每一叶子处打印一种结果（也就是沿着树根到该叶子的路径）
    public void playNow() {

        // 入站的话
        if (!waiting.isEmpty()) {
            hasIn.push(waiting.pop());
            playNow();

            // 把刚入站的车厢退回到等待状态，恢复成原来刚入本函数的状态，好进行下面的出站操作
            waiting.push(hasIn.pop());
        }

        // 出站的话
        if (!hasIn.isEmpty()) {
            hasOut.push(hasIn.pop());
            playNow();
            hasIn.push(hasOut.pop());
        }

        // 遍历完了
        if (hasOut.length() == n) {
            // 栈头的为先出的车厢
            hasOut.printAll();
        }
    }

    public static void main(String[] args) {
        /**
          * test:
          * n=3 输出
          [Head] -> 3 -> 2 -> 1
          [Head] -> 2 -> 3 -> 1
          [Head] -> 2 -> 1 -> 3
          [Head] -> 1 -> 3 -> 2
          [Head] -> 1 -> 2 -> 3
          */
        Practice_2_3 p = new Practice_2_3(3);
        p.playNow();
    }
}


    
    
    


package hartech.ds.practice.stackQueue;

import hartech.ds.*;

/**