Problem Statement

A stack is a data structure that follows the Last In, First Out (LIFO) principle, meaning the last element added is the first one to be removed. A queue, on the other hand, follows the First In, First Out (FIFO) principle, where the first element added is the first to be removed. The challenge is to implement a stack using one or two queues, leveraging the operations provided by the std::queue in C++.

Approach to Solving the Problem

There are multiple ways to implement a stack using queues. The most common approaches involve either:

1. Using two queues: This method uses two queues (q1 and q2) to simulate stack behavior.
2. Using a single queue: This method involves using only one queue (q) and manipulating the order of elements to achieve stack behavior.

1️⃣ Method 1: Implementing Stack Using Two Queues

Idea: We use two queues to simulate the push and pop operations of a stack. The idea is to always keep one queue empty and use it as a temporary buffer during the push operation.

Operations:

1. Push Operation:
   • Enqueue the new element into the empty queue (q2).
   • Move all elements from the non-empty queue (q1) to the empty queue (q2).
   • Swap the names of q1 and q2 to keep q1 as the main queue with the elements arranged in LIFO order.
2. Pop Operation:
   • Simply dequeue from the non-empty queue (q1), which has elements arranged in LIFO order.

Code:

#include <iostream>
#include <queue>

class StackUsingTwoQueues {
private:
    std::queue<int> q1, q2;

public:
    // Push element x onto stack
    void push(int x) {
        // Enqueue new element into q2
        q2.push(x);

        // Move all elements from q1 to q2
        while (!q1.empty()) {
            q2.push(q1.front());
            q1.pop();
        }

        // Swap the names of q1 and q2
        std::swap(q1, q2);
    }

    // Removes the element on top of the stack
    void pop() {
        if (!q1.empty()) {
            q1.pop();
        }
    }

    // Get the top element
    int top() {
        if (!q1.empty()) {
            return q1.front();
        }
        return -1; // Or throw an exception for empty stack
    }

    // Return whether the stack is empty
    bool empty() {
        return q1.empty();
    }
};

int main() {
    StackUsingTwoQueues s;
    s.push(1);
    s.push(2);
    s.push(3);
    std::cout << "Top element: " << s.top() << std::endl; // Output: 3
    s.pop();
    std::cout << "Top element after pop: " << s.top() << std::endl; // Output: 2
    return 0;
}

Time Complexity:

• Push Operation: O(n), where `nnn` is the number of elements in the stack. This is because all elements are moved from q1 to q2.
• Pop Operation: O(1)
• Top Operation: O(1)

2️⃣ Method 2: Implementing Stack Using a Single Queue

Idea: By using one queue, we can make the push operation efficient, but the elements are rearranged after each push to simulate the stack’s LIFO behavior.

Operations:

1. Push Operation:
   • Enqueue the new element to the queue.
   • Rotate the queue to move the newly added element to the front, simulating a stack's top position.
2. Pop Operation:
   • Dequeue from the front of the queue, which is the "top" of the stack.

Code:

#include <iostream>
#include <queue>

class StackUsingSingleQueue {
private:
    std::queue<int> q;

public:
    // Push element x onto stack
    void push(int x) {
        // Get the current size of the queue
        int size = q.size();
        
        // Enqueue the new element
        q.push(x);

        // Rotate the queue to move the new element to the front
        for (int i = 0; i < size; i++) {
            q.push(q.front());
            q.pop();
        }
    }

    // Removes the element on top of the stack
    void pop() {
        if (!q.empty()) {
            q.pop();
        }
    }

    // Get the top element
    int top() {
        if (!q.empty()) {
            return q.front();
        }
        return -1; // Or throw an exception for empty stack
    }

    // Return whether the stack is empty
    bool empty() {
        return q.empty();
    }
};

int main() {
    StackUsingSingleQueue s;
    s.push(1);
    s.push(2);
    s.push(3);
    std::cout << "Top element: " << s.top() << std::endl; // Output: 3
    s.pop();
    std::cout << "Top element after pop: " << s.top() << std::endl; // Output: 2
    return 0;
}

OR

#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;
}

Time Complexity:

• Push Operation: O(n), where n is the number of elements in the queue. This is because elements are rotated in the queue after each push.
• Pop Operation: O(1)
• Top Operation: O(1)