Topic describes

// Please use only two stacks to implement the first-in, first-out queue. The queue should support all the operations that queues normally support (push, // pop, peek, empty) : // int pop() removes the element from the beginning of the queue and returns the element // int peek() returns the element at the beginning of the queue // Boolean empty() If the queue is empty, Returns true. Otherwise, return false // // Note: // You can only use standard stack operations -- i.e., only push to Top, peek/pop from top, size, // and is empty are legal. // Your language may not support stacks. You can use a list or a deque to simulate a stack, as long as it's standard stack operation. // // Advanced: // Can you implement a queue with O(1) amortized time per operation? In other words, the total // time complexity of performing n operations is O(n), even though one of the operations may take a long time.Copy the code

Answer key

/** * Your MyQueue object will be instantiated and called as such: * MyQueue obj = new MyQueue(); * obj.push(x); * int param_2 = obj.pop(); * int param_3 = obj.peek(); * boolean param_4 = obj.empty(); */ // this is an example of a queue with two stacks. // We define a stack stack1 for queuing (pushing) and another stack stack2 for queuing (pushing) // as long as the queuing elements must go to Stack1, as long as the queuing elements must go to Stack2. // All the elements in stack1 are removed from the stack and then added to stack2, which is a first-in-first-out sequence. // If you implemented pop and the elements were in stack2, push the elements in stack2, and in turn push the elements out of stack2 and back into Stack1 and back into stack1. // // execution time: 0 ms, beat 100.00% user // memory consumption in all Java commits: Class MyQueue {Stack<Integer> stack1; Stack<Integer> stack2; /** Initialize your data structure here. */ public MyQueue() { this.stack1 = new Stack<>(); this.stack2 = new Stack<>(); } /** Push element x to the back of queue. */ public void push(int x) { if (stack1.isEmpty()) { while (! stack2.isEmpty()) { stack1.push(stack2.pop()); } } stack1.push(x); } /** Removes the element from in front of queue and returns that element. */ public int pop() { if (stack2.isEmpty()) {  while (! stack1.isEmpty()) { stack2.push(stack1.pop()); } } if (! stack2.isEmpty()) return stack2.pop(); return -1; } /** Get the front element. */ public int peek() { if (stack2.isEmpty()) { while (! stack1.isEmpty()) { stack2.push(stack1.pop()); } } if (! stack2.isEmpty()) return stack2.peek(); return -1; } /** Returns whether the queue is empty. */ public boolean empty() { return (stack1.isEmpty() && stack2.isEmpty()); }}Copy the code