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
- Start
- Declare two queues: queue1, queue2
- To Push, add the element to queue1
- 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
- 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