# Implementation of Queue using two Stacks

**Queue Implementation using Two Stacks in C++:** Here, we are going to **implement a C++ program to implement Queue using two Stacks**.

Submitted by Radib Kar, on September 25, 2018

**Queue:**

A queue is a data structure for storing data where the order in which data arrives is important. The queue is implemented as FIFO (First in First Out).

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).

The main Queue operations are:

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

**Stack:**

A stack is also another data structure which is implemented as LIFO.

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).

The main stack operations are:

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

## Implementing Queue using stack

A queue can be implanted using stack also. We need two stacks for implementation. The basic idea behind the implementation is to implement the queue operations (enqueue, dequeue) with stack operations (push, pop).

**Implementation:**

Let s1 and s2 be the two stacks used for implanting the queue.

struct queue{ struct stack *s1; // this stack is for enqueue operation struct stack *s2; // this stack is for dequeue operation }

**Enqueue algorithm:**

Just push to stack s1

void Enqueue(struct queue *q, int data){ push(q->s1,data); //data pushed to stack s1 }

**Dequeue algorithm**

Dequeue operation is little expansive here, we need to check few things like whether stack s2 is empty or not (stack s2 is for dequeuer operation). The basic idea is if s2 is empty we transfer all element of s1 to s2 and pop s2. The popped element is same as the dequeued one. Whenever we transfer all element from s1 to s2, the top element of s2 becomes the first one to enter s1 thus popping s2 deletes/returns the first element that was enqueued, maintaining the queue property FIFO.

Let's check the algorithm:

- If the stack s2 is not empty then pop from s2.
- If stack s2 is empty, then transfer all elements from s1 to s2 and pop from s2.
- If stack1 is empty throw an error. (underflow problem)

int Dequeue(struct queue *q1){ if (!isempty( q->s2)) //checking whether s2 is empty or not return pop(q->s2); // if s2 is not empty return popped element else{ while(!isempty(q->s1)) push(q->s2,pop(q->s1)); //transfer all element from s1 to s2 return pop(q->s2); } }

**Time complexity analysis:**

- Enqueuer operation : O(1)
- Dequeue operation: O(1) (amortized complexity)

### C++ implementation using STL

// header file to include all libraries #include <bits/stdc++.h> using namespace std; struct Queue { stack<int> s1, s2; // stl used // Enqueue an item to the queue void enQueue(int x) { // Push item into the first stack s1.push(x); } // Dequeue an item from the queue int deQueue() { // if both stacks are empty if (s1.empty() && s2.empty()){ cout << "Queue is empty"; exit(0); } // if s2 is empty, move elements from s1 if (s2.empty()) { while (!s1.empty()) { s2.push(s1.top()); // using stl operation top() s1.pop(); } } // return the top item from s2 int x = s2.top(); s2.pop(); return x; } }; // main function int main() { Queue q; int x,count=0; cout<<"press 0 to stop push operaton, else enqueue integers"<<endl; cin>>x; while(x){ q.enQueue(x); count++; cin>>x; } cout<<"dequeueing...."<<endl; while(count){ cout<<q.deQueue()<<endl; count--; } cout<<"execution successful"<<endl; return 0; }

**Output**

press 0 to stop push operaton, else enqueue integers 10 20 5 7 0 dequeueing... 10 20 5 7 execution successful

**Explanation:**

10,20,5,7,0 are the input taken from console and 10,20,5,7 are enqueued. Enqueue operation stopped as soon as user gave input 0.

Then dequeue operation started and the dequeue order is FIFO 10,20,5,7

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.