Question (in Chinese): http://ac.jobdu.com/problem.php?pid=1512
Question Name: Queue With Two Stacks
Question Description: simulate a queue class with two stacks. Write a test program for the queue. If queue is empty and pop, print -1.
Input: the first list is an integer, saying the number of instructions in the following lines. Otherwise, each line is an instruction: either “POP” or “PUSH val” (val is an integer).
Output: the popped result.
1 2 3 4 5 6 7 8 | Input: 3 PUSH 10 POP POP Output: 10 -1 |
This question is the same as the problem 3.5 from Cracking the Coding Interview.
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 80 81 82 83 84 85 86 87 88 89 90 91 92 93 | /** * Filename : QueueWithTwoStacks.java * Dependency: None * Author : Sheng Yu (codesays.com) * Create at : 2014-08-01 * JDK used : 1.7 * Change log: None */ import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.io.StreamTokenizer; import java.util.NoSuchElementException; import java.util.Stack; /** * * @author Sheng Yu (codesays.com) * * @param <T>: the type of the element in the queue. */ class Queue<T> { // Every element enter the entrance stack firstly, and then switch to // exit stack waiting to be popped out. private Stack<T> entrance = new Stack<T>(); private Stack<T> exit = new Stack<T>(); /** * Remove the oldest element in the queue and return it. * @return the oldest element in the queue. * @throws NoSuchElementException: when the queue is empty. */ public T remove() throws NoSuchElementException { if (exit.empty()) { if (entrance.empty()) { throw new NoSuchElementException("Queue is empty."); } else { // Move all elements in entrance stack to exit stack. while (!entrance.empty()) { exit.push(entrance.pop()); } } } return exit.pop(); } /** * Add a new element to the queue. * @param element: the new element to add to queue. */ public void add(T element) { entrance.add(element); } } public class QueueWithTwoStacks { public static void main(String[] args) throws IOException, IllegalArgumentException { StreamTokenizer st = new StreamTokenizer(new BufferedReader( new InputStreamReader(System.in))); // Get the number of following instructions. But actually // it is useless. int instructionCount = -1; if (st.nextToken() != StreamTokenizer.TT_EOF) { instructionCount = (int)st.nval; } Queue<Integer> test = new Queue<Integer>(); boolean popSuc = true; Integer oldestElement = 0; String instruction = null; while (st.nextToken() != StreamTokenizer.TT_EOF) { instruction = st.sval; if (instruction.equalsIgnoreCase("POP")) { try{ popSuc = true; oldestElement = test.remove(); } catch (NoSuchElementException e) { // Failed to pop something. popSuc = false; System.out.println(-1); } if (popSuc) { // Successful to pop something. System.out.println(oldestElement); } } else if (instruction.equalsIgnoreCase("PUSH")){ st.nextToken(); test.add((int)st.nval); } else { throw new IllegalArgumentException(instruction + "is invalid."); } } } } |