Question

Show how to implement a stack using two queues. Analyze the running time of the stack operations. Assume that two queues Q1 and Q2 are the only data structures you can use so you shouldn’t need any auxiliary arrays.

Answer 1

In order to implement stack using queues, we need to maintain two queues que1 and que2. Also we will keep top stack element in a constant memory.

#include <bits/stdc++.h>
using namespace std;
// we create a class stack to be implemented by two queue's.
class Stack{
queue<int>que1,que2;// these are the two queues we use to impelement the stack
int top_element;//stores the top element of the stack
int size_of_stack;//gives the size of stack at any given time
public:
Stack(){
size_of_stack=0;//constructor to initialise the current size=0
  
}
// gice the size of stack at any moment
int size(){
return size_of_stack;
}
//now we are gonna make 3 function to perform pop, push and top function of stack
void push(int k)
{
que1.push(k);// we always push the new element in que1
size_of_stack=size_of_stack+1;// we increase the size of stack
top_element=k;//it will be the top element;
  
}
int top()// returns top element of the stack
{
return top_element;
}
bool isempty()// return true if stack is empty
{
if(size_of_stack==0)
return true;
return false;
}
void pop(){
// since queues are based on FIFO(first in first out) while stack follow LIFO(last in first out)
// so when we need to pop an element from stack, we need the last element that we pushed in queue que1
//so we pop all elements from except the last one from que1 and push them in que2, and then pop the last element of que1
//now que2 contains all elements of que1(in the same order as they were in que1), so now que2 have become que1, so we swap names of que1 and que2
// below is the implementation of the idea
if(que1.empty())// if que1 is empty, stack is empty
return;
  
int k=que1.size();
//push all elemnts in que2 except the last element
while(k>1)
{
top_element=que1.front();
que2.push(top_element);
que1.pop();
k--;
}
//removing the last element
que1.pop();
//decrasing the size
size_of_stack=size_of_stack-1;
  
//swappinf the two queue
queue<int>temp=que2;
que2=que1;
que1=temp;
  
  
  
  
  
}

  
};

int main() {
   // your code goes here
   Stack s;// creating a stack
   s.push(1);
   s.push(2);
   s.push(21);
   s.push(46);
   cout<<s.top()<<endl;
   s.pop();
   cout<<s.top()<<endl;
   cout<<s.size()<<endl;
   cout<<s.isempty();
   return 0;
}

Sample output

46
21
3
0

Time complexity analysis

push():

O(1), since we simply push an element in que1

pop()

If n is size of stack, O(n), since we pop n elements from que1 and and push n-1 elements into que2, this gives us 2n-1 operatons

top()

O(1) since we always maintain the top element in sepearte variable

isempty()

O(1) we simply check if size_of_stack is zero or not

Please give a like if you liked the answer.Thank you!