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)
Python Code
from queue import LifoQueue
# using LifoQueue which is a stack in python
class Queue:
def __init__(self):
self.input = LifoQueue()
self.output = LifoQueue()
def push(self, data: int) -> None:
# Pop out all elements from the stack input
while not self.input.empty():
self.output.put(self.input.get())
# Insert the desired element in the stack input
print("The element pushed is", data)
self.input.put(data)
# Pop out elements from the stack output and push them into the stack input
while not self.output.empty():
self.input.put(self.output.get())
# Pop the element from the Queue
def pop(self) -> int:
if self.input.qsize() == 0:
print("Stack is empty")
exit(0)
val = self.input.get()
return val
def Top(self) -> int:
if self.input.qsize() == 0:
print("Stack is empty")
exit(0)
return self.input.queue[-1]
def size(self) -> int:
return self.input.qsize()
if __name__ == "__main__":
q = Queue()
q.push(3)
q.push(4)
print("The element poped is", q.pop())
q.push(5)
print("The top of the queue is", q.Top())
print("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)
Python Code
from queue import LifoQueue
# using LifoQueue which is a stack in python
class MyQueue:
def __init__(self):
self.input = LifoQueue()
self.output = LifoQueue()
# Push element x to the back of queue.
def push(self, x: int) -> None:
print("The element pushed is ", x)
self.input.put(x)
# Removes the element from in front of queue and returns that element.
def pop(self) -> int:
# shift input to output
if self.output.empty():
while not self.input.empty():
self.output.put(self.input.get())
x = self.output.get()
return x
# Get the front element.
def top(self) -> int:
# shift input to output
if self.output.empty():
while not self.input.empty():
self.output.put(self.input.get())
return self.output.queue[-1]
def size(self) -> int:
return self.input.qsize() + self.output.qsize()
if __name__ == "__main__":
q = MyQueue()
q.push(3)
q.push(4)
print("The element poped is ", q.pop())
q.push(5)
print("The top of the queue is ", q.top())
print("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 of the queue is 4
The size of the queue is 2
Time Complexity: O(1 )
Space Complexity: O(2N)
Special thanks to Gurmeet Singh and Sudip Ghosh for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article