Question Name: Simulate Stack With Two Queues
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 94 95 96 97 98 99 | /** * Filename : StackWithTwoQueues.java * Dependency: None * Author : Sheng Yu (codesays.com) * Create at : 2014-08-03 * 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.Queue; import java.util.concurrent.LinkedBlockingQueue; /** * @author Sheng Yu (codesays.com) * @param <T>: the type of dealing data. */ class Stack<T> { // main queue always stores the elements. // swap is used in pop() function to hold the elements temporarily. private Queue<T> main = new LinkedBlockingQueue<T>(); private Queue<T> swap = new LinkedBlockingQueue<T>(); // Used in pop() function to exchange he main and swap queues. private Queue<T> temp = null; /** * @param item: to push into the stack. */ public void push(T item) { main.add(item); } /** * @return T: remove and return the most recent element in the stack. * @throws NoSuchElementException: pop when queue is empty. */ public T pop() throws NoSuchElementException { T result = null; // swap is always empty at the beginning of popping. if (main.size() == 0) { throw new NoSuchElementException("Queue is empty"); } // Move all data in main queue to swap, except the most recent one. while (main.size() > 1) { swap.add(main.remove()); } // Get the most recent element. result = main.remove(); // Exchange main and swap queue, so that we always push new data into // main queue. temp = main; main = swap; swap = temp; return result; } } public class StackWithTwoQueues { /** * Stub for test * @param args * @throws IOException * @throws NoSuchElementException * @throws IllegalArgumentException */ public static void main(String[] args) throws IOException, NoSuchElementException, IllegalArgumentException { StreamTokenizer st = new StreamTokenizer(new BufferedReader( new InputStreamReader(System.in))); Stack<Integer> test = new Stack<Integer>(); boolean popSuc = true; Integer res = 0; String instruction = null; while (st.nextToken() != StreamTokenizer.TT_EOF) { instruction = st.sval; if (instruction.equalsIgnoreCase("POP")) { try{ popSuc = true; res = test.pop(); } catch (NoSuchElementException e) { // Failed to pop something. popSuc = false; System.out.println(-1); } if (popSuc) { // Successful to pop something. System.out.println(res); } } else if (instruction.equalsIgnoreCase("PUSH")){ st.nextToken(); test.push((int)st.nval); } else { throw new IllegalArgumentException(instruction + "is invalid."); } } } } |
What’s the question for this?
As the title, Simulate A Stack With Two Queues.
Oh, right! How is it marked? Is what you did in Main() required as part of the question, or is this just your test cases?
Yes, Stack class is the implementation. And the main() function is only for test.
Oh, phew! It’s pretty easy then! 😀
& Thanks for the walkthrough 🙂
My great pleasure! Enjoy coding!