Python_100DaysofCode/ImplementQueueUsingStackDay25.py at main · ayushlingayat/Python_100DaysofCode · GitHub

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
#Brute Approach
class MyQueue:
    def __init__(self):
        self.stack = []

    def push(self, x: int) -> None:
        temp = []
        # Reverse stack
        while self.stack:
            temp.append(self.stack.pop())
        self.stack.append(x)
        # Put back elements
        while temp:
            self.stack.append(temp.pop())

    def pop(self) -> int:
        return self.stack.pop()

    def peek(self) -> int:
        return self.stack[-1]

    def empty(self) -> bool:
        return len(self.stack) == 0

# ⏱️ Time & Space Complexity
# push: O(n)
# pop: O(1)
# peek: O(1)
# empty: O(1)
# Space: O(n)


#Better Approach
class MyQueue:
    def __init__(self):
        self.stack1 = []
        self.stack2 = []

    def push(self, x: int) -> None:
        while self.stack1:
            self.stack2.append(self.stack1.pop())
        self.stack1.append(x)
        while self.stack2:
            self.stack1.append(self.stack2.pop())

    def pop(self) -> int:
        return self.stack1.pop()

    def peek(self) -> int:
        return self.stack1[-1]

    def empty(self) -> bool:
        return len(self.stack1) == 0

# ⏱️ Time & Space Complexity
# push: O(n)
# pop: O(1)
# peek: O(1)
# empty: O(1)
# Space: O(n)

#Optimal Approach

class MyQueue:
    def __init__(self):
        self.in_stack = []
        self.out_stack = []

    def push(self, x: int) -> None:
        self.in_stack.append(x)

    def pop(self) -> int:
        if not self.out_stack:
            while self.in_stack:
                self.out_stack.append(self.in_stack.pop())
        return self.out_stack.pop()

    def peek(self) -> int:
        if not self.out_stack:
            while self.in_stack:
                self.out_stack.append(self.in_stack.pop())
        return self.out_stack[-1]

    def empty(self) -> bool:
        return not self.in_stack and not self.out_stack

# Time Complexity:
# push(x) → O(1)
# pop(), peek() → Amortized O(1)
# empty() → O(1)
# Space Complexity: O(n) — for maintaining the two stacks