NUHMAN.com

🧩 Problem Statement

Implement a stack using two queues.

• You must implement MyStack class:
• void push(int x): Pushes element x onto the stack.
• int pop(): Removes the element on the top of the stack.
• int top(): Gets the top element of the stack.
• boolean empty(): Returns whether the stack is empty.

📘 Example

go

Input:
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]

Output:
[null, null, null, 2, 2, false]

📝 Explanation:

1. MyStack is instantiated.
2. push(1) pushes 1 onto the stack.
3. push(2) pushes 2 onto the stack.
4. top() returns 2, the top element of the stack.
5. pop() removes and returns the top element, which is 2.
6. empty() returns false since there is still one element (1) in the stack.

🧠 Approach

We need to implement a stack using two queues. The key operations for a stack are push, pop, and top.

Plan:

To simulate a stack with two queues:

1. Push operation (push(x)):

• Add element to queue1.
• The new element must always be in the front of the queue.

1. Pop operation (pop()):

• To remove the top element, we move all but one element from queue1 to queue2, leaving the last element as the top of the stack.
• Then, we swap queue1 and queue2, so queue1 always holds the current elements.

1. Top operation (top()):

• This is similar to pop but without removing the top element.

1. Empty operation (empty()):

• Simply return whether queue1 is empty.

Steps:

1. Use two queues: queue1 and queue2.
2. On push(x), enqueue x to queue1.
3. On pop(), transfer elements from queue1 to queue2 until only one element is left in queue1, then dequeue and return it.
4. For top(), perform the same operation as pop() but without removing the element.
5. For empty(), check if queue1 is empty.

✅ Go Implementation

go

package main

import "fmt"

type MyStack struct {
	queue1 []int // main queue to hold the stack elements
	queue2 []int // auxiliary queue to help with pop operation
}

// Constructor to initialize the stack
func Constructor() MyStack {
	return MyStack{}
}

// Push an element onto the stack
func (this *MyStack) Push(x int) {
	this.queue1 = append(this.queue1, x)
}

// Pop the top element from the stack
func (this *MyStack) Pop() int {
	// Transfer all elements except the last one to queue2
	for len(this.queue1) > 1 {
		this.queue2 = append(this.queue2, this.queue1[0])
		this.queue1 = this.queue1[1:]
	}
	// The last element in queue1 is the top of the stack
	topElement := this.queue1[0]
	// Clear queue1 and swap with queue2
	this.queue1, this.queue2 = this.queue2, this.queue1
	this.queue2 = nil // Reset queue2
	return topElement
}

// Get the top element of the stack
func (this *MyStack) Top() int {
	// Transfer all elements except the last one to queue2
	for len(this.queue1) > 1 {
		this.queue2 = append(this.queue2, this.queue1[0])
		this.queue1 = this.queue1[1:]
	}
	// The last element in queue1 is the top of the stack
	topElement := this.queue1[0]
	// Move the element to queue2 to keep queue1 unchanged
	this.queue2 = append(this.queue2, topElement)
	// Swap back the queues
	this.queue1, this.queue2 = this.queue2, this.queue1
	this.queue2 = nil // Reset queue2
	return topElement
}

// Check if the stack is empty
func (this *MyStack) Empty() bool {
	return len(this.queue1) == 0
}

func main() {
	// Example usage
	stack := Constructor()
	stack.Push(1)
	stack.Push(2)
	fmt.Println(stack.Top())   // Output: 2
	fmt.Println(stack.Pop())   // Output: 2
	fmt.Println(stack.Empty()) // Output: false
}

📦 Example Usage

go

func main() {
	// Instantiate the stack
	stack := Constructor()
	// Push elements onto the stack
	stack.Push(1)
	stack.Push(2)
	// Get the top element
	fmt.Println(stack.Top())   // Output: 2
	// Pop the top element
	fmt.Println(stack.Pop())   // Output: 2
	// Check if the stack is empty
	fmt.Println(stack.Empty()) // Output: false
}

⏱️ Time & Space Complexity

• Time Complexity:
• Push: O(1), as appending to the end of the queue takes constant time.
• Pop: O(n), where n is the number of elements in the stack. We need to move all elements from queue1 to queue2, which takes linear time.
• Top: O(n), similar to pop but doesn't remove the element, only retrieves it.
• Empty: O(1), checking if queue1 is empty takes constant time.
• Space Complexity:
• O(n), where n is the number of elements in the stack. We use two queues that together store all elements.

This approach efficiently simulates stack operations using two queues, adhering to the constraints and expected performance.