Sponsored
Sponsored
This approach uses two stacks: 'input' for pushing elements and 'output' for popping elements. While pushing, simply add the element to the input stack. For popping or peeking, check if the output stack is empty; if it is, transfer all elements from the input stack to the output stack and then pop or peek from the output stack.
Time Complexity: Each operation (push, pop, peek, empty) has an amortized O(1) complexity. Space Complexity: O(n), where n is the number of elements in the queue.
1#include <stack>
2
3class MyQueue {
4public:
5 std::stack<int> input, output;
6
7 MyQueue() {}
8
9 void push(int x) {
10 input.push(x);
11 }
12
13 int pop() {
14 moveInputToOutput();
15 int topElement = output.top();
16 output.pop();
17 return topElement;
18 }
19
20 int peek() {
21 moveInputToOutput();
22 return output.top();
23 }
24
25 bool empty() {
26 return input.empty() && output.empty();
27 }
28
29private:
30 void moveInputToOutput() {
31 if (output.empty()) {
32 while (!input.empty()) {
33 output.push(input.top());
34 input.pop();
35 }
36 }
37 }
38};This C++ solution employs similar logic to the Python solution. It uses two stacks, 'input' and 'output', for enacting queue operations. The method moveInputToOutput transfers elements from the input stack to the output stack when needed, ensuring pop and peek operations function correctly.
This approach is similar to the previous one, but emphasizes minimizing transfers between the stacks by only transferring when absolutely necessary (when the output stack is empty). This optimizes performance in terms of total operations.
Time Complexity: Each operation (push, pop, peek, empty) has an amortized O(1) complexity. Space Complexity: O(n), where n is the number of elements in the queue.
1class MyQueue {
2 constructor()
This JavaScript solution mirrors the logic seen in Java, employing two arrays to act as stacks. The 'input' and 'output' arrays manage queue elements, transferring data between them only when required for accessing the front of the queue.