# Implementation of Stack using two Queues

**Stack implementation using two Queues:** Here, we are going to **implement a stack using two queues using C++**.

Submitted by Radib Kar, on September 26, 2018

**Stack and Queue at a glance...**

**Stack:**

The stack is an ordered list where insertion and deletion are done from the same end, top. The last element that entered first is the first one to be deleted (the basic principle behind the LIFO). That means it is a data structure which is implemented as LIFO.

The main stack operations are (basic ADT operations)...

**push (int data):**Insertion at top**int pop():**Deletion from top

**Queue:**

The queue is an ordered list in which insertions are done at one end (rear) and deletions are done from another end (front). The first element that got inserted is the first one to be deleted (basic principle of FIFO). That means it is a data structure which is implemented as FIFO.

The main Queue operations are (basic ADT operations)...

**EnQueue (int data):**Insertion at rear end**int DeQueue():**Deletion from front end

## Implementation of a stack using two queues

Likewise, a queue can be implemented with two stacks, a stack can also be implemented using two queues. The basic idea is to perform stack ADT operations using the two queues.

So, we need to implement push(),pop() using DeQueue(), EnQueue() operations available for the queues.

**Implementation:**

Let q1 and q2 be the two queues...

struct stack{ struct queue *q1; struct queue *q2; }

**Algorithm to implement push and pop:**

**Push operation algorithm:**

- Check whether q1 is empty or not. If q1 is empty then EnQueue the element to q2.
- Otherwise EnQueue to q1.

push(struct stack *s,int data){ if(isempty(s->q1)) EnQueue(s->q2,data); else EnQueue(s->q1,data); }

**Pop operation algorithm**

The basic idea is to transfer n-1 elements (let n be the total no of elements) to other queue and delete the last one from a queue to perform the pop operation.

- If q1 is not empty then transfer n-1 elements from q1 to q2 and DeQueue the last element and return it.
- If q2 is not empty then transfer n-1 elements from q2 to q1 and DeQueue the last element and return it.

int pop(struct stack *s){ int count,size; if(isempty(s->q2)){ size=Size(s->q1); count=0; while(count<size-1){ //transferring n-1 elements EnQueue(s->q2,DeQueue(s->q1)); count++; } //last element to be popped return DeQueue(s->q1); } else{ size=Size(s->q2); count=0; while(count<size-1){ EnQueue(s->q1,DeQueue(s->q2)); count++; } return DeQueue(s->q1); } }

**Time complexity analysis:**

- Push: O(1)
- Pop: O(n) , since transferring n-1 elements

### Implementation code using C++ (using STL)

#include <bits/stdc++.h> using namespace std; struct Stack{ queue<int> q1,q2; void push(int x){ if(q1.empty()){ q2.push(x); //EnQueue operation using STL } else{ q1.push(x); //EnQueue operation using STL } } int pop(){ int count,size,item; if(q2.empty()){ size=q1.size(); //size=no of elements; count=0; while(count<size-1){ //transfering n-1 elements q2.push(q1.front()); // DeQueue operation using STL q1.pop(); count++; } item=q1.front(); q1.pop(); return item; //popping out the element } else{ size=q2.size(); count=0; while(count<size-1){ q1.push(q2.front()); q2.pop(); count++; } item=q2.front(); q2.pop(); return item; } } }; int main() { cout<<"implementing stack with two queues"<<endl; cout<<"enter any integer to push and 0 to stop pushing"<<endl; Stack s; int x,count=0; cin>>x; while(x){ s.push(x); cin>>x; count++; } cout<<"now popping......."<<endl; while(count){ cout<<s.pop()<<endl; count--; } cout<<"executed successfully!!!"<<endl; return 0; }

**Output**

implementing stack with two queues enter any integer to push and 0 to stop pushing 1 2 3 0 now popping....... 3 2 1 executed successfully!!!

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions

**Ad:**
Are you a blogger? Join our Blogging forum.

Learn PCB Designing: PCB DESIGNING TUTORIAL