NUHMAN.com

🧩 Problem Statement

Implement a first in, first out (FIFO) queue using only two stacks. The queue should support the following operations:

1. push(x): Push element x to the back of the queue.
2. pop(): Removes the element from the front of the queue.
3. peek(): Get the front element.
4. empty(): Returns whether the queue is empty.

You must implement the solution using two stacks.

📘 Example

go

Input:
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]

Output:
[null, null, null, 1, 1, false]

Explanation:
MyQueue myQueue = new MyQueue();
myQueue.push(1);   // queue is: [1]
myQueue.push(2);   // queue is: [1, 2]
myQueue.peek();    // return 1
myQueue.pop();     // return 1, queue is: [2]
myQueue.empty();   // return false

🧠 Approach

We need to implement a queue using two stacks, and we will simulate the FIFO behavior using these two stacks:

1. Two Stacks:

• stack1: This will be used for pushing elements (acting like the enqueue operation).
• stack2: This will be used for popping elements (acting like the dequeue operation).

1. Push Operation (push(x)):

• Simply push the element x into stack1.

1. Pop Operation (pop()):

• If stack2 is empty, we move all elements from stack1 to stack2. This ensures that the oldest elements in stack1 are transferred to stack2 in the correct order for dequeueing.
• If stack2 is not empty, we can simply pop the top element from stack2.

1. Peek Operation (peek()):

• If stack2 is empty, we move elements from stack1 to stack2 (as explained for pop).
• Then, we return the top element from stack2.

1. Empty Operation (empty()):

• The queue is empty if both stack1 and stack2 are empty.

✅ Go Implementation

go

package main

import "fmt"

// Implement a Queue using Two Stacks
type MyQueue struct {
    stack1 []int  // Stack used for pushing elements
    stack2 []int  // Stack used for popping elements
}

// Constructor to initialize the MyQueue object
func Constructor() MyQueue {
    return MyQueue{}
}

// Push element x to the back of the queue
func (q *MyQueue) Push(x int) {
    q.stack1 = append(q.stack1, x)
}

// Pop the element from the front of the queue
func (q *MyQueue) Pop() int {
    // If stack2 is empty, transfer elements from stack1 to stack2
    if len(q.stack2) == 0 {
        for len(q.stack1) > 0 {
            q.stack2 = append(q.stack2, q.stack1[len(q.stack1)-1])
            q.stack1 = q.stack1[:len(q.stack1)-1]
        }
    }
    // Pop the front element from stack2
    res := q.stack2[len(q.stack2)-1]
    q.stack2 = q.stack2[:len(q.stack2)-1]
    return res
}

// Get the front element of the queue
func (q *MyQueue) Peek() int {
    if len(q.stack2) == 0 {
        for len(q.stack1) > 0 {
            q.stack2 = append(q.stack2, q.stack1[len(q.stack1)-1])
            q.stack1 = q.stack1[:len(q.stack1)-1]
        }
    }
    return q.stack2[len(q.stack2)-1]
}

// Return whether the queue is empty
func (q *MyQueue) Empty() bool {
    return len(q.stack1) == 0 && len(q.stack2) == 0
}

// Test the MyQueue implementation
func main() {
    myQueue := Constructor()
    
    // Example sequence of operations
    myQueue.Push(1)         // Queue: [1]
    myQueue.Push(2)         // Queue: [1, 2]
    fmt.Println(myQueue.Peek()) // Output: 1 (Front element)
    fmt.Println(myQueue.Pop())  // Output: 1 (Element removed)
    fmt.Println(myQueue.Empty()) // Output: false (Queue is not empty)
}

📦 Example Usage

go

func main() {
    myQueue := Constructor()

    // Pushing elements to the queue
    myQueue.Push(1)         // Queue: [1]
    myQueue.Push(2)         // Queue: [1, 2]

    // Peek operation - should return 1 (front of the queue)
    fmt.Println(myQueue.Peek()) // Output: 1

    // Pop operation - should return 1 (front element removed)
    fmt.Println(myQueue.Pop())  // Output: 1

    // Empty operation - should return false (queue is not empty)
    fmt.Println(myQueue.Empty()) // Output: false
}

⏱️ Time & Space Complexity

• Time Complexity:
• Push operation (push(x)): O(1) since we are just appending to stack1.
• Pop operation (pop()): O(n) in the worst case when all elements are moved from stack1 to stack2.
• Peek operation (peek()): O(n) in the worst case when all elements are moved from stack1 to stack2.
• Empty operation (empty()): O(1) because we just check if both stacks are empty.
• Space Complexity:
• O(n) where n is the number of elements in the queue, since we're using two stacks to hold the elements.

This solution efficiently simulates a queue using two stacks, handling the operations in a straightforward manner.