# Implement Queue using Stack

Problem Statement: Given a Stack having some elements stored in it. Can you implement a
Queue using the given Stack?

Queue: A Queue is a linear data structure that works on the basis of FIFO(First in First out). This means the element added at first will be removed first from the Queue.

Disclaimer: Don’t jump directly to the solution, try it out yourself first.

Solution 1: Using two Stacks where push operation is O(N)

Approach: push(x) -> pop()-> top()-> size()->

size() operation is for returning the size of a queue which can be done by using the function Stack1. size(). It will actually return the total number of elements in the queue.

Code:

## C++ Code

``````#include <bits/stdc++.h>

using namespace std;

struct Queue {
stack < int > input, output;

// Push elements in queue
void Push(int data) {
// Pop out all elements from the stack input
while (!input.empty()) {
output.push(input.top());
input.pop();
}
// Insert the desired element in the stack input
cout << "The element pushed is " << data << endl;
input.push(data);
// Pop out elements from the stack output and push them into the stack input
while (!output.empty()) {
input.push(output.top());
output.pop();
}
}
// Pop the element from the Queue
int Pop() {
if (input.empty()) {
cout << "Stack is empty";
exit(0);
}
int val = input.top();
input.pop();
return val;
}
// Return the Topmost element from the Queue
int Top() {
if (input.empty()) {
cout << "Stack is empty";
exit(0);
}
return input.top();
}
// Return the size of the Queue
int size() {
return input.size();
}
};
int main() {
Queue q;
q.Push(3);
q.Push(4);
cout << "The element poped is " << q.Pop() << endl;
q.Push(5);
cout << "The top of the queue is " << q.Top() << endl;
cout << "The size of the queue is " << q.size() << endl;
}``````

Output:

The element pushed is 3

The element pushed is 4

The element poped is 3

The element pushed is 5

The top of the queue is 4

The size of the queue is 2

Time Complexity: O(N )

Space Complexity: O(2N)

## Java Code

``````import java.util.*;

class MyQueue {
Stack < Integer > input = new Stack < > ();
Stack < Integer > output = new Stack < > ();
/** Initialize your data structure here. */
public MyQueue() {

}

/** Push element x to the back of queue. */
public void push(int x) {
while (input.empty() == false) {
output.push(input.peek());
input.pop();
}
// Insert the desired element in the stack input
System.out.println("The element pushed is " + x);
input.push(x);
// Pop out elements from the stack output and push them into the stack input
while (output.empty() == false) {
input.push(output.peek());
output.pop();
}

}

/** Removes the element from in front of queue and returns that element. */
public int pop() {
// shift input to output
if (input.empty()) {
System.out.println("Stack is empty");

}
int val = input.peek();
input.pop();
return val;

}

/** Get the front element. */
public int peek() {
// shift input to output
if (input.empty()) {
System.out.println("Stack is empty");

}
return input.peek();
}

int size() {
return input.size();
}
}
class TUF {
public static void main(String args[]) {
MyQueue q = new MyQueue();
q.push(3);
q.push(4);
System.out.println("The element poped is " + q.pop());
q.push(5);
System.out.println("The top element is " + q.peek());
System.out.println("The size of the queue is " + q.size());

}
}``````

Output:

The element pushed is 3
The element pushed is 4
The element poped is 3
The element pushed is 5
The top element is 4
The size of the queue is 2

Time Complexity: O(N )

Space Complexity: O(2N)

Solution 2: Using two Stacks where push operation is O(1)

Approach :

Push()-> Pop()->  top()->  Size(): Code:

## C++ Code

``````#include <bits/stdc++.h>

using namespace std;

class MyQueue {
public:
stack < int > input, output;
/** Initialize your data structure here. */
MyQueue() {

}

/** Push element x to the back of queue. */
void push(int x) {
cout << "The element pushed is " << x << endl;
input.push(x);
}

/** Removes the element from in front of queue and returns that element. */
int pop() {
// shift input to output
if (output.empty())
while (input.size())
output.push(input.top()), input.pop();

int x = output.top();
output.pop();
return x;
}

/** Get the front element. */
int top() {
// shift input to output
if (output.empty())
while (input.size())
output.push(input.top()), input.pop();
return output.top();
}

int size() {
return (output.size() + input.size());
}

};
int main() {
MyQueue q;
q.push(3);
q.push(4);
cout << "The element poped is " << q.pop() << endl;
q.push(5);
cout << "The top of the queue is " << q.top() << endl;
cout << "The size of the queue is " << q.size() << endl;

}``````

Output:

The element pushed is 3

The element pushed is 4

The element poped is 3

The element pushed is 5

The top of the queue is 4

The size of the queue is 2

Time Complexity: O(1 )

Space Complexity: O(2N)

## Java Code

``````import java.util.*;

class MyQueue {
Stack < Integer > input = new Stack < > ();
Stack < Integer > output = new Stack < > ();
/** Initialize your data structure here. */
public MyQueue() {

}

/** Push element x to the back of queue. */
public void push(int x) {
System.out.println("The element pushed is " + x);
input.push(x);
}

/** Removes the element from in front of queue and returns that element. */
public int pop() {
// shift input to output
if (output.empty())
while (input.empty() == false) {
output.push(input.peek());
input.pop();
}

int x = output.peek();
output.pop();
return x;
}

/** Get the front element. */
public int peek() {
// shift input to output
if (output.empty())
while (input.empty() == false) {
output.push(input.peek());
input.pop();
}
return output.peek();
}
int size() {
return (output.size() + input.size());
}

}
class TUF {
public static void main(String args[]) {
MyQueue q = new MyQueue();
q.push(3);
q.push(4);
System.out.println("The element poped is " + q.pop());
q.push(5);
System.out.println("The top element is " + q.peek());
System.out.println("The size of the queue is " + q.size());

}
}``````

Output:

The element pushed is 3
The element pushed is 4
The element poped is 3
The element pushed is 5
The top element is 4
The size of the queue is 2

Time Complexity: O(1 )

Space Complexity: O(2N)