SAMSUNG 49-Inch Odyssey G9

Because earth is not flat

Description

Implement a queue using two stacks. The queue should support the standard operations of push (to add an element to the end), pop (to remove the element from the front), peek (to retrieve the element at the front without removing it), and empty (to check if the queue is empty). This implementation leverages stack operations to simulate the behavior of a queue.

Intuition

A queue follows the First-In-First-Out (FIFO) principle, while a stack follows the Last-In-First-Out (LIFO) principle. By using two stacks, we can simulate the queue operations. One stack (stack1) is used to store the elements in the order they are pushed. When an element needs to be popped from the queue, the elements in stack1 can be transferred to stack2 (if using a two-stack approach) to reverse the order, making the oldest element accessible.

Approach

1. Push Operation:

   • The push operation simply adds the element to the end of the stack (stack1).

2. Pop Operation:

   • For the pop operation, we retrieve and remove the first element of the stack. Since the first element in the stack corresponds to the front of the queue, this operation simulates queue behavior.

3. Peek Operation:

   • The peek operation retrieves the front element of the stack without removing it. This allows us to view the next element to be dequeued.

4. Empty Operation:

   • The empty operation checks if the stack is empty, which corresponds to the queue being empty.

Edge Cases:

• The queue should handle cases where it is empty, ensuring that operations like pop and peek do not cause errors when called on an empty queue.

Complexity

Time Complexity:

• push: O(1) - Inserting an element into the stack is a constant-time operation.
• pop: O(1) - Removing an element from the front of the stack is also a constant-time operation in this implementation.
• peek: O(1) - Accessing the front element of the stack is a constant-time operation.
• empty: O(1) - Checking if the stack is empty is a constant-time operation.

Space Complexity:

O(n), where n is the number of elements in the queue. This is due to the space required to store elements in stack1.

Code

C++

class MyQueue {
private:
    vector<int> stack1;

public:
    MyQueue() {
        // Initialize the queue
    }

    void push(int x) {
        stack1.push_back(x);
    }

    int pop() {
        int popNumber = stack1[0];
        stack1.erase(stack1.begin());
        return popNumber;
    }

    int peek() {
        return stack1[0];
    }

    bool empty() {
        return stack1.empty();
    }
};

Python

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

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

    def pop(self) -> int:
        pop_number = self.stack1[0]
        self.stack1.pop(0)
        return pop_number

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

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

Java

class MyQueue {
    private Queue<Integer> stack1;

    public MyQueue() {
        stack1 = new LinkedList<>();
    }

    public void push(int x) {
        stack1.add(x);
    }

    public int pop() {
        return stack1.poll(); // Retrieves and removes the head of the queue
    }

    public int peek() {
        return stack1.peek(); // Retrieves, but does not remove, the head of the queue
    }

    public boolean empty() {
        return stack1.isEmpty();
    }
}

JavaScript

var MyQueue = function () {
    this.stack1 = []
    this.stack2 = []
};

/** 
 * @param {number} x
 * @return {void}
 */
MyQueue.prototype.push = function (x) {
    this.stack1.push(x)

};

/**
 * @return {number}
 */
MyQueue.prototype.pop = function () {
    let popNumber = this.stack1[0]
    this.stack1.shift()
    return popNumber
};

/**
 * @return {number}
 */
MyQueue.prototype.peek = function () {
    this.stack1[0]
    return this.stack1[0]
};

/**
 * @return {boolean}
 */
MyQueue.prototype.empty = function () {
    if (this.stack1.length === 0) return true
    return false
};