Implement Queue using Stack

Stack / Queues Implementation Easy

Implement a First-In-First-Out (FIFO) queue using a single stack. The implemented queue should support the following operations: push, pop, peek, and isEmpty.

Implement the StackQueue class:

void push(int x): Adds element x to the end of the queue.

int pop(): Removes and returns the front element of the queue.

int peek(): Returns the front element of the queue without removing it.

boolean isEmpty(): Returns true if the queue is empty, false otherwise.

Examples:

Input:

["StackQueue", "push", "push", "pop", "peek", "isEmpty"]

[[], [4], [8], [], [], []]

Output:[null, null, null, 4, 8, false]

Explanation:

StackQueue queue = new StackQueue();

queue.push(4);

queue.push(8);

queue.pop(); // returns 4

queue.peek(); // returns 8

queue.isEmpty(); // returns false

Input:

["StackQueue", "isEmpty"]

[[]]

Output: [null, true]

Explanation:

StackQueue queue = new StackQueue();

queue.isEmpty(); // returns true

Input:

["StackQueue", "push", "pop", "isEmpty"]

[[], [6], [], []]

Constraints

1 <= numbers of calls made <= 100
1 <= x <= 100

Hints

To implement a queue using a single stack, we need to reverse the order when dequeuing elements.
"Calling pop() or peek() on an empty queue should raise an appropriate exception. Ensure isEmpty() accurately reflects whether the queue has elements."

Company Tags

GE Healthcare Deloitte eBay Zoho Red Hat Mastercard DoorDash Roblox PayPal Oracle KPMG Dropbox Alibaba HCL Technologies Airbnb Texas Instruments Zomato Chewy IBM Twilio Bain & Company Siemens Healthineers Bungie Roche Splunk Google Microsoft Amazon Meta Apple Netflix Adobe TCS Cognizant Accenture Infosys Capgemini Wipro

Using two Stacks where push operation is O(N)

Real Life Example

To better visualize this problem imagine a line of people waiting to get tickets for a movie. The first person who arrives at the counter is the first one to get the ticket, just like in a queue. Now, if there are two large boxes, one for placing and another for reversing the order of tickets, the first box can be used to collect tickets from people in the order they arrive. When it's time to issue the tickets, they can be transferred to the second box to reverse their order, ensuring the first person to arrive is the first one to get the ticket, simulating the behavior of a queue using stacks.

Intuition

The goal is to implement a queue using stacks, which naturally follow Last In, First Out (LIFO) order. To achieve the First In, First Out (FIFO) order of a queue, the idea is to use two stacks. By pushing elements onto one stack and then transferring them to another stack before popping, the order of elements is reversed twice. This ensures that the first element pushed onto the stack is the first one to be popped, thus mimicking a queue's behavior.

Approach

Use Two Stacks: Maintain two stacks, stack1 and stack2.
Push Operation:
1. Transfer all elements from stack1 to stack2.
2. Add the new element to stack1.
3. Transfer all elements back from stack2 to stack1.
4. This ensures the new element is always at the front for the next pop operation.
Pop Operation: Remove and return the top element from stack1.
Top Operation: Return the top element of stack1 without removing it.
Size Operation: Return the size of stack1.

Dry Run

Solution:

#include <bits/stdc++.h>
using namespace std;

// Queue implementation using stack
class StackQueue {
private:
    stack <int> st1, st2;

public: 
    // Empty Constructor
    StackQueue () {
        
    }
    
    // Method to push elements in the queue
    void push(int x) {
        /* Pop out elements from the first stack 
        and push on top of the second stack */
        while (!st1.empty()) {
            st2.push(st1.top());
            st1.pop();
        }
        
        // Insert the desired element
        st1.push(x);
        
        /* Pop out elements from the second stack 
        and push back on top of the first stack */
        while (!st2.empty()) {
            st1.push(st2.top());
            st2.pop();
        }
    }
    
    // Method to pop element from the queue
    int pop() {
        // Edge case
        if (st1.empty()) {
            cout << "Stack is empty";
            return -1; // Representing empty stack
        }
        
        // Get the top element
        int topElement = st1.top();
        st1.pop(); // Perform the pop operation
        
        return topElement; // Return the popped value
    }
    
    // Method to get the front element from the queue 
    int peek() {
        // Edge case
        if (st1.empty()) {
            cout << "Stack is empty";
            return -1; // Representing empty stack
        }
        
        // Return the top element
        return st1.top();
    }
    
    // Method to find whether the queue is empty
    bool isEmpty() {
        return st1.empty();
    }
};

int main() {
    StackQueue q;
    
    // List of commands
    vector<string> commands = {"StackQueue", "push", "push", 
                               "pop", "peek", "isEmpty"};
    // List of inputs
    vector<vector<int>> inputs = {{}, {4}, {8}, {}, {}, {}};

    for (int i = 0; i < commands.size(); ++i) {
        if (commands[i] == "push") {
            q.push(inputs[i][0]);
            cout << "null ";
        } else if (commands[i] == "pop") {
            cout << q.pop() << " ";
        } else if (commands[i] == "peek") {
            cout << q.peek() << " ";
        } else if (commands[i] == "isEmpty") {
            cout << (q.isEmpty() ? "true" : "false") << " ";
        } else if (commands[i] == "StackQueue") {
            cout << "null ";
        }
    }
    
    return 0;
}
import java.util.*;

class StackQueue {
    private Stack<Integer> st1, st2;

    // Constructor
    public StackQueue() {
        st1 = new Stack<>();
        st2 = new Stack<>();
    }

    // Method to push elements in the queue
    public void push(int x) {
        /* Pop out elements from the first stack 
        and push on top of the second stack */
        while (!st1.isEmpty()) {
            st2.push(st1.pop());
        }

        // Insert the desired element
        st1.push(x);

        /* Pop out elements from the second stack 
        and push back on top of the first stack */
        while (!st2.isEmpty()) {
            st1.push(st2.pop());
        }
    }

    // Method to pop element from the queue
    public int pop() {
        // Edge case
        if (st1.isEmpty()) {
            System.out.println("Stack is empty");
            return -1; // Representing empty stack
        }

        // Get the top element
        int topElement = st1.pop(); // Perform the pop operation

        return topElement; // Return the popped value
    }

    // Method to get the front element from the queue 
    public int peek() {
        // Edge case
        if (st1.isEmpty()) {
            System.out.println("Stack is empty");
            return -1; // Representing empty stack
        }

        // Return the top element
        return st1.peek();
    }

    // Method to find whether the queue is empty
    public boolean isEmpty() {
        return st1.isEmpty();
    }
}

class Main {
    public static void main(String[] args) {
        StackQueue q = new StackQueue();

        // List of commands
        String[] commands = {"StackQueue", "push", "push", 
                             "pop", "peek", "isEmpty"};
        // List of inputs
        int[][] inputs = {{}, {4}, {8}, {}, {}, {}};

        for (int i = 0; i < commands.length; i++) {
            if (commands[i].equals("push")) {
                q.push(inputs[i][0]);
                System.out.print("null ");
            } else if (commands[i].equals("pop")) {
                System.out.print(q.pop() + " ");
            } else if (commands[i].equals("peek")) {
                System.out.print(q.peek() + " ");
            } else if (commands[i].equals("isEmpty")) {
                System.out.print((q.isEmpty() ? "true" : "false") + " ");
            } else if (commands[i].equals("StackQueue")) {
                System.out.print("null ");
            }
        }
    }
}
class StackQueue:
    def __init__(self):
        # Constructor
        self.st1 = []
        self.st2 = []

    # Method to push elements in the queue
    def push(self, x):
        '''Pop out elements from the first stack 
        and push on top of the second stack'''
        while self.st1:
            self.st2.append(self.st1.pop())

        # Insert the desired element
        self.st1.append(x)

        '''Pop out elements from the second stack 
        and push back on top of the first stack'''
        while self.st2:
            self.st1.append(self.st2.pop())

    # Method to pop element from the queue
    def pop(self):
        # Edge case
        if not self.st1:
            print("Stack is empty")
            return -1  # Representing empty stack

        # Get the top element
        top_element = self.st1.pop()  # Perform the pop operation
        return top_element  # Return the popped value

    # Method to get the front element from the queue
    def peek(self):
        # Edge case
        if not self.st1:
            print("Stack is empty")
            return -1  # Representing empty stack

        # Return the top element
        return self.st1[-1]

    # Method to find whether the queue is empty
    def is_empty(self):
        return not self.st1

if __name__ == "__main__":
    q = StackQueue()

    # List of commands
    commands = ["StackQueue", "push", "push", "pop", "peek", "isEmpty"]
    # List of inputs
    inputs = [[], [4], [8], [], [], []]

    for i in range(len(commands)):
        if commands[i] == "push":
            q.push(inputs[i][0])
            print("null", end=" ")
        elif commands[i] == "pop":
            print(q.pop(), end=" ")
        elif commands[i] == "peek":
            print(q.peek(), end=" ")
        elif commands[i] == "isEmpty":
            print("true" if q.is_empty() else "false", end=" ")
        elif commands[i] == "StackQueue":
            print("null", end=" ")
class StackQueue {
    constructor() {
        // Constructor
        this.st1 = [];
        this.st2 = [];
    }

    // Method to push elements in the queue
    push(x) {
        /* Pop out elements from the first stack 
        and push on top of the second stack */
        while (this.st1.length) {
            this.st2.push(this.st1.pop());
        }

        // Insert the desired element
        this.st1.push(x);

        /* Pop out elements from the second stack 
        and push back on top of the first stack */
        while (this.st2.length) {
            this.st1.push(this.st2.pop());
        }
    }

    // Method to pop element from the queue
    pop() {
        // Edge case
        if (!this.st1.length) {
            console.log("Stack is empty");
            return -1; // Representing empty stack
        }

        // Get the top element
        return this.st1.pop(); // Perform the pop operation
    }

    // Method to get the front element from the queue 
    peek() {
        // Edge case
        if (!this.st1.length) {
            console.log("Stack is empty");
            return -1; // Representing empty stack
        }

        // Return the top element
        return this.st1[this.st1.length - 1];
    }

    // Method to find whether the queue is empty
    isEmpty() {
        return this.st1.length === 0;
    }
}

const q = new StackQueue();

// List of commands
const commands = ["StackQueue", "push", "push", "pop", "peek", "isEmpty"];
// List of inputs
const inputs = [[], [4], [8], [], [], []];

for (let i = 0; i < commands.length; i++) {
    if (commands[i] === "push") {
        q.push(inputs[i][0]);
        console.log("null");
    } else if (commands[i] === "pop") {
        console.log(q.pop());
    } else if (commands[i] === "peek") {
        console.log(q.peek());
    } else if (commands[i] === "isEmpty") {
        console.log(q.isEmpty() ? "true" : "false");
    } else if (commands[i] === "StackQueue") {
        console.log("null");
    }
}

Complexity Analysis:

Time Complexity: O(N) where N is the number of elements. Space Complexity: O(2N) because, in the worst case, both the input and output stacks can each hold up to N elements, totalling 2N elements. Here N is the size of the stack.