Question (in Chinese): http://ac.jobdu.com/problem.php?pid=1366
Question Name: Stack Push Pop Order
Question Description: give two integer arrays. The first one is the order to push the integers into stack. To check whether the second one is an valid order to pop the items from the stack.
Input: the input might contain multiple test cases. Inside each test case, the first line includes one intergers N (1 <= N <= 100000), saying the number of items in the operations. The second line contain N integers, to represent the order to push these elements. The third, also the final, line contains N integers, as the result of popping the items.
Output: “Yes” if the pop order is possible. Otherwise, “No”.
1 2 3 4 5 6 7 8 9 10 | Input: 5 1 2 3 4 5 4 5 3 2 1 5 1 2 3 4 5 4 3 5 1 2 Output: Yes No |
The solution is:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 | /*---------------------------------------------------------------- * Author: Sheng Yu codesays.com * Written: 08/10/2014 * Last updated: 08/10/2014 * * Filename: StackPushPopOrder.java * Compilation: javac StackPushPopOrder.java * Execution: java StackPushPopOrder * JDK Used: 1.7 *----------------------------------------------------------------*/ import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.io.StreamTokenizer; import java.util.Stack; /** * The utility to valid the pop order, with a given push order. * @author Sheng Yu codesays.com */ public class StackPushPopOrder { /** * Check whether the popOrder is possible, when the pushOrder is given. * @param pushOrder the order to push items. * @param popOrder the order to pop items. * @return whether the pop order is possible. */ public final boolean validPopOrder(final int[] pushOrder, final int[] popOrder) { Stack<Integer> numbers = new Stack<Integer>(); int toPopIndex = 0; for (int toPush : pushOrder) { // Push one element. numbers.push(toPush); // Pop as many as we can. while (!numbers.empty() && popOrder[toPopIndex] == numbers.peek()) { numbers.pop(); ++toPopIndex; } } // If the popOrder is valid, the stack numbers should be empty. AND // we get all the numbers in the popOrder. return toPopIndex == popOrder.length; } /** * Stub for test. * @param args the command line arguments. * @throws IOException when input gets error. */ public static void main(final String[] args) throws IOException { StreamTokenizer st = new StreamTokenizer(new BufferedReader( new InputStreamReader(System.in))); int stackSize = 0; int[] pushOrder = null; int[] popOrder = null; StackPushPopOrder validator = new StackPushPopOrder(); while (st.nextToken() != StreamTokenizer.TT_EOF) { // Get the test size. stackSize = (int) st.nval; pushOrder = new int[stackSize]; popOrder = new int[stackSize]; // Get the push order of the elements. for (int i = 0; i < stackSize; ++i) { st.nextToken(); pushOrder[i] = (int) st.nval; } // Get the pop order of the elements. for (int i = 0; i < stackSize; ++i) { st.nextToken(); popOrder[i] = (int) st.nval; } // Check whether the pop order is possible. if (validator.validPopOrder(pushOrder, popOrder)) { System.out.println("Yes"); } else { System.out.println("No"); } } } } |