Lecture 261:- Queue using 2 Stacks

You can implement a queue using two stacks in C++. One stack will be used for enqueueing elements, and the other stack will be used for dequeueing elements. The process of dequeuing elements involves transferring elements from one stack to the other to reverse their order, making the element at the front of the queue accessible.

Here's a C++ implementation of a queue using two stacks:

cppCopy code

#include <iostream> #include <stack> class Queue { private:    std::stack<int> enqStack;    std::stack<int> deqStack; public:    void enqueue(int data) {        enqStack.push(data);    }    void dequeue() {        if (isEmpty()) {            std::cout << "Queue is empty. Cannot dequeue." << std::endl;            return;        }        if (deqStack.empty()) {            while (!enqStack.empty()) {                deqStack.push(enqStack.top());                enqStack.pop();            }        }        deqStack.pop();    }    int front() {        if (isEmpty()) {            std::cout << "Queue is empty." << std::endl;            return -1; // Assuming -1 is not a valid element in the queue.        }        if (deqStack.empty()) {            while (!enqStack.empty()) {                deqStack.push(enqStack.top());                enqStack.pop();            }        }        return deqStack.top();    }    bool isEmpty() {        return enqStack.empty() && deqStack.empty();    }    int size() {        return enqStack.size() + deqStack.size();    } }; int main() {    Queue queue;    queue.enqueue(10);    queue.enqueue(20);    queue.enqueue(30);    std::cout << "Front element: " << queue.front() << std::endl;    queue.dequeue();    std::cout << "Front element after dequeue: " << queue.front() << std::endl;    std::cout << "Queue size: " << queue.size() << std::endl;    return 0; }

In this implementation, we define a Queue class that uses two stacks: enqStack for enqueuing elements and deqStack for dequeuing elements. The enqueue() function pushes elements onto the enqStack, while the dequeue() function transfers elements from enqStack to deqStack if deqStack is empty. This operation effectively reverses the order of elements, making the front element accessible. The front() function retrieves the front element without removing it, and the isEmpty() and size() functions work similarly to previous implementations.

The main function demonstrates how to use the queue by enqueueing and dequeueing elements, checking the front element, and getting the queue's size.