Implementation of Stack Using Circular Queue

To understand the implementation of a stack using a circular queue using C++

Objective

To understand the implementation of a stack using a circular queue using C++

#include <iostream>
#include <queue>

using namespace std;

class Stack {
    // Two queues to implement stack
    queue<int> q1, q2;
    int curr_size;
 
public:
    Stack() { curr_size = 0; }

    void push(int x)
    {
        curr_size++;

        // Push x first into empty q2
        q2.push(x);
 
        // Push all the remaining elements in q1 to q2
        while (!q1.empty()) {
            q2.push(q1.front());
            q1.pop();
        }
 
        // swap the names of two queues
        queue<int> q = q1;
        q1 = q2;
        q2 = q;
    }

    void pop()
    {
        // if no elements are there in q1
        if (q1.empty())
            return;
        q1.pop();
        curr_size--;
    }

    int top()
    {
        if (q1.empty())
            return -1;
        return q1.front();
    }

    int size() { return curr_size; }
};

int main()
{
    Stack s;
    s.push(1);
    s.push(2);
    s.push(3);

    cout << "current size: " << s.size() << endl;
    cout << s.top() << endl;
    s.pop();
    cout << s.top() << endl;
    s.pop();
    cout << s.top() << endl;

    cout << "current size: " << s.size() << endl;
    return 0;
}

Discussion of Algorithms

1. Start
2. Declare a circular queue with capacity n
3. For stack operations:
• To push an element, add element to the end of the queue
• To pop an element, remove the last element from the queue
• To get the top of the stack, get the last element from the queue
4. End

Representations

Flow Diagram

   +----------------------------------+
   |                                  |
   |           Start                  |
   |             |                    |
   +----------------------------------+
                  |
                  V
   +----------------------------------+
   |                                  |
   |         Push operations          |
   |             |                    |
   +----------------------------------+
                  |
                  V
   +----------------------------------+
   |                                  |
   |         Pop operations           |
   |             |                    |
   +----------------------------------+
                  |
                  V
   +----------------------------------+
   |                                  |
   |          Top operation           |
   |             |                    |
   +----------------------------------+
                  |
                  V
   +----------------------------------+
   |                                  |
   |     Print current size           |
   |             |                    |
   +----------------------------------+
                  |
                  V
   +----------------------------------+
   |                                  |
   |             Exit                 |
   |             |                    |
   +----------------------------------+

Tabular Dry Run

Push | Size | Top | Pop
  1  |      |     |
  2  |      |     |
  3  |      |     |
     |  3   |  3  | 
     |      |     |  3 
     |      |  2  |  
     |      |     |  2 
     |      |  1  |   
     |  1   |     |   

Results/Output

The stack has been successfully created using a circular queue

current size: 3
3
2
1
current size: 1