剣指offerブラシ問題まとめ——スタック、スタック、キュー編

1.2つのスタックでキューを実装
【テーマ】
2つのスタックで1つのキューを実現し、キューのPushとPop操作を完了します.キュー内の要素はintタイプです.
【コード】

package swear2offer.construction;

import java.util.Stack;

public class StackToQueue {

    /**
     *            ，      Push   Pop   。         int   。
     *
     *          ，          
     *  
     * */

    Stack<Integer> stack1 = new Stack<Integer>();
    Stack<Integer> stack2 = new Stack<Integer>();

    public void push(int node) {
        stack1.add(node);
    }

    public int pop() {
        if (stack2.empty()) {
            while (!stack1.empty()) {
                stack2.add(stack1.pop());
            }
        }

        return stack2.pop();
    }

}

【考え方】
2つのスタックstack 1とstack 2は、キューをシミュレートする能力で、挿入要素を直接stack 1に挿入すればよい.記憶要素は保存を保証すれば、両者の違いはポップアップ要素の順序であり、キューからポップアップされた要素はstackの一番下にあるため、stack 1の要素を順次ポップアップし、stack 2に入れる必要がある.このようにエレメントをポップアップするとき、stack 2が空でない限り、stack 2の要素がポップアップされます.stack 2が空の場合は、stack 1の要素をstack 2に押し込んでから、stack 2をポップアップします.
2.スタックの圧入、イジェクトシーケンス
【テーマ】
2つの整数シーケンスを入力します.最初のシーケンスはスタックの圧入順序を表します.2番目のシーケンスがスタックのポップアップ順序である可能性があるかどうかを判断してください.スタックに押し込まれたすべての数字が等しくないと仮定します.例えば、シーケンス1,2,3,4,5は、あるスタックの押し込み順序であり、シーケンス4,5,3,2,1は、そのスタックシーケンスに対応するポップアップシーケンスであるが、4,3,5,1,2は、そのスタックシーケンスのポップアップシーケンスであることは不可能である.(注:この2つのシーケンスの長さは等しい)
【コード】

/**
     *         ，             ，
     *                     。
     *               。     1,2,3,4,5         ，
     *    4,5,3,2,1                ，
     *   4,3,5,1,2                。（  ：            ）
     * */

    public boolean IsPopOrder(int [] pushA,int [] popA) {

        int n,start,end,i,j;

        n = pushA.length;

        if (n == 0) return false;

        Stack<Integer> stack = new Stack<>();

        start = 0;
        end = GetIndex(pushA, popA[0]);

        if (end < 0) return false;

        //  start end         stack 
        for (j=start; j<=end; j++) {
            stack.add(pushA[j]);
        }

        start = end + 1;

        i = 0;
        while (i < n) {
            if (stack.peek() == popA[i]) {
                stack.pop();
                i++;
                continue;
            } else {
                end = GetIndex(pushA,popA[i]);
                if (start > end) return false;
                for (j=start; j<=end; j++) {
                    stack.add(pushA[j]);
                }
                start = end + 1;
            }
        }

        return true;

    }

    //            
    public int GetIndex(int[] a, int target) {

        for(int i=0; i<a.length; i++) {
            if (a[i] == target) {
                return i;
            }
        }
        return -1;
    }

【考える】
whileサイクルとforサイクル、同じi