Implementation of Stack Using Queue

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

Objective

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

#include <iostream>
#include <queue>
using namespace std;

class Stack {
    queue<int> q1, q2;
    int curr_size;

public:
    Stack() {
        curr_size = 0;
    }

    void push(int x) {
        curr_size++;
        q1.push(x);
    }

    void pop() {
        if (q1.empty())
            return;
        while (q1.size() != 1) {
            q2.push(q1.front());
            q1.pop();
        }
        q1.pop();
        curr_size--;

        queue<int> q = q1;
        q1 = q2;
        q2 = q;
    }

    int top() {
        if (q1.empty())
            return -1;
        while (q1.size() != 1) {
            q2.push(q1.front());
            q1.pop();
        }

        int temp = q1.front();
        q1.pop();
        q2.push(temp);

        queue<int> q = q1;
        q1 = q2;
        q2 = q;

        return temp;
    }

    int size() {
        return curr_size;
    }
};

int main() {
    Stack s;
    s.push(1);
    s.push(2);
    cout << "Current top of stack: " << s.top() << endl;
    s.pop();
    s.push(3);
    cout << "Current top of stack: " << s.top() << endl;
    s.pop();

    return 0;
}

Discussion of Algorithms

1. Start
2. Declare two queues: queue1, queue2
3. To Push, add the element to queue1
4. To Pop, if queue1 is not empty, transfer all but the last element of queue1 to queue2, then dequeue the remaining element in queue1. Swap the names of queue1 and queue2
5. End

Representations

Flow Diagram

   +----------------------------------+
   |                                  |
   |           Start                  |
   |             |                    |
   +----------------------------------+
                  |
                  V
   +----------------------------------+
   |                                  |
   |      Declare Stack object s      |
   |             |                    |
   +----------------------------------+
                  |
                  V
   +----------------------------------+
   |                                  |
   |         Push operations          |
   |             |                    |
   +----------------------------------+
                  |
                  V
   +----------------------------------+
   |                                  |
   |    Print the top of the stack    |
   |             |                    |
   +----------------------------------+
                  |
                  V
   +----------------------------------+
   |                                  |
   |         Pop operation            |
   |             |                    |
   +----------------------------------+
                  |
                  V
   +----------------------------------+
   |                                  |
   |    Print the new top of stack    |
   |             |                    |
   +----------------------------------+
                  |
                  V
   +----------------------------------+
   |                                  |
   |             Exit                 |
   |             |                    |
   +----------------------------------+

Tabular Dry Run

Push | Top | Pop | Elements
  1  |     |     | 1
  2  |     |     | 1 2
     |  2  |     | 1 2
     |     |  2  | 1
  3  |     |     | 1 3
     |  3  |     | 1 3
     |     |  3  | 1

Results/Output

Push 1
Push 2
Pop -> returns 2
Push 3
Pop -> returns 3