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.
1class MyQueue:
2 def __init__(self):
3 self.input = []
4 self.output = []
5
6 def push(self, x: int) -> None:
7 self.input.append(x)
8
9 def pop(self) -> int:
10 self.move_input_to_output()
11 return self.output.pop()
12
13 def peek(self) -> int:
14 self.move_input_to_output()
15 return self.output[-1]
16
17 def empty(self) -> bool:
18 return not self.input and not self.output
19
20 def move_input_to_output(self) -> None:
21 if not self.output:
22 while self.input:
23 self.output.append(self.input.pop())The MyQueue class is implemented using two stacks. The 'input' stack holds elements pushed to the queue, and 'output' stack holds elements in the pop/peek order. The move_input_to_output helper method is used to transfer elements from input to output stack when output is empty, ensuring the correct order for queue operations.
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.
1import java.util.Stack;
2
3
Like the other solutions, this Java implementation leverages two stacks but specifically reduces data transfer by only moving elements from input to output when the output stack is empty. This ensures minimal effort when dequeue operations are scaffolded by stacked operations.