Implement Stack using Queue

Stack / Queues Implementation Easy

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

Implement the QueueStack class:

void push(int x): Pushes element x onto the stack.

int pop(): Removes and returns the top element of the stack.

int top(): Returns the top element of the stack without removing it.

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

Examples:

Input:

["QueueStack", "push", "push", "pop", "top", "isEmpty"]

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

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

Explanation:

QueueStack stack = new QueueStack();

stack.push(4);

stack.push(8);

stack.pop(); // returns 8

stack.top(); // returns 4

stack.isEmpty(); // returns false

Input:

["QueueStack", "isEmpty"]

[[]]

Output:[null, true]

Explanation:

QueueStack stack = new QueueStack();

stack.isEmpty(); // returns true

Input:

["QueueStack", "push", "pop", "isEmpty"]

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

Constraints

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

Hints

To implement a stack using a single queue, we need to reverse the order of elements within the queue after each push() operation.
After inserting a new element, rotate the queue so that the newest element moves to the front.

Company Tags

Bungie Goldman Sachs Alibaba Instacart Robinhood Zoho Siemens Healthineers Mastercard Activision Blizzard Pinterest HCL Technologies Freshworks Bloomberg Roche ARM Reddit MongoDB Flipkart Qualcomm Square Western Digital Electronic Arts Johnson & Johnson Lyft Cloudflare Google Microsoft Amazon Meta Apple Netflix Adobe TCS Cognizant Accenture Infosys Capgemini Wipro

Intuition:

Imagine you have a box (queue) that can only be accessed from one side. You want to use this box to simulate a stack, where the last item you put in is the first one you take out. This is like stacking plates: you put a plate on top and when you need a plate, you take the top one. Here's how we can achieve this with our box:

Pushing Items: When you want to push an item onto the stack, you put it in the box (queue) and then move all the other items in the box (queue) to the back of the new item. This way, the new item is always at the front, simulating the top of the stack. For example, if the box currently has plates A, B, C, and you want to add D, you put D in the box and then rearrange so that D is at the front followed by A, B, C.

Popping Items: To pop an item, you simply take out the item at the front of the box (queue). This is like taking the top plate off the stack. In our example, popping would remove D, leaving A, B, C in the box.

Top Item: To see the top item without removing it, you look at the item at the front of the box (queue). In our example, peeking would show D.

Checking if Stack is Empty: To check if the stack is empty, you just check if the box (queue) is empty.

Approach:

Data Structure Used: A single queue will be used to store the elements.
Push(x): Insert the element x into the queue. Rearrange the elements in the queue to maintain the stack order by:
- Running a loop that iterates size() - 1 times, where size() is the current number of elements in the queue.
- In each iteration, remove the front element and add it back to the rear of the queue. This ensures that the most recently added element is always at the front of the queue.
Pop(): Remove and return the front element of the queue, which corresponds to the top of the stack.
isEmpty(): Return true if the queue is empty, and false otherwise.

Dry Run:

Solution:

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

// Stack implementation using Queue
class QueueStack {
    // Queue
    queue<int> q;

public:
    // Method to push element in the stack
    void push(int x) {
        // Get size 
        int s = q.size(); 
        // Add element
        q.push(x); 

        // Move elements before new element to back
        for (int i = 0; i < s; i++) {
            q.push(q.front()); 
            q.pop(); 
        }
    }

    // Method to pop element from stack
    int pop() {
        // Get front element 
        int n = q.front(); 
        // Remove front element
        q.pop(); 
        // Return removed element
        return n; 
    }

    // Method to return the top of stack
    int top() {
        // Return front element
        return q.front(); 
    }

    // Method to check if the stack is empty
    bool isEmpty() {
        return q.empty(); 
    }
};

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

    for (int i = 0; i < commands.size(); ++i) {
        if (commands[i] == "push") {
            st.push(inputs[i][0]);
            cout << "null ";
        } else if (commands[i] == "pop") {
            cout << st.pop() << " ";
        } else if (commands[i] == "top") {
            cout << st.top() << " ";
        } else if (commands[i] == "isEmpty") {
            cout << (st.isEmpty() ? "true" : "false") << " ";
        } else if (commands[i] == "QueueStack") {
            cout << "null ";
        }
    }

    return 0;
}
import java.util.*;

// Stack implementation using Queue
class QueueStack {
    // Queue
    Queue<Integer> q = new LinkedList<>();

    // Method to push element in the stack
    public void push(int x) {
        // Get size
        int s = q.size();
        // Add element
        q.add(x);

        // Move elements before new element to back
        for (int i = 0; i < s; i++) {
            q.add(q.poll());
        }
    }

    // Method to pop element from stack
    public int pop() {
        // Get front element
        int n = q.peek();
        // Remove front element
        q.poll();
        // Return removed element
        return n;
    }

    // Method to return the top of stack
    public int top() {
        // Return front element
        return q.peek();
    }

    // Method to check if the stack is empty
    public boolean isEmpty() {
        return q.isEmpty();
    }
}

// Main class
class Main {
    public static void main(String[] args) {
        QueueStack st = new QueueStack();
        
        // Array of commands
        String[] commands = {"QueueStack", "push", "push", 
                             "pop", "top", "isEmpty"};
        int[][] inputs = {{}, {4}, {8}, {}, {}, {}};

        for (int i = 0; i < commands.length; ++i) {
            switch (commands[i]) {
                case "push":
                    st.push(inputs[i][0]);
                    System.out.print("null ");
                    break;
                case "pop":
                    System.out.print(st.pop() + " ");
                    break;
                case "top":
                    System.out.print(st.top() + " ");
                    break;
                case "isEmpty":
                    System.out.print(st.isEmpty() ? "true " : "false ");
                    break;
                case "QueueStack":
                    System.out.print("null ");
                    break;
            }
        }
    }
}
from queue import Queue

# Stack implementation using Queue
class QueueStack:
    def __init__(self):
        # Queue
        self.q = Queue()

    # Method to push element in the stack
    def push(self, x):
        # Get size
        s = self.q.qsize()
        # Add element
        self.q.put(x)

        # Move elements before new element to back
        for _ in range(s):
            self.q.put(self.q.get())

    # Method to pop element from stack
    def pop(self):
        # Get front element
        n = self.q.queue[0]
        # Remove front element
        self.q.get()
        # Return removed element
        return n

    # Method to return the top of stack
    def top(self):
        # Return front element
        return self.q.queue[0]

    # Method to check if the stack is empty
    def isEmpty(self):
        return self.q.empty()

if __name__ == "__main__":
    st = QueueStack()

    # List of commands
    commands = ["QueueStack", "push", "push", "pop", "top", "isEmpty"]
    inputs = [[], [4], [8], [], [], []]

    for i in range(len(commands)):
        if commands[i] == "push":
            st.push(inputs[i][0])
            print("null", end=" ")
        elif commands[i] == "pop":
            print(st.pop(), end=" ")
        elif commands[i] == "top":
            print(st.top(), end=" ")
        elif commands[i] == "isEmpty":
            print("true" if st.isEmpty() else "false", end=" ")
        elif commands[i] == "QueueStack":
            print("null", end=" ")
// Stack implementation using Queue
class QueueStack {
    constructor() {
        // Queue
        this.q = [];
    }

    // Method to push element in the stack
    push(x) {
        // Get size
        let s = this.q.length;
        // Add element
        this.q.push(x);

        // Move elements before new element to back
        for (let i = 0; i < s; i++) {
            this.q.push(this.q.shift());
        }
    }

    // Method to pop element from stack
    pop() {
        // Get front element
        let n = this.q[0];
        // Remove front element
        this.q.shift();
        // Return removed element
        return n;
    }

    // Method to return the top of stack
    top() {
        // Return front element
        return this.q[0];
    }

    // Method to check if the stack is empty
    isEmpty() {
        return this.q.length === 0;
    }
}

const st = new QueueStack();

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

for (let i = 0; i < commands.length; ++i) {
    switch (commands[i]) {
        case "push":
            st.push(inputs[i][0]);
            console.log("null ");
            break;
        case "pop":
            console.log(st.pop() + " ");
            break;
        case "top":
            console.log(st.top() + " ");
            break;
        case "isEmpty":
            console.log(st.isEmpty() ? "true " : "false ");
            break;
        case "QueueStack":
            console.log("null ");
            break;
    }
}

Complexity Analysis:

Time Complexity:

Push operation: O(n) (where n is the number of elements in the queue at that time) because every time an element is pushed, all the elements in the queue are popped from front and pushed in the back again.
Pop operation: O(1) as constant operations are performed.
Top operation: O(1) as constant operations are performed.
IsEmpty operation: O(1) as constant operations are performed.

Space Complexity: O(k) for storing k elements in the queue.

Code

Problem List

Implement Stack using Queue

Examples:

Constraints

Hints

Company Tags

Editorial

Intuition:

Approach:

Dry Run:

Solution:

Complexity Analysis:

Frequently Occurring Doubts

Interview Followup Questions

Notes

Code