Difficulty

Easy

Language

Python

URL

https://leetcode.com/problems/implement-stack-using-queues/

Solution 1 - Brute Force

Iterate through every pair of numbers using two nested loops. For each pair, check if they sum to the target. Return the indices when a match is found.

TimeComplexity: O(n^2)

SpaceComplexity: O(1)

Solution 2 - Brute Force using `enumerate()`

Same brute force logic, but uses Python's enumerate() for cleaner index tracking instead of range(len(...)).

TimeComplexity: O(n^2)

SpaceComplexity: O(1)

Solution 1 - Single Queue (Push Costly)

Implement a stack using a single queue. On each push, add the new element to the back of the queue, then rotate all previous elements behind it by popping from the front and pushing to the back. This ensures the most recently pushed element is always at the front, making pop and top O(1).

TimeComplexity: O(n) \text{ push, } O(1) \text{ pop}

SpaceComplexity: O(n)

Solution 2 - Two Queues (Push Costly)

Use two queues. On each push, add the new element to the empty auxiliary queue, then move all elements from the main queue into the auxiliary queue. Finally, swap the two queues. This keeps the most recent element at the front of the main queue.

TimeComplexity: O(n) \text{ push, } O(1) \text{ pop}

SpaceComplexity: O(n)

Difficulty

Easy

Language

Python

URL

https://leetcode.com/problems/implement-stack-using-queues/

Solution 1 - Brute Force

Iterate through every pair of numbers using two nested loops. For each pair, check if they sum to the target. Return the indices when a match is found.

TimeComplexity: O(n^2)

SpaceComplexity: O(1)

""" 0001.1 - Solution 1 - Brute Force Approach """

#####################################################################################
# Imports
#####################################################################################
from typing import List

#####################################################################################
# Classes
#####################################################################################
class Solution:
    """Solution Class"""

    def twoSum(self, nums: List[int], target: int) -> List[int]:
        """Two Sum Function"""
        for i in range(len(nums)):
            for j in range(i + 1, len(nums)):
                if nums[i] + nums[j] == target:
                    return [i, j]


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    print(Solution().twoSum([3, 3], 6))
    print(Solution().twoSum([3, 2, 4], 6))
    print(Solution().twoSum([2, 7, 11, 15], 9))


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()

Solution 2 - Brute Force using `enumerate()`

Same brute force logic, but uses Python's enumerate() for cleaner index tracking instead of range(len(...)).

TimeComplexity: O(n^2)

SpaceComplexity: O(1)

""" 0001.1 - Solution 1 - Using Enumerate """

#####################################################################################
# Imports
#####################################################################################
from typing import List

#####################################################################################
# Classes
#####################################################################################
class Solution:
    """Solution Class"""

    def twoSum(self, nums: List[int], target: int) -> List[int]:
        """Two Sum Function"""
        for key1, num1 in enumerate(nums):
            for key2, num2 in enumerate(nums[key1 + 1 :], key1 + 1):
	              # enumerate(iterable, start=1) -> start value determines starting index
                # Printing value and key will output 1 i , 2 j, 3 k, 4 l 
                if num1 + num2 == target:
                    return [key1, key2]


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    print(Solution().twoSum([3, 3], 6))
    print(Solution().twoSum([3, 2, 4], 6))
    print(Solution().twoSum([2, 7, 11, 15], 9))


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()

Solution 1 - Single Queue (Push Costly)

TimeComplexity: O(n) \text{ push, } O(1) \text{ pop}

SpaceComplexity: O(n)

""" 0225.1 - Implement Stack using Queues - Solution 1 - Single Queue (Push Costly) """

#####################################################################################
# Imports
#####################################################################################
from collections import deque

#####################################################################################
# Classes
#####################################################################################
class MyStack:
    """Stack implementation using a single queue."""

    def __init__(self):
        self.q = deque()

    def push(self, x: int) -> None:
        """Push element x onto stack."""
        self.q.append(x)
        # Rotate all elements before x to the back
        for _ in range(len(self.q) - 1):
            self.q.append(self.q.popleft())

    def pop(self) -> int:
        """Remove and return the top element."""
        return self.q.popleft()

    def top(self) -> int:
        """Return the top element without removing it."""
        return self.q[0]

    def empty(self) -> bool:
        """Return True if the stack is empty."""
        return len(self.q) == 0


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    stack = MyStack()
    stack.push(1)
    stack.push(2)
    print(stack.top())   # 2
    print(stack.pop())   # 2
    print(stack.empty()) # False


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()

Solution 2 - Two Queues (Push Costly)

TimeComplexity: O(n) \text{ push, } O(1) \text{ pop}

SpaceComplexity: O(n)

""" 0225.2 - Implement Stack using Queues - Solution 2 - Two Queues (Push Costly) """

#####################################################################################
# Imports
#####################################################################################
from collections import deque

#####################################################################################
# Classes
#####################################################################################
class MyStack:
    """Stack implementation using two queues."""

    def __init__(self):
        self.q1 = deque()
        self.q2 = deque()

    def push(self, x: int) -> None:
        """Push element x onto stack."""
        self.q2.append(x)
        # Move all elements from q1 to q2
        while self.q1:
            self.q2.append(self.q1.popleft())
        # Swap q1 and q2
        self.q1, self.q2 = self.q2, self.q1

    def pop(self) -> int:
        """Remove and return the top element."""
        return self.q1.popleft()

    def top(self) -> int:
        """Return the top element without removing it."""
        return self.q1[0]

    def empty(self) -> bool:
        """Return True if the stack is empty."""
        return len(self.q1) == 0


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    stack = MyStack()
    stack.push(1)
    stack.push(2)
    print(stack.top())   # 2
    print(stack.pop())   # 2
    print(stack.empty()) # False


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()

0225 - Implement Stack using Queues

Solution 1 - Brute Force

Solution 2 - Brute Force using `enumerate()`

Solution 1 - Single Queue (Push Costly)

Solution 2 - Two Queues (Push Costly)

0225 - Implement Stack using Queues

Solution 1 - Brute Force

Solution 2 - Brute Force using `enumerate()`

Solution 1 - Single Queue (Push Costly)

Solution 2 - Two Queues (Push Costly)

0225 - Implement Stack using Queues

Solution 1 - Brute Force

Solution 2 - Brute Force using enumerate()

Solution 1 - Single Queue (Push Costly)

Solution 2 - Two Queues (Push Costly)

0225 - Implement Stack using Queues

Solution 1 - Brute Force

Solution 2 - Brute Force using enumerate()

Solution 1 - Single Queue (Push Costly)

Solution 2 - Two Queues (Push Costly)

Solution 2 - Brute Force using `enumerate()`

Solution 2 - Brute Force using `enumerate()`